코딩테스트 한 문제를 여러 풀이로 접근하기 - 실무적 해석력 키우기

코딩테스트를 준비하면서 나는 처음에 모든 문제를 한 가지 방법으로만 풀려고 했다. 어떤 풀이가 정답인지 찾으면 거기서 끝이라고 생각했다. 하지만 실제로는 같은 문제를 여러 각도에서 해석하고 풀어보는 과정 속에서 내 실력이 부쩍 늘었다. 특히 면접 때 "다른 방식은 생각해봤나?"라는 질문을 받을 때 자신감 있게 답할 수 있었던 것도 이 습관 덕분이었다.

 

이번 글에서는 실제 코딩테스트에 자주 나오는 패턴의 문제를 예시로 들면서, 같은 문제를 어떻게 다양한 방식으로 접근할 수 있는지 그리고 왜 이렇게 공부하는 것이 효율적인지 공유하려고 한다. 나처럼 코딩테스트를 준비 중인 개발자들이 이 글을 읽고 자기만의 풀이 방법들을 만들어 나갈 수 있으면 좋겠다.

같은 문제, 왜 여러 번 풀어야 할까?

코딩테스트 준비를 할 때 많은 사람들이 범하는 실수 중 하나는 문제를 푼 후 그 문제를 끝냈다고 생각하는 것이다. 특히 처음 푼 풀이가 정답이 나오면 더욱 그렇다. 하지만 실제 회사의 면접이나 업무에서는 하나의 결과가 나오는 것만큼 그 과정이 중요하다.

 

내가 여러 풀이로 접근하는 것을 권장하는 이유는 몇 가지다. 첫째, 같은 문제를 다양한 각도에서 보는 경험은 문제 해결 능력 자체를 높인다. 브루트포스로 풀 수도 있고, 효율적인 알고리즘으로 풀 수도 있으며, 자료구조를 활용해 풀 수도 있다. 이런 식으로 다양한 접근을 해보면 나중에 비슷한 새로운 문제가 나왔을 때 더 빠르게 최적의 풀이를 찾을 수 있다.

 

둘째, 시간 복잡도와 공간 복잡도의 트레이드오프를 이해할 수 있다. 어떤 풀이는 시간이 적게 걸리지만 메모리를 많이 사용하고, 어떤 풀이는 그 반대다. 여러 풀이를 비교해보면 이런 차이를 몸으로 느낄 수 있다.

 

셋째, 면접에서 강점이 된다. 면접관들은 단순히 문제를 푸는 것뿐만 아니라, 그 과정에서 얼마나 깊이 있게 생각했는지를 본다. "이 방법 말고 다른 방법도 시도해봤나요?"라는 질문에 자신감 있게 여러 풀이를 설명할 수 있다면 정말 강한 인상을 남길 수 있다.

실제 예제: 부분합 문제로 여러 풀이 비교하기

이제 구체적으로 어떻게 다양한 풀이를 만들 수 있는지 보여주기 위해 실제 코딩테스트에 자주 나오는 "부분합" 문제를 가지고 설명하겠다.

 

문제: 길이 n인 정수 배열이 주어졌을 때, 특정 범위 [i, j]의 원소들의 합을 구하는 쿼리가 여러 개 들어온다. 각 쿼리에 대해 부분합을 빠르게 계산해야 한다.

 

예를 들어 배열이 [1, 2, 3, 4, 5]일 때, [1, 3] 범위의 합은 2 + 3 + 4 = 9가 되는 식이다.

 

풀이 1: 브루트포스 방식

가장 먼저 생각할 수 있는 방법은 쿼리가 들어올 때마다 해당 범위의 원소들을 모두 더하는 것이다.

public class RangeSum {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        
        // 쿼리: [1, 3] 범위의 합
        int result = bruteForce(arr, 1, 3);
        System.out.println("합: " + result); // 9
    }
    
    // 브루트포스: 매번 범위를 순회하며 합산
    static int bruteForce(int[] arr, int start, int end) {
        int sum = 0;
        for (int i = start; i <= end; i++) {
            sum += arr[i];
        }
        return sum;
    }
}

