실전 문제 해결 루틴 만들기

왜 루틴이 필요한가

알고리즘을 하나씩 배웠는데도 실제 문제 앞에서 막히는 경우가 많다. 이유는 지식이 부족해서만은 아니다. 문제를 읽고, 어떤 풀이를 떠올리고, 구현하고, 틀린 부분을 찾는 순서가 아직 정리되지 않았기 때문이다.

실전에서는 좋은 알고리즘을 많이 아는 것보다 먼저 해야 할 일이 있다. 문제를 차분히 분해하는 것이다. 입력은 무엇인지, 출력은 무엇인지, 입력 크기는 얼마나 되는지, 어떤 예외가 있는지 확인해야 한다. 그다음 가능한 풀이를 떠올리고, 제한 시간 안에 되는지 판단한다.

이 장의 목표는 하나다. 문제를 만났을 때 매번 같은 순서로 생각하는 루틴을 만드는 것이다. 루틴이 있으면 어려운 문제도 덜 막막하다. 지금 당장 답이 보이지 않아도 어디부터 확인해야 하는지 알 수 있다.

AI 생성 이미지

1단계: 문제를 입력, 출력, 조건으로 나눈다

문제를 읽자마자 코드를 쓰면 놓치는 조건이 생기기 쉽다. 먼저 다음 네 가지를 따로 적어 보자.

• 입력: 어떤 값이 주어지는가?

• 출력: 최종적으로 무엇을 구해야 하는가?

• 제한: 입력 크기와 제한 시간은 얼마인가?

• 예외: 빈 데이터, 중복, 최솟값, 최댓값이 가능한가?

예를 들어 다음과 같은 문제가 있다고 하자.

정수 배열 arr과 목표값 target이 주어진다. 서로 다른 두 원소의 합이 target이 되는 쌍이 있으면 true, 없으면 false를 출력하라.

이 문제를 바로 코드로 쓰기 전에 이렇게 나눌 수 있다.

• 입력: 정수 배열 arr, 정수 target

• 출력: 조건을 만족하는 두 원소가 있으면 true, 아니면 false

• 조건: 같은 원소를 두 번 쓰면 안 된다

• 확인할 예외: 배열 길이가 0 또는 1인 경우, 중복 값이 있는 경우, 음수가 있는 경우

이렇게 정리하면 풀이 방향이 더 분명해진다. 문제의 핵심은 "두 수의 합"이고, 같은 원소를 두 번 쓰지 않아야 하며, 여러 쌍을 모두 출력하는 것이 아니라 존재 여부만 판단하면 된다.

2단계: 입력 크기로 가능한 시간 복잡도를 추정한다

실전 문제에서는 입력 크기가 중요한 힌트다. n이 작으면 완전 탐색도 가능하지만, n이 크면 더 빠른 방법을 찾아야 한다.

정확한 기준은 언어, 제한 시간, 실행 환경, 입출력 방식에 따라 달라진다. 그래도 처음에는 다음처럼 거칠게 판단해도 충분하다.

이 표는 절대적인 규칙이 아니라 출발점이다. 예를 들어 n = 100,000인데 모든 두 수의 쌍을 비교하면 O(n²)이다. 실제 쌍의 개수는 대략 50억 개에 이르므로 현실적으로 어렵다. 이때는 해시, 정렬, 이진 탐색 같은 도구를 떠올려야 한다.

반대로 n = 15이고 가능한 선택 조합을 모두 검사해야 한다면 백트래킹이 맞을 수 있다. 입력이 작기 때문에 모든 경우를 보면서 조건에 맞지 않는 길을 가지치기하는 전략이 가능하다.

중요한 점은 복잡도를 완벽하게 계산하는 것이 아니다. "이 풀이가 제한 시간 안에 될 가능성이 있는가?"를 먼저 걸러내는 것이다.

3단계: 완전 탐색에서 시작해 개선한다

처음부터 가장 빠른 풀이를 떠올리려고 하면 오히려 생각이 막힌다. 먼저 완전 탐색으로 정확한 풀이를 만들어 보자. 완전 탐색은 느릴 수 있지만 문제의 구조를 이해하는 데 매우 좋다.

두 수의 합 문제라면 완전 탐색은 다음과 같다.

