ch3. 그리디 알고리즘
코딩 테스트 개념잡기 첫 번째로 그리디(greedy)알고리즘에 대해서 정리해보려합니다.
출처:https://commons.wikimedia.org/wiki/File:Greedy-search-path-example.gif
그리디 알고리즘은 말 그대로 욕심쟁이 알고리즘입니다.
탐욕법이라고도 부르는데, 현재 상황에서 가장 좋은 것을 고르는 방법입니다.
위의 예시처럼 그리디 알고리즘을 이용해 그래프에서 가장 큰 수를 찾으려고 한다면, 현재 위치(7)과 연결된 두 노드 중 큰 노드(12)를 고르는 것입니다.
그리고 이동한 노드(12)에서 또 다시 가장 큰 수를 찾으면 결과적으로 6에 도달하게 됩니다.
단점
전체 문제에 대한 최선의 결과가 아닐 수 있다.
다시 말해서 위의 예시처럼 각 노드에서 가장 큰 수를 골랐지만 결과적으로 전체에서 가장 큰 수를 고르지는 못한 경우입니다.
장점
빠르게 최적해로 가는 근사치를 구할 수 있다
하지만 위와 같은 단점이 있기 때문에 특정 조건에서만 사용 가능합니다.
그럼 어떨 때 사용할 수 있을까?
1. 탐욕적 선택 특성(Greedy choice property)
2. 최적 부분 구조(Optimal substructure)
우리는 위의 두 가지 조건에서 그리디 알고리즘을 적용할 수 있습니다.
다시 위의 예시를 보겠습니다.
우리가 12를 고르게 되면서 3으로 가는 경우가 사라졌습니다. 이러면 12를 고른 결정이 최종 결과에 영향을 미치게 됩니다.
이는 탐욕적 선택 특성에 어긋납니다.
탐욕적 선택 특성이란, 지금의 선택이 다음 선택에 영향을 주지 않는 것을 의미합니다.
유명한 다른 예시를 들어보겠습니다.
서울에서 대전을 거쳐서 부산으로 가장 빨리가는 방법을 찾는 문제입니다.
출처:https://yganalyst.github.io/concept/algo_cc_book_1/
서울에서 대전까지의 경로가 대전에서 부산까지의 경로에 영향을 미치지 않습니다.
그래서 서울에서 대전까지 가장 빠른 경로 7,
대전에서 부산까지 가장 빠른 경로 22를 고르면
결과적으로 서울에서 부산까지 가장 빠른 경로를 찾을 수 있는 것입니다.
각 부분의 최선의 선택의 합이 전체의 최선의 결과가 되는 것이 최적 부분 구조입니다.
따라서 코딩테스트에서 특정 문제를 만났을 때 그리디 알고리즘을 사용하고 싶다면, 현재 상황의 최선의 선택의 조합으로 문제가 해결되는지 판단하는 것이 핵심입니다.
예제 종류
-
거스름돈 문제 : 가장 적은 수의 동전을 이용해 특정 값을 지불하는 문제입니다
-
1이 될 때까지 : 어떤 수 N이 1이 될 때까지 -1또는 %K를 반복 수행 하여 가장 적을 횟수로 1을 만드는 문제입니다.
위의 문제들은 제가 풀이하면 올리도록 하겠습니다
끝.
