몇 가지 Greedy

그리디 문제는 특수한 알고리즘이나 자료구조를 딱히 쓰지 않고 문제를 푸는 기법을 이야기합니다. 본디 그리디 알고리즘은 주어진 상황에서 최선의 선택을 해서 답을 구하는 방식이고 최적의 해인지 확인도 해야 한다고 하는데… 그냥 잘 보면 문제를 치밀하게 분석해서 다른 문제로 치환해서 푸는 방식입니다. (사실상 잘하기 제일 어려운…)

그래서 스핑크스의 수수께끼마냥 신박한, 모르면 못푸는(?) 경우의 문제들이 있고, 그럼에도 결국 몇 가지 자주 보이고 활용도 높은 유형들이 있기 마련입니다. 이것들을 기억하고자 조금 정리해둡니다.

1. Knapsack(백팩) 문제

너무 유명한 문제입니다.

• 크기가 한정된 백팩에 가장 값어치있는 물건을 담기

(값어치/크기) 가 큰 물건부터 넣어보면 빠르게 찾을 수 있다. 다만 이 경우는 fractional 한 경우!

⇒ 어떻게 채우는지 방법을 찾아야 한다면, 최적해의 상태에서 Backtracking을 하면 됩니다. tracking 데이터를 인자로 계속 넘겨준다던가… 하는건 좋지 않음!

⇒ fractional 하지 않은 경우에는 그리디를 쓸 수 없습니다. 일례로 (w2, c20), (w3, c30), (w4, 41) 인데 w5 limit인 반례 케이스가 있죠. 모든 경우(DP)를 고려해야 합니다. 비슷한 예로 “백팩에 물건을 가장 많이 담는 모든 경우의 수” 문제와는 다릅니다. 이것도 DP를 써야 합니다. Memoization 없이 일일이 구하는 건 시간복잡도가 엄청날 것이 자명하기 때문에…

2. 최적의 예약 시간대 찾는 문제

흔히 아래와 같은 문제들도 종종 보입니다. (결국 같은 문제)

• 비행기 예매를 안 겹치고 최대한 많이 할 수 있는 경우 구하기
• 회의실을 안 겹치고 최대한 예약하는 경우

대충 이런 그림이 있으면 열에 아홉은 이 문제…

“시작하는 시간의 역순으로 정렬해서 뒤에서부터 고르기"로 문제를 보면 비교적 풀기가 쉽습니다.

• 가장 나중에 시작하는 일을 먼저 뽑으면, 선택할 수 있는 다른 시간대를 가장 많이 고를 수 있는 것은 자명한 사실이고, 이를 여러번 반복해도 성립하므로 가능

시간복잡도는 Sorting 후 backward scanning이므로 O(nlogn)

참고로 이거 답 안다고 바로 Optimized Solution으로 가는 건 추천드리지 않습니다. Naive 솔루션부터 시작해서 인터뷰어와 (다 알지만은) 소소한 토의 및 합의를 거치며 optimal solution을 가는 것을 추천드립니다. 코딩인터뷰의 소소한 팁 ㅎㅎ.

이미지 출처: https://loosie.tistory.com/515?category=972195

3. 파라메트릭 서치

사실 결정문제에 해당되는 부류인데, 결국 문제를 바꿔 풀어서 최적해를 구하는 방식이라 그리디 형태의 유형에 넣기로 했다 (?) 사실 파라메트릭서치 이것도 굉장히 광범위한 문제들을 일컫는 경우라 적합한 분류는 아닌 것 같지만 …

파라메트릭 서치는 단순하다, 그냥 Predicate(조건)이 붙은 검색을 의미한다. 이걸 이용해서 그리디한 문제를 해결할 수 있다가 핵심 포인트이다.

카카오 코테 문제를 일례로 들면,

코딩 테스트를 총괄하는 무지는 안정적인 시험을 위해, 시험장에서 오는 트래픽을 k개의 그룹으로 나누어 각 그룹별 서버로 분산시키기로 하였습니다. 시험장 사이를 연결한 간선들 중 k-1개를 끊어서 시험장을 k 개의 그룹으로 나눌 계획입니다. 이때, 그룹별 최대 트래픽을 최소화하기 위하여 가장 큰 그룹의 인원을 최소화시켜야 합니다.

참고로 가중치의 총합은 112 이다.

최적해는 저렇게 생겼지만, 사실 어디서 어떻게 잘라야 하는지를 우리가 구체적으로 알 필요는 없다. 그럼 무엇을 구해야 하냐? 가장 공평하게 나누었을 때의 가장 큰 그룹의 인원을 구하는 것이다. 그런데 생각해보면 아무리 공평하게 나누어도 가장 큰 그룹은 112/3 = 38 보다 작을 수는 없다. 따라서, 문제를 아래와 같이 치환해서 풀어볼 수 있다.

• 트리를 임의로 K 그룹으로 나누었을 때, 그룹의 합이 Sum/K 보다 큰 것 중 최소값

따라서 이를 기반으로 그룹을 구성해서 최대값을 구해보고, 그것들 중 최솟값을 찾아 리턴하면 된다. (각 그룹을 만들때 그룹의 합이 Sum/K 보다 작거나 큰 것(전후로) 하나씩 경우를 두고 계속해서 DFS를 수행하며 그룹을 쪼개면 될 듯.) 그렇게 함으로서 Search Space를 크게 줄일 수 있다.

• 다만 그래프 분할 측면까지 고려하면 꽤 생각할 점이 많다. 특정 노드를 자르면 2개의 단절선이 생기는 경우가 있는데 이 경우까지 고려해서 DFS를 수행해야 할 것.
• 그래프 분할 관련 유형도 꽤 문제가 많은 것으로 알고있는데, 이후에 그래프 분할과 관련된 알고리즘 정리해 봐야겠다.

문제 및 풀이 출처: https://loosie.tistory.com/518?category=972195

---

이후에 더 있으면 추가할 예정.