for i from 0 to n - 1:
    for j from i + 1 to n - 1:
        if arr[i] + arr[j] == target:
            return true
return false

이 풀이는 모든 두 원소의 쌍을 확인하므로 O(n²)이다. n이 작으면 충분하지만, n이 크면 개선해야 한다.

개선할 때는 다음 질문을 던진다.

• 같은 값을 반복해서 찾고 있는가? → 해시, 집합, 딕셔너리

• 데이터가 정렬되어 있거나 정렬하면 규칙이 생기는가? → 정렬, 이진 탐색

• 후보 범위를 절반씩 줄일 수 있는가? → 이진 탐색

• 현재 선택이 항상 안전한가? → 그리디

• 같은 작은 문제가 반복되는가? → 동적 계획법

• 가능한 선택을 만들어야 하지만 중간에 버릴 수 있는가? → 백트래킹

• 대상들이 연결 관계를 이루는가? → 그래프 탐색 DFS, BFS

두 수의 합 문제에서는 "필요한 값이 이전에 나왔는지"를 계속 찾는다. 반복 조회가 핵심이므로 집합을 사용할 수 있다.

seen = empty set

for x in arr:
    need = target - x
    if need in seen:
        return true
    add x to seen

return false

이제 각 원소를 한 번씩 보면서 집합에서 필요한 값을 찾는다. 평균적으로 O(n)에 가깝다. 완전 탐색에서 출발했기 때문에 개선 이유도 분명하다. "모든 쌍을 직접 만들지 말고, 이미 본 값 중 필요한 값만 빠르게 찾자"가 핵심이다.

4단계: 구현 전에 의사코드를 쓴다

풀이가 떠올랐다고 바로 코드를 쓰면 변수 이름, 반복 범위, 종료 조건에서 실수하기 쉽다. 짧게라도 의사코드를 먼저 쓰자.

의사코드는 프로그램 언어 문법보다 절차를 정리하는 데 목적이 있다. 다음 순서로 쓰면 좋다.

1. 필요한 자료구조를 만든다.

2. 입력을 어떤 순서로 볼지 정한다.

3. 각 단계에서 검사할 조건을 적는다.

4. 답을 갱신하거나 반환하는 시점을 정한다.

5. 반복이 끝난 뒤 기본 답을 정한다.

예를 들어 BFS 문제라면 의사코드는 이렇게 정리할 수 있다.

queue에 시작 정점을 넣는다
시작 정점을 방문 처리한다

while queue is not empty:
    현재 정점을 꺼낸다
    for 다음 정점 in 현재 정점의 이웃:
        if 아직 방문하지 않았다:
            방문 처리한다
            거리 값을 갱신한다
            queue에 넣는다

이 정도만 적어도 구현 실수가 줄어든다. 특히 재귀, 백트래킹, DP, 그래프 탐색은 코드가 길어지기 쉬우므로 의사코드가 더 중요하다.

5단계: 예제보다 강한 테스트를 직접 만든다

문제에 있는 예제 입력은 기본 확인용이다. 예제만 통과했다고 해서 맞았다고 볼 수 없다. 직접 반례를 만들어야 한다.

반례는 거창한 것이 아니다. 다음 경우를 습관처럼 확인하면 된다.

• 최소 입력: 배열 길이가 0, 1인 경우

• 최대 입력: 입력이 가장 클 때 시간 안에 가능한지

• 중복: 같은 값이 여러 번 나오는 경우

• 경계값: 인덱스가 처음이나 마지막에 걸리는 경우

• 빈 데이터: 문자열이 비었거나 리스트가 비어 있는 경우

• 정렬 상태: 이미 정렬됨, 거꾸로 정렬됨, 모두 같은 값

• 불가능한 경우: 답이 존재하지 않는 입력

두 수의 합 문제라면 다음 테스트를 생각할 수 있다.

arr = [], target = 10        -> false
arr = [5], target = 10       -> false
arr = [5, 5], target = 10    -> true
arr = [1, 2, 3], target = 7  -> false
arr = [-1, 4, 6], target = 3 -> true

특히 [5]와 [5, 5]의 차이를 봐야 한다. 같은 원소를 두 번 쓰면 안 되므로 [5]는 false다. 하지만 원소가 두 개 있는 [5, 5]는 서로 다른 위치의 두 값을 쓰므로 true다.

