애드혹 알고리즘 접근법에서 가장 먼저 막히는 순간은 코드를 짤 때가 아니라 어떤 방식으로 접근해야 할지 결정하는 순간입니다. 이번 글에서는 애드혹 문제를 처음 읽었을 때 그리디와 완전탐색 중 어느 쪽을 먼저 의심해야 하는지 정리해보겠습니다.
애드혹 문제는 왜 접근 방향이 먼저 중요할까
애드혹 문제는 구현은 쉬워 보이는데 규칙은 애매하고, 어떤 기준으로 선택해야 하는지가 흐린 경우가 많습니다. 그래서 애드혹 문제에서 중요한 것은 알고리즘 이름을 빨리 맞히는 것이 아니라 문제 구조를 먼저 읽는 것입니다.
가장 먼저 봐야 하는 것은 입력 크기다
문제를 읽을 때는 먼저 가능한 선택이 몇 개나 생기는지, 모든 경우를 다 보면 몇 번 계산해야 하는지, 입력 크기상 완전탐색이 가능한지를 확인해야 합니다. 입력 크기를 보면 이 문제가 다 봐도 되는 문제인지, 아니면 구조를 줄여야 하는 문제인지 먼저 가를 수 있습니다.
그리디를 먼저 의심해볼 수 있는 신호
- 선택 기준이 끝까지 단순하게 유지된다
- 지금 선택이 이후 구조를 크게 망가뜨리지 않는다
- 정렬하면 구조가 단순해진다
그리디가 통할 가능성이 있는 문제는 현재 최선 선택이 전체 답을 망치지 않는 구조인 경우가 많습니다.
코드 예시 1: 정렬 후 기준이 유지되면 그리디가 자연스럽다
여러 작업 시간이 주어졌을 때 전체 대기 시간을 최소화하려면 짧은 작업부터 처리하는 것이 자연스럽습니다. 정렬 후 규칙이 끝까지 유지되고, 현재 선택이 이후에도 같은 방향으로 좋은 영향을 주기 때문입니다.
fun minWaitingTime(times: List<Int>): Int {
val sorted = times.sorted()
var prefixSum = 0
var total = 0
for (time in sorted) {
prefixSum += time
total += prefixSum
}
return total
}이 코드가 보여주는 것은 단순합니다. 정렬 후 앞에서부터 처리하면 현재 선택이 이후 누적합에도 계속 좋은 영향을 준다는 점입니다.
완전탐색을 먼저 떠올려야 하는 신호
- 선택이 여러 갈래로 갈라지고 미래 영향이 크다
- 지금 좋아 보여도 나중에 틀릴 수 있다
- 입력 크기가 작다
이런 구조에서는 그리디보다 완전탐색이나 백트래킹을 먼저 의심하는 편이 더 안전합니다.
코드 예시 2: 현재 선택이 미래를 크게 바꾸면 완전탐색이 자연스럽다
숫자들을 순서대로 보면서 각 숫자를 더할지 말지를 결정해 어떤 목표 값을 만들 수 있는지 판단해야 한다고 해봅시다. 이 문제는 현재 선택이 이후 가능한 경우 전체를 바꿉니다.
fun canMakeTarget(nums: IntArray, index: Int, currentSum: Int, target: Int): Boolean {
if (index == nums.size) {
return currentSum == target
}
return canMakeTarget(nums, index + 1, currentSum + nums[index], target) ||
canMakeTarget(nums, index + 1, currentSum, target)
}이 코드에서 중요한 것은 현재 숫자를 선택하는 경우와 선택하지 않는 경우로 상태가 갈라진다는 점입니다. 이런 구조에서는 지금 당장 좋아 보이는 규칙보다 가능한 경우를 탐색하는 쪽이 더 자연스럽습니다.
겉보기엔 그리디 같지만 실제로는 위험한 경우
그럴듯한 규칙 하나를 잡고 바로 그리디로 가는 것은 입문자가 자주 하는 실수입니다. 예를 들어 항상 가장 큰 것부터 고르면 된다고 생각하기 쉽지만, 몇 개의 예제에서는 맞아 보여도 조금만 입력이 바뀌면 깨질 수 있습니다.
그래서 그리디를 떠올렸다면 항상 이 규칙이 항상 맞을까, 작은 반례를 만들 수 있을까를 같이 물어봐야 합니다. 반례를 못 버티는 그리디는 거의 항상 틀립니다.
이 다이어그램은 애드혹 문제를 읽었을 때 어떤 순서로 생각하면 좋은지 정리한 것입니다. 중요한 것은 그리디냐 완전탐색이냐를 감으로 찍는 것이 아니라, 질문 순서를 고정하는 것입니다.
실전에서 가장 중요한 질문: 지금 선택이 미래를 얼마나 바꾸는가
그리디와 완전탐색을 가를 때 가장 강력한 질문은 지금 선택이 미래를 얼마나 바꾸는가입니다. 현재 선택이 이후 구조를 거의 안 바꾸면 그리디가 잘 맞을 가능성이 크고, 현재 선택이 이후 구조 전체를 바꾼다면 완전탐색이 훨씬 자연스럽습니다.
실전 체크리스트
- 입력 크기가 작은가
- 선택 기준이 끝까지 유지되는가
- 지금 선택이 미래에 큰 영향을 주는가
- 정렬하면 구조가 단순해지는가
- 작은 반례를 바로 만들 수 있는가
이 체크리스트가 익숙해지면 문제를 읽고 바로 구현부터 들어가는 습관을 많이 줄일 수 있습니다.
마무리
애드혹 알고리즘 문제는 구현보다 먼저 접근 방향을 정하는 단계에서 많이 갈립니다. 그리디로 갈지, 완전탐색으로 갈지 판단할 때 중요한 것은 감이 아니라 기준입니다.
다음 글에서는 여기서 한 걸음 더 나아가 애드혹 알고리즘 반례 찾는 법을 이어서 다뤄보겠습니다. 관련해서는 브루트포스, DFS, 백트래킹 비교 글도 함께 참고할 수 있습니다.
