최적화 문제 결정 문제로 바꿔 풀기 #알고리즘문제해결전략 ch.12

이 글은

'알고리즘 문제해결전략' (저자 구종만 , 출판사 인사이트)의 12번째 챕터(최적화 문제 결정 문제로 바꿔 풀기)의 내용을 정리한 글입니다.

(https://www.aladin.co.kr/shop/wproduct.aspx?ItemId=21089176)

---

알고리즘을 설계할 때,

어느 한 지점, 조합에 대해 대답하는 알고리즘보다

임의로 설정한 구간에 대해 대답하는 알고리즘을 설계하는 것이 더 쉬울 때가 있습니다.

예를 들어, 술게임(...)에서 많이 하는 1에서 50사이의 숫자 맞추기 게임은 두가지 버전이 있을 수 있을 것입니다 .

1. 어느 한 숫자를 부르면 그 숫자가 정답인지 아닌지만 알려주는 방식

2. 어느 한 숫자를 부르면 정답인 숫자가 더 큰지 작은지 알려주는 방식

당연히 2번 방식의 게임이 더 정답을 찾기 쉽겠죠?

1번 게임에서는 최대 50번까지 틀릴 수 있겠지만, 2번 게임에서는 lg50(대략 5~6)번 안에 정답을 맞출 수 있을 것입니다.

1번 게임에서는 한 지점(어느 한 숫자)에 대해서 진위 여부를 판별하고,

2번 게임에서는 구간에 대한 진위 여부를 판별할 수 있습니다.

이 진위 여부를 이용하여 정답이 존재하지 않을 구간을 후보에서 제거할 수 있게 되죠.

그 구간을 남은 구간의 절반씩으로 잡는다면, 즉 남은 구간을 이분하여 결정한다면,

시간 복잡도는 O(n)에서 O(lgn)으로 떨어질 것입니다.

모든 상황에서 적용할 수 있는 것은 아니지만,

이렇듯, 알고리즘 설계를 지점/특정 조합 에서 구간 으로 시점을 전환하면,

정답을 탐색할 수 있는 방법이 간단해지는 등, 정답을 찾기 쉬워지는 경우가 있습니다.

책에서 제시한 예시를 보면서 설명을 보충해보겠습니다.

(https://algospot.com/judge/problem/read/DARPA)

시점을 지점 / 특정 조합 으로 제한한다면 ,

이 문제를 풀기 위해서는 n개의 카메라를 m개의 장소에 설치할 수 있는 모든 조합을 고려해야할 것 같은 느낌입니다.

당연히 실행시간이 많이 필요하겠죠. 가능한 조합의 수가 mCn이고, 각 조합 당 최소 간격을 구하기 위해 O(n)만큼의 시간이 필요할 것입니다.

따라서, 총 O(mCn * n ) 만큼의 실행시간이 필요할 것입니다.

알고리즘을 설계할때,
지점에 대해 대답하는 알고리즘 보다,
구간에 대해 대답하는 알고리즘을 설계하는 게 더 쉬울 수 있다.

예시)1~50사이의 숫자를 맞추는 것과 비슷

탐색하는 방법도 더 쉬워질 수 있다

x 또는 그보다 좋은 답이 있는가? 의 식으로 // 어떤 구간에 대한 질문으로 바꿀 수 있는가?


이 전략 / y/n로 답하게 하는 것의 장점

이렇게 간단하게 대답할 수 있게 하고, 타겟으로 하는 구간을 좁혀나가는 것

이 전략은 최적화 문제보다 어려울 수가 없다는 설명



책의 예제

- 지점의 관점으로 본다면

    주어진 카메라 설치 조합에서 가능한 최소 거리의 최대값을 구해야 한다
        (가능한 설치 조합을 다 실험해봐야 한다)

- 구간의 관점으로 본다면

    gap이상의 구간을 두면서 카메라를 설치할 수 있는지 확인해보기

    //이렇게 다른 알고리즘을 설계할 수도 있다