6단계: 디버깅은 작은 입력부터 한다

코드가 틀렸을 때 가장 나쁜 방법은 큰 입력을 그대로 바라보는 것이다. 큰 입력에서는 어디서 잘못됐는지 찾기 어렵다. 먼저 손으로 계산할 수 있는 작은 입력을 만든다.

디버깅 순서는 다음처럼 잡으면 좋다.

1. 가장 작은 입력에서 실행한다.

2. 반복문이 몇 번 도는지 확인한다.

3. 핵심 변수의 값을 출력한다.

4. 예상한 값과 실제 값을 비교한다.

5. 한 줄을 고친 뒤 다시 같은 입력으로 확인한다.

예를 들어 이진 탐색이 틀렸다면 left, right, mid를 출력한다.

while left <= right:
    mid = (left + right) // 2
    print(left, mid, right)

    if arr[mid] == target:
        return mid
    else if arr[mid] < target:
        left = mid + 1
    else:
        right = mid - 1

백트래킹이 틀렸다면 현재 선택 목록과 재귀 깊이를 출력한다. DP가 틀렸다면 dp 배열이 한 칸씩 어떻게 채워지는지 확인한다. 그래프 탐색이 틀렸다면 방문 처리 시점과 큐에 들어가는 값을 본다.

출력은 많이 하는 것보다 핵심 변수를 고르는 것이 중요하다. "답을 결정하는 변수"와 "반복 범위를 바꾸는 변수"를 먼저 확인하자.

실전 문제 해결 체크리스트

문제를 풀 때마다 다음 순서를 반복하자.

1. 입력과 출력을 한 문장으로 정리한다.
2. 제한에서 입력 크기 n을 찾는다.
3. 가능한 시간 복잡도를 추정한다.
4. 완전 탐색 풀이를 먼저 생각한다.
5. 느리다면 어떤 중복을 줄일지 찾는다.
6. 알맞은 도구를 고른다.
   - 빠른 존재 확인: 집합, 딕셔너리
   - 정렬 후 규칙 활용: 정렬, 이진 탐색
   - 연결 관계 탐색: DFS, BFS
   - 반복되는 작은 문제: DP
   - 가능한 선택 탐색: 백트래킹
   - 매번 최선 선택: 그리디 검증
7. 의사코드를 쓴다.
8. 구현한다.
9. 최소 입력, 최대 입력, 중복, 불가능한 경우를 테스트한다.
10. 틀리면 작은 입력에서 변수 상태를 확인한다.

이 체크리스트는 문제를 대신 풀어 주지는 않는다. 하지만 막혔을 때 돌아갈 길을 만들어 준다. 알고리즘 실력은 한 번에 생기지 않는다. 문제를 읽는 방식, 풀이를 개선하는 방식, 틀린 코드를 점검하는 방식이 반복되면서 조금씩 쌓인다.

자주 틀리는 부분

가장 흔한 실수는 입력 크기를 보지 않고 익숙한 풀이부터 쓰는 것이다. O(n²) 풀이가 직관적이어도 n이 100,000이면 다른 방법을 찾아야 한다.

두 번째는 예제만 믿는 것이다. 예제는 보통 기본 흐름을 보여 줄 뿐이다. 최소 입력, 중복 입력, 답이 없는 입력을 직접 만들어야 한다.

세 번째는 알고리즘 이름만 보고 억지로 끼워 맞추는 것이다. "DP 문제처럼 보인다"보다 "같은 작은 문제가 반복되는가?"가 먼저다. "그리디로 풀고 싶다"보다 "지금 선택이 나중에도 안전한가?"를 확인해야 한다.

네 번째는 디버깅을 감으로 하는 것이다. 틀린 이유를 머릿속으로만 추측하지 말고, 작은 입력에서 변수 값을 확인하자. 알고리즘 문제의 오류는 대부분 반복 범위, 초기값, 방문 처리, 상태 복구, 경계 조건에서 나온다.

마지막으로, 한 번에 완벽한 풀이를 쓰려고 하지 말자. 먼저 정확한 느린 풀이를 생각하고, 그 풀이에서 낭비되는 부분을 찾고, 배운 도구로 줄여 나가면 된다. 이것이 실전에서 가장 안정적인 문제 해결 루틴이다.