ndb796
Page 311. 모험가 길드 문제
안녕하세요. 책 너무 잘보고 있습니다. 감사합니다. 그런데 '모험가 길드 문제' 를 풀고나서, 그리디 말고 파라메트릭 서치 로도 풀수 있을거 같은데, 혹시, 파라메트릭 서치로 구현 하신 소스가 있을까요? java 나 c++ 소스이면, 더 좋을거 같습니다. 아니면, 혹시 파라메트릭 서치로 풀수 없는 건가요? 풀어 보려니깐 잘 안돼서요. 어쩌면, 책 이외의 질문 이라, 죄송 합니다.
안녕하세요 @world9604 님.
재미있는 질문 감사합니다.
파라메트릭 서치(parametric search)로 문제를 해결할 수 있다고 생각하시는 이유를 더 자세히 설명해 주시면 답변에 도움이 될 것 같습니다.
파라메트릭 서치로 해결할 수 있는 문제에 관하여
파라메트릭 서치로 문제를 해결할 때는, 현재의 문제가 최솟값을 찾거나(minimize), 최댓값을 찾는(maximize) 최적화(optimization) 문제이면서 탐색 범위를 따르는 변수 x에 대하여 어떠한 함수 f(x)가 단조 증가 함수 형태가 되어야 합니다.
이 문제를 한 번 파라메트릭 서치로 해결할 수 있는 형태로 정의하는 시도를 해봅시다. 먼저 모험가를 정렬한 뒤에, 매번 그룹에 포함할 모험가를 설정한다고 합시다. 예를 들어 각 모험가의 공포도가 1 2 2 2 3 이라고 하면 처음에 시작점(s) = 0, 끝점(e) = 4이되고 중간점(m)은 2가 되겠네요.
이때 중간점(mid)이 작을수록 더 적은 사람이 한 그룹에 들어가게 되며, 중간점(mid)이 클수록 더 많은 사람이 한 그룹에 들어가게 될 것을 예상할 수 있습니다. 그리고 현재 그룹에 포함된 사람의 수 = m - s + 1 이라고 정의할 수 있을 겁니다. 얼핏 보면 파라메트릭 서치로 문제를 해결할 수 있을 것처럼 보입니다.
다만 이 경우에 우리가 해결하고자 하는 문제는 "현재 그룹에 포함된 사람의 수가 arr[mid] 이상이라는 조건을 만족하는 mid 중에서, 가장 작은 mid 값 찾기"입니다. 하지만 arr[mid]는 mid에 따라서 계속 변화하기 때문에 항상 단조 증가 형태를 띤다고 볼 수 없습니다.
예시를 통한 이해
예를 들어 다음과 같이 각 모험가의 공포도가 나열되어 있다고 해봅시다.
1 3 4
처음에 시작점(s) = 0, 끝점(e) = 4라고 하면 중간점(m)은 1이 되겠네요. 중간점까지를 하나의 그룹으로 설정할 때, 현재 그룹에 포함되는 모험가의 수 = 중간점(m) - 시작점(s) + 1 = 2가 될 것입니다. 현재 그룹에 포함되는 모험가의 수가 현재 확인하고 있는 모험가의 공포도 arr[mid] = 3보다 작습니다.
그러면 왼쪽 부분을 탐색해야 할까요? 오른쪽 부분을 탐색해야 할까요?
이 경우에는 왼쪽 부분을 탐색해야 optimal solution을 찾을 수 있습니다. 하지만 3 3 3의 경우에서는 오른쪽 부분을 탐색해야 optimal solution을 찾을 수 있습니다.
감사합니다. 나동빈 드림
