그리디, 라인스위핑, 투포인터

1️⃣ 그리디

Greedy는 '탐욕스러운, 욕심 많은'이라는 뜻으로 각 단계마다 지역적 최적해가 궁극적으로 전역 최적해가 되는 것이다.

(선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달한다)

 

그리디 알고리즘으로 문제를 풀기 위해서는 아래 두 가지 조건을 충족해야 한다.

1. 최적 부분 구조 - 현재 상태에서의 최적해가 전역적인 최적해로 이어져야 한다.
2. 탐욕적 속성(앞의 선택이 이후의 선택에 영향을 주지 않음)이 증명되어야 한다
   • 귀류, 귀납, 대우증명을 사용할 수 있으며, 귀류법을 보통 자주 사용
   • 귀류법 - 어떤 명제가 참이라고 가정한 후, 모순을 이끌어내 그 가정이 거짓임을 증명하는 방법

 

코테에서 그리디를 풀기 위해 증명까지 해야 하는가?!

💡 무식하게 풀기 → DP → 그리디

DP는 완전탐색으로 경우의 수를 모두 생각하지만, 메모이제이션을 통해 시간복잡도를 줄이는 것이다.

만약 DP를 사용하기에도 공간복잡도가 너무 크다면 그 때 그리디를 생각해보자.

 

그리디를 풀다 보면 자주 나오는 풀이가 있어 이것을 외우면 좋다! 보통 정렬, 우선순위 큐를 사용하는 2가지의 한정적인 방법으로 주로 나온다.

 

2️⃣ 라인 스위핑

도식화

하나의 라인을 빗자루 쓸듯이 한 쪽 방향부터 시작해서 다른 방향으로 스캔해가면서 탐색하는 알고리즘이다.

 

활용 문제

2170번: 선 긋기

 

3️⃣ 투 포인터

2개의 포인터를 가지고 탐색하는 알고리즘으로, 시작점과 끝점으로 하여 시작하거나 둘 다 시작점에서 같이 시작할 수 있다.

 

시작점과 끝점에서 시작

 

둘 다 시작점에서 시작

활용 문제

3273번: 두 수의 합

 

Reference

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트 - 인프런 | 강의

[알고리즘] 탐욕 알고리즘(Greedy Algorithm) - 하나몬