탐욕 알고리즘 기법

탐욕 알고리즘 기법

처음에 탐욕 알고리즘은 꽤 공들여서 공부했기 때문에 기억이 새록새록하다 ㅎ.ㅎ

여기까진 재미있었다.

탐욕 알고리즘은 차근차근 local optimum 을 찾아서 global optimum 에 도달하는 것이다. 정말로 이게 끝이다 !

장점은 간단하다는 것이고, 단점은 간단한만큼 탐욕 알고리즘 기법을 통해서는 완전 최적해에 도달하지 못할 가능성이 있다는 것이다.

탐욕알고리즘 기법이라고 한 이유는 (코세라에서 이 부분이 엄청 햇갈렸는데) 탐욕 알고리즘이 하나의 구체적 알고리즘이라고 하기 보다는 탐욕 알고리즘의 원리로 구현된 다양한 알고리즘들이 존재하는 것이기 때문이다.

예를 들어 신청할 수 있는 되도록 많은 수업을 수강신청하고 싶다고 하였을 때

1. 가장 빨리 끝나는 과목을 고른다 (local optimum)

2. 첫 번째 과목이 끝난 후 시작하는 과목을 고르는 데 그 중 가장 빨리 끝나는 과목을 고른다 (local optimum)

…

이런 식으로 반복하는 것이다.

탐욕 알고리즘 기법이 안 먹히는 문제로는 잔돈 바꾸기 문제가 있었던 것 같은데 잘 기억이 나지 않는다. 그런데 내가 탐욕 알고리즘으로 했을 때 계속 안 됐던 기억은 확실하다.

=> 그러니까 탐욕 알고리즘은 단순하고 쉽지만 경우에 따라서 완벽한 정답을 찾아주지 못할 수도 있다 !

백준 문제 추천

친절하게 공유해주신 분이 있다.

출처 : 그리디 알고리즘-백준 문제

내일 동전 0, 신입사원, 회의실 배정 이렇게 세 문제를 풀어볼 계획이다.

leetcode, codewars 도 추천받은 사이트인데 고루 이용해야겠다.