[바킹독의 실전 알고리즘] 0x11강 - 그리디

1. 알고리즘 설명

 

그리디 알고리즘(Greedy Algorithm)이란?

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

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

 

예시로는 0x0E강-정렬1에서 언급된 예시가 있음!

정렬된 두 배열을 하나의 배열로 합칠 때, 기본 정렬(삽입, 선택, 버블)이 O((N+M)^2)을 걸려서 했던 일을 O(N+M)에 수행할 수 있었음. 즉, 관찰을 통해 탐색 범위를 줄였고 시간을 줄였기 때문에 그리디 알고리즘의 예시라고 할 수 있음.

 

풀이 흐름

 

이상적인 풀이 흐름

1) 관찰을 통해 탐색 범위를 줄이는 방법을 고안함

2) 탐색 범위를 줄여도 올바른 결과를 낸다는 사실을 수학적으로 증명함

3) 구현하여 문제를 통과!

 

...이지만 코테에서 현실적인 풀이 흐름을 보자면

1) 관찰을 통해 탐색 범위를 줄이는 방법을 고안함

2) 탐색 범위를 줄여도 올바른 결과를 낸다는 믿음을 가지고

3) 구현해서 문제 통과!

이렇게 정리가 됨. 하지만 절망적인 시나리오로 1) 잘못된 방법을 고안하고 3) 계속 틀리는 상황이 슬프지만 발생할 수 있기 때문에 전략이 필요함.

 

⭐코테 추천 전략⭐ 

1) 거의 똑같은 문제를 풀어봤거나 간단한 문제여서 그리디 풀이를 100% 확신하는 상태 

→  짜서 제출해보고 틀리면 손절! 오래 붙잡을수록 나만 손해임

2) 일단 확신은 없지만 맞는 것 같은 그리디 풀이를 찾은 상태

→ 일단 넘어간 후, 다른 문제를 다 풀었거나 종료 20-40분 남은 시점에 코딩 시작함. 

그리디로 풀 수 없는 문제인지 그리디로 착각하는 경우가 종종 있으므로 100% 확신이 없다면 다른 문제를 먼저 보는 걸 추천함.

 

2. 연습 문제

 

백준 1931번 - 회의실 배정 문제 풀이

https://shingy.tistory.com/28

[C++] 백준 1931번 - 회의실 배정 문제