그리디 알고리즘

지금 가장 최적인 답을 근시안적으로 택하는 알고리즘

= 관찰을 통해 탐색 범위를 줄이는 알고리즘

이상적인 풀이 흐름

1. 관찰을 통해 탐색 범위를 줄이는 방법
2. 탐색 범위를 줄여도 올바른 결과를 낸다는 사실을 수학적으로 증명 (실제 코테에서는 수학적 증명이 사실상 불가)
3. 구현해서 문제를 통과

코딩 테스트에서의 추천 전략

1. 거의 똑같은 문제를 풀어봤거나 간단한 문제여서 나의 그리디 풀이를 확신! ⇒ 짜서 제출해보고 틀리면 빠르게 손절
2. 100%확신은 없지만 맞는 것 같은 그리드 풀이를 찾았다. ⇒ 일단은 넘어가고 다른 문제를 풀게 없거나 종료가 20-40분 남은 시점에 시작

⇒ 코테에 그렇게 잘 나오는 문제는 아니다.

11047 - 동전

시간복잡도 : O(NK) ⇒ N = 10^8이므로 시간 초과 발생

 

1931 - 회의실배정

t 이후에 회의 A와 B를 선택하는 경우에서 회의 B를 선택했을 경우 (정답은 정해져있음 결국에는 회의 A도 선택하게되므로 지금 최선의 선택을 하지 않았을 경우 최선의 선택을 했을 때보다 더 결과가 좋아질 수 없음을 의미

• sort 순서에 따른 결과차이 (cmp2는 pair<int, int> cur의 cur.second에 의한 오름차순)

• 해당 문제에서 아래와 같은 코드도 결과1과 같은 결과를 얻을 수 있는데, 나중에 정렬강의 듣고 다시 생각해봐야겠다. (14:50)

그리디 같지만 아닌 문제들

12865, 1477 풀어보고 꼭 강의 보기!

 

그리디로 풀 수 있는 문제가 아닌데 그리디로 풀 수 있다고 착각하는 것을 조심!