1. 오늘의 학습 키워드

백준 1654-랜선 자르기(파라메트릭 서치)

2. 공부한 내용 본인의 언어로 정리하기

• 파라메트릭 서치는 조건을 만족하는 최적해를 찾음.

• 접근법

1. 탐색 가능한 값의 최대값/최소값을 잘 정의할 것.
2. 결정 함수를 잘 만들 것.
3. 결국 이분 탐색의 한 종류이므로, 이분 탐색의 틀을 벗어나지 말 것.

• 결정함수의 매개변수는 최적해(최대화하려거나 최소화하려는 값)으로 할 것.

3. 오늘의 회고

3.1 어떤 문제가 있었고, 나는 어떤 시도를 했는지

• 처음 풀이에서 랜선을 'N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다'라는 조건을 놓쳤습니다.
• 결정함수를 통한 탐색 과정에서, 범위를 줄이는 것이 아닌 결정함수의 매개변수를 1씩 증가시켰습니다.

3.2 어떻게 해결했는지

• 이분 탐색 메서드를 수정했습니다.

//틀린 풀이
static long bs(){
        long l = 1;
        //shortest: 가장 짧은 랜선
        while(l <= shortest){
            if(!isValid(l)) l++;
            else{
                return --l;
            }
        }
        return 0;
    }

//정답 풀이
static long bs(){
        long l = 1, r = Arrays.stream(cable).max().getAsLong(), ret = 0;

        while(l <= r){
            long m = (l + r) / 2;
            if(isValid(m)){
                ret = m;
                l = m + 1;
            }else r = m - 1;
        }
        return ret;
    }

처음에는 길이 l을 1씩 늘려가는 선형 탐색을 했습니다. 이후에는 l의 범위를 한정하고, l의 범위 자체를 줄여가는 이분 탐색을 수행했습니다. 또한 결정함수에다가 범위의 최대/최소값의 산술평균인 m을 넘겼습니다.

3.3 무엇을 새롭게 알았는지

• 파라메트릭 서치도 결국 이분 탐색의 한 종류입니다. 찾는 값과 중앙값을 비교하는 부분이 결정함수로 바뀔 뿐입니다.
• 이분 탐색에서 그랬듯 탐색의 범위를 한정하고, 그 범위를 줄여나가는 것이 핵심입니다.

3.4 내일 학습할 것은 무엇인지

• 내일은 오늘 풀었던 문제를 다시 풀어볼 것입니다.
• 삼성 기출문제를 풀 예정입니다.