- 문제에 접근하는 순서는 무조건 Bruteforce ▶ DP ▶ Greedy 순서입니다.
- Greedy(그리디) 알고리즘을 적용하기 위해서는 부분 문제의 최적해가 전체 문제의 최적해가 됨을 증명해야 합니다.
- 코딩테스트의 시간제약 특성 상 시험시간 내에 이를 증명하는 것은 불가능합니다.
- 결과적으로, 문제 조건 및 범위에 따라 시간복잡도 및 공간복잡도를 추론한 뒤 '아, 완전탐색, DP도 시간초과/메모리초과가 날 것 같네, 그렇다면 그리디로 풀어봐야 겠다'고 예상하고 접근해야 합니다.
- 그리디 알고리즘 문제는 그림을 그려보는 것이 상당히 도움이 됩니다.
- 문제 예제에 맞게 동그라미나 막대그래프를 그려보며 도식화하면 문제를 푸는 아이디어를 얻는 데 도움이 됩니다.
- 그리디 알고리즘은 거의 정렬 + 우선순위 큐로 풀이합니다.
- 특정 기준에 따라
sort()로 정렬한 뒤 - 우선순위 큐에 넣어 문제 조건에 맞게
pop()합니다. - 보통 이러한 일련의 과정을 거쳐서 풉니다.
- 특정 기준에 따라
임베디드 시스템 공학자를 지망하는 컴퓨터공학+전자공학 복수전공 학부생입니다. 타인의 피드백을 수용하고 숙고하고 대응하며 자극과 반응 사이의 간격을 늘리며 스스로 반응을 컨트롤 할 수 있는 주도적인 사람이 되는 것이 저의 20대의 목표입니다.
좋은 글 감사합니다. 자주 올게요 :)