점프와 순간 이동

https://school.programmers.co.kr/learn/courses/30/lessons/12980

프로그래머스

기록용으로 남긴다.

 

그리디로 풀어야 하는 문제다.

(말이 '그리디로 풀어야 한다'지 실제로 그렇게 하라 하면 바로 코드가 안 나온다.)

특이사항은 최적해를 찾기 위해 뒤에서 앞으로 간다는 점.

public class Solution {
    public int solution(int N) {
        int batteryUsage = 0;
        while (N > 0) {
            if (N % 2 == 0) {
                N /= 2;
            } else {
                N -= 1;
                batteryUsage += 1;
            }
        }
        return batteryUsage;
    }
}

와, 진짜 쉽지 않나? ㅠㅠ

아니, 근데 진짜 이런 식으로 하는 게 그리디의 다라고???

나는 별별 희한한 식으로 문제 푸는 걸 생각했는데 그렇게 꼴 필요도 없고 복잡한 자료 구조를 쓸 것도 없이 그냥 이런 방식으로 끝난다고?

 

그런데 나는 Gpt한테 백트래킹을 사용하라는 추천을 받았었다.

백트래킹은 그리디랑 상관이 없다.

이는 탐색 알고리즘의 하위 분야로 특히 완전 탐색 기법 중 하나다.

가능한 모든 해를 탐색하면서 조건에 맞지 않으면 되돌아가는 식으로 최적의 해를 찾는다.

 

위 문제를 백트래킹으로 풀면 어떻게 될까?

public class Solution {
    public int solution(int N) {
        return backtracking(N, 0);
    }

    private int backtracking(int position, int batteryUsage) {
        if (position == 0) {
            return batteryUsage;
        }
        if (position % 2 == 0) {
            return backtracking(position / 2, batteryUsage);
        } else {
            return backtracking(position - 1, batteryUsage + 1);
        }
    }
}

내가 이런 풀이를 보면 나는 이걸 백트래킹이라 생각하지 못 하고

'아, 그냥 재귀로 풀었구나'라고 생각할 것이다.

 

갈 길이 멀다라고 생각이 되면서도 이게 심각하게 받아들인다고 될 문제도 아니라고 느낀다.

 

위 백트래킹 솔루션은 그리 좋은 예제라고 생각이 안 되니 그냥 눈으로 한 번만 훑어도 무방하겠다.