그리디 알고리즘

나동빈님의 이것이 코딩 테스트다 강의를 이용해서 공부하고 있다.

신찬수 교수님 강의도 짬짬이 병행하고 있는데,

원론 + 실전문제풀이 느낌이라 딱 좋다.

---

 

- 맞힌 코드 -

(좌)해설 / (우)내 코드 - N, K = 25, 5

N이 10만까지이므로, 내 풀이방법처럼 할 수야 있지만,

좌측의 풀이방법의 시간복잡도에 비해 내 풀이의 시간복잡도가 높다.

(n - target)으로 덩어리로 쳐내냐 vs (n-target)만큼 반복으로 -1로 쳐내냐

 

나름대로 추적해보려고 했다.

29와 5를 입력했다.

29와 5의 1차 타겟은 25다(가장 가까운 5로 나눌 수 있는 수)

29에서 25까지 4(N - target)를 빼야하므로, 시행횟수는 4가 더해진다(result +=)

그렇게 N은 target과 동일해진다.

25 < 5는 거짓이기 때문에 넘어간다.

25를 5로 나누고, 시행횟수를 1 더한다. (1차 시행횟수 5)

 

5와 5의 2차 타겟은 5다.

5에서 5까지 0을 빼야하므로 시행횟수는 0이 더해진다

그렇게 N은 target과 동일해진다.

5 < 5는 거짓이기 때문에 넘어간다.

5를 5로 나누고 시행횟수를 1 더한다. (2차 시행횟수 6)

 

1과 5의 2차 타겟은 0이다.

1에서 0까지 빼야하므로 시행횟수는 1이 더해진다.

1 < 5는 참이기 때문에 반복문을 탈출한다.

 

1에서 0으로 만드는 시행이 있었으므로

result -1 해준다.

 

왜.. N - 1이지? (어차피 N은 0이 되니까.. 뭐 그런건가? 무슨 의미지?)

---

(좌)해설 / (우)내 코드

연산횟수가 왼쪽이 훨씬 적다.

---

맞게 푼 듯하다.

내 풀이에 반례가 있을 가능성이 더 높아보인다.

만약 반례가 없다면 시간복잡도는 내가 더 좋을지도?

---

오늘은 여기까쥐~