이 방법은 구현이 간단하지만, 쿼리마다 O(n) 시간이 걸린다. 만약 쿼리가 많다면 총 O(q × n) 시간이 소요된다 (q는 쿼리의 개수).

 

풀이 2: 누적합(Prefix Sum) 활용

두 번째 방법은 미리 누적합을 계산해두는 것이다. 이렇게 하면 각 쿼리를 O(1) 시간에 처리할 수 있다.

public class RangeSumWithPrefix {
    static class PrefixSum {
        int[] prefix;
        
        // 누적합 미리 계산
        PrefixSum(int[] arr) {
            prefix = new int[arr.length + 1];
            for (int i = 0; i < arr.length; i++) {
                prefix[i + 1] = prefix[i] + arr[i];
            }
        }
        
        // O(1)에 부분합 계산
        int query(int start, int end) {
            return prefix[end + 1] - prefix[start];
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        PrefixSum ps = new PrefixSum(arr);
        
        System.out.println("합: " + ps.query(1, 3)); // 9
    }
}

이 방법은 전처리에 O(n) 시간이 걸리지만, 이후 모든 쿼리를 O(1)에 처리한다. 따라서 총 시간은 O(n + q)다.

 

풀이 3: 세그먼트 트리

만약 배열의 원소가 자주 업데이트되는 경우라면 어떻게 할까? 이때는 세그먼트 트리를 사용할 수 있다.

public class SegmentTree {
    int[] tree;
    int n;
    
    // 세그먼트 트리 구성
    public SegmentTree(int[] arr) {
        n = arr.length;
        tree = new int[4 * n];
        build(arr, 0, 0, n - 1);
    }
    
    // 트리 구성 - O(n)
    void build(int[] arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            build(arr, 2 * node + 1, start, mid);
            build(arr, 2 * node + 2, mid + 1, end);
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }
    }
    
    // 범위 합 쿼리 - O(log n)
    public int query(int start, int end) {
        return query(0, 0, n - 1, start, end);
    }
    
    int query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) {
            return 0;
        }
        if (l <= start && end <= r) {
            return tree[node];
        }
        int mid = (start + end) / 2;
        return query(2 * node + 1, start, mid, l, r) +
               query(2 * node + 2, mid + 1, end, l, r);
    }
    
    // 원소 업데이트 - O(log n)
    public void update(int idx, int val) {
        update(0, 0, n - 1, idx, val);
    }
    
    void update(int node, int start, int end, int idx, int val) {
        if (start == end) {
            tree[node] = val;
        } else {
            int mid = (start + end) / 2;
            if (idx <= mid) {
                update(2 * node + 1, start, mid, idx, val);
            } else {
                update(2 * node + 2, mid + 1, end, idx, val);
            }
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }
    }
}

 

풀이 4: 펜윅 트리(Binary Indexed Tree)

또 다른 고급 자료구조는 펜윅 트리인데, 세그먼트 트리보다 구현이 간단하면서도 비슷한 성능을 낸다.

public class FenwickTree {
    int[] tree;
    int n;
    
    public FenwickTree(int[] arr) {
        n = arr.length;
        tree = new int[n + 1];
        for (int i = 0; i < n; i++) {
            updateTree(i, arr[i]);
        }
    }
    
    // 트리 업데이트 - O(log n)
    void updateTree(int idx, int val) {
        idx++; // 1-based indexing
        while (idx <= n) {
            tree[idx] += val;
            idx += idx & (-idx);
        }
    }
    
    // 누적합 조회 - O(log n)
    int prefixSum(int idx) {
        idx++; // 1-based indexing
        int sum = 0;
        while (idx > 0) {
            sum += tree[idx];
            idx -= idx & (-idx);
        }
        return sum;
    }
    
    // 범위 합 - O(log n)
    public int rangeSum(int start, int end) {
        if (start == 0) {
            return prefixSum(end);
        }
        return prefixSum(end) - prefixSum(start - 1);
    }
}

