LeetCode 121 Best Time to Buy and Sell Stock 풀이: 최저가를 유지하는 그리디
LeetCode 121 Best Time to Buy and Sell Stock을 한 번 훑으며 최저 매수가와 최대 이익을 갱신한다. 매수일이 매도일보다 앞서야 하는 조건을 지키면서 O(n) 시간과 O(1) 공간에 푸는 방법을 설명한다.
#그리디
매 순간 최선의 선택을 반복해 답을 만드는 그리디 문제를 다룬다. 현재 10개의 풀이가 있다.
LeetCode 853 Car Fleet 풀이: 도착 시간을 비교하는 그리디
목적지에 가까운 차부터 도착 시간을 계산해 앞 차와 합쳐지는지 판별한다. 위치순 정렬과 도착 시간의 단조성을 이용해 O(n log n)에 플릿 수를 구한다.
프로그래머스 섬 연결하기 풀이: 크루스칼 최소 신장 트리
프로그래머스 섬 연결하기에서 비용순으로 다리를 살펴보고 Union-Find로 사이클을 막는다. 서로 다른 연결 요소를 잇는 간선만 골라 최소 신장 트리를 만든다.
프로그래머스 지폐 접기 풀이: 긴 변을 줄이는 그리디
프로그래머스 PCCE 지폐 접기에서 매번 긴 변을 절반으로 줄여 지갑에 들어가는지 확인한다. 90도 회전 가능한 크기 비교와 최소 접기 횟수를 다룬다.
프로그래머스 조이스틱 풀이: 알파벳 변경과 커서 이동 그리디
프로그래머스 조이스틱에서 알파벳 변경 비용과 좌우 이동 비용을 나눠 계산한다. 연속된 A 구간을 건너뛰는 경로까지 비교해 최소 조작 횟수를 찾는다.
프로그래머스 점프와 순간 이동 풀이: 홀수 위치만 점프하는 그리디
프로그래머스 점프와 순간 이동에서 목적지부터 거꾸로 이동하며 홀수 위치에서만 배터리를 쓴다. 짝수 위치는 순간 이동으로 절반씩 줄여 최소 점프 수를 구한다.
프로그래머스 구명보트 풀이: 정렬과 양끝 투 포인터 그리디
프로그래머스 구명보트에서 가장 무거운 사람과 가장 가벼운 사람을 함께 태울 수 있는지 확인한다. 정렬된 배열의 양끝 포인터로 필요한 보트 수를 센다.
프로그래머스 숫자 게임 풀이: 정렬과 그리디 매칭
프로그래머스 숫자 게임에서 두 팀의 숫자를 정렬하고, A팀을 이길 수 있는 가장 작은 B팀 숫자를 짝짓는다. 불필요하게 큰 수를 아껴 최대 승점을 만든다.
프로그래머스 기지국 설치 풀이: 빈 구간 길이 계산 그리디
프로그래머스 기지국 설치에서 기존 기지국 사이의 빈 구간만 살펴보고, 한 기지국의 전파 범위로 나누어 필요한 수를 구한다. 아파트를 전부 순회하지 않는 경계 처리와 올림 나눗셈을 설명한다.
프로그래머스 단속카메라 풀이: 종료 지점 기준 그리디
프로그래머스 단속카메라에서 차량 경로를 종료 지점 기준으로 정렬한다. 아직 감시되지 않은 경로의 끝에 카메라를 두어 필요한 대수를 최소화한다.
그리디 알고리즘 학습 가이드
필요한 주제만 펼쳐서 그리디 선택을 설계하고 검증하는 방법을 익힌다.
그리디 기본 개념
그리디 알고리즘은 매 순간 현재 기준에서 가장 좋아 보이는 선택을 하고, 선택을 되돌리지 않은 채 최종 답을 만든다.
- 후보: 현재 선택할 수 있는 여러 선택지
- 그리디 기준: 매 단계에서 어떤 후보를 고를지 정하는 규칙
- 확정: 선택한 값을 다시 바꾸지 않고 다음 단계로 진행
- 목표: 모든 선택을 마친 뒤 최적의 결과를 얻음
활동 선택, 최소 회의실 배정, 현재까지의 최솟값 유지처럼 한 번의 선택이 이후 상태를 제한하는 문제에서 자주 쓴다.
그리디 선택이 안전한지 증명하기
그리디 문제는 “지금 가장 좋아 보이는 선택”이라는 직관만으로는 충분하지 않다. 해당 선택을 포함해도 최적해를 잃지 않는 근거가 필요하다.
- 교환 논증: 어떤 최적해의 선택을 그리디 선택으로 바꾸어도 결과가 나빠지지 않음을 보임
- 탐욕적 선택 속성: 현재의 최적 선택을 포함하는 최적해가 항상 존재함
- 최적 부분 구조: 선택 후 남은 문제의 최적해도 전체 최적해를 구성함
증명하기 어렵다면 그리디를 바로 구현하지 말고, 정렬·동적 계획법·완전탐색과 비교해 선택을 되돌릴 필요가 없는지 먼저 확인한다.
대표적인 그리디 패턴
| 문제 조건 | 그리디 기준 | 대표 유형 |
|---|---|---|
| 겹치지 않는 구간을 최대한 선택 | 끝나는 시간이 빠른 순서 | 활동 선택 |
| 현재까지의 최선 상태 유지 | 최솟값·최댓값 갱신 | 주식 최대 수익 |
| 가장 큰 우선순위부터 처리 | 힙의 최댓값 또는 최솟값 | 작업·자원 배정 |
| 앞선 선택과 충돌하지 않게 배치 | 정렬된 순서로 가능한 선택 | 회의실·구간 배정 |
| 앞 차량이나 앞 상태를 따라잡는지 비교 | 도착 시간 또는 누적 상태 | Car Fleet |
그리디가 실패하는 경우
모든 문제에서 가장 큰 값이나 가장 작은 값을 먼저 고르면 안 된다. 현재 선택이 미래의 조합을 제한하고, 선택을 바꿨을 때 더 좋은 결과가 생길 수 있으면 그리디만으로는 부족하다.
이 경우에는 여러 선택 조합을 비교해야 하므로 동적 계획법이나 완전탐색이 필요할 수 있다. 그리디를 선택하기 전에 반례를 만들어 보는 습관이 중요하다.
자주 하는 실수
- 정렬 기준을 문제의 목표와 반대로 선택하는 경우
- 현재 값이 좋아 보인다는 이유만으로 그리디의 정당성을 증명하지 않는 경우
- 같은 값이나 같은 끝점의 포함 여부를 잘못 처리하는 경우
- 선택한 항목과 충돌하는 이전 상태를 제거하지 않는 경우
- 그리디로 풀 수 없는 반례를 동적 계획법 없이 처리하려는 경우