각 풀이의 특징과 선택 기준

브루트포스 방식은 구현이 쉽고 이해하기 간단하다. 데이터 크기가 작거나 쿼리가 적을 때 사용할 수 있다. 시간 복잡도는 O(q × n)이다.

 

누적합 방식은 가장 실용적이다. 데이터가 변하지 않는다면 이 방식이 최고의 선택이다. 시간 복잡도는 O(n + q), 공간 복잡도는 O(n)이다.

 

세그먼트 트리는 데이터 업데이트와 범위 쿼리가 모두 필요할 때 사용한다. 구현이 복잡하지만 O(log n)의 우수한 성능을 제공한다.

 

펜윅 트리도 비슷한 상황에서 사용되지만, 코드가 더 간결하고 이해하기 쉽다. 시간 복잡도는 세그먼트 트리와 동일하다.

여러 풀이로 공부하면서 얻는 실질적인 이점

내가 코딩테스트를 준비하면서 느낀 가장 큰 이점은 문제를 보는 시야가 넓어진다는 것이다. 처음에는 "이 문제는 이 알고리즘으로 풀어야 한다"는 고정관념이 있었다. 하지만 같은 문제를 여러 방식으로 풀어보니 그런 고정관념이 깨졌다.

 

예를 들어, 범위 합 문제는 누적합으로도, 세그먼트 트리로도, 펜윅 트리로도 풀 수 있다는 걸 알게 되면서, 이제 어떤 문제를 봐도 "이건 어느 알고리즘으로 적용할 수 있을까?"라고 유연하게 생각할 수 있게 됐다.

 

또한, 각 자료구조와 알고리즘의 장단점을 실제 코드로 경험해보니 이론을 깊이 있게 이해할 수 있었다. 예를 들어, 세그먼트 트리가 왜 O(log n)이 나오는지 코드를 짜면서 자연스럽게 이해했다.

여러 풀이로 공부하는 효율적인 방법

이제 어떻게 이런 공부를 할 수 있을지 구체적으로 조언해보겠다.

• 쉬운 문제부터 시작하라. 다양한 풀이를 시도하기 좋다.
• 자신의 풀이의 시간·공간 복잡도를 분석하라.
• 의도적으로 다른 접근 방식을 만들어보라.
• 각 풀이의 실행 속도를 비교해보라.
• 왜 효율 차이가 나는지 이론적으로 이해하라.

실전 팁: 면접에서 여러 풀이를 설명할 때

면접에서는 풀이를 순서 있게 설명하는 것이 중요하다.

1. 가장 직관적인 풀이를 먼저 설명하라.
2. 그 풀이의 한계를 짚어라.
3. 개선된 풀이를 제안하라.
4. 시간/공간 트레이드오프를 언급하라.

코딩테스트 준비는 많은 문제를 푸는 것도 중요하지만, 같은 문제를 깊이 있게 파고드는 것도 정말 중요하다. 내가 여러 풀이로 공부한 경험이 취업으로 이어졌고, 업무를 시작한 후에도 문제를 해결할 때 다양한 접근이 가능하다는 장점이 계속 도움이 되고 있다.

 

특히 코딩테스트를 준비하는 초반에는 "빨리 많은 문제를 풀어야 한다"는 생각에 급할 수 있다. 하지만 속도보다는 깊이를 먼저 확보하는 것이 장기적으로 더 효율적이다. 한 문제를 충분히 깊이 있게 공부하고 여러 풀이로 접근해본 경험이 쌓이면, 나중에는 새로운 문제도 빠르게 해결할 수 있게 된다.

 

다음에 문제를 풀 때는 첫 번째 풀이가 나온 후에도 "이걸 또 다른 방식으로 풀 수 있을까?"라고 스스로에게 물어보자. 그 작은 습관이 모여서 당신의 코딩 실력을 한 단계 업그레이드시킬 것이다.

 

완전탐색 vs 그리디 vs 백트래킹: 코딩테스트 알고리즘 완벽 가이드