[알고리즘] 06. 알고리즘 문제 풀이 순서

[알고리즘] 06. 알고리즘 문제 풀이 순서

지난 글에서는 완전탐색이 필요한 상황에 대해 정리했습니다. 이번 글에서는 알고리즘 문제를 풀 때 어떤 순서로 접근하면 좋은지 알아보겠습니다.

알고리즘 문제를 처음 풀 때 가장 많이 하는 실수는 문제를 읽자마자 바로 코드를 작성하는 것입니다. 물론 쉬운 문제라면 바로 풀릴 수도 있지만, 조금만 조건이 복잡해져도 중간에 흐름이 꼬이기 쉽습니다.

알고리즘 문제 풀이는 코드를 먼저 쓰는 것이 아니라, 문제를 정리하는 것에서 시작됩니다.

---

1. 문제를 먼저 정확히 이해하기

알고리즘 문제를 풀 때 가장 먼저 해야 할 일은 문제를 정확히 이해하는 것입니다. 문제를 대충 읽고 바로 코드를 작성하면 조건을 놓치거나, 전혀 다른 방향으로 풀게 될 수 있습니다.

문제를 읽을 때는 아래 내용을 확인해야 합니다.

• 무엇을 구해야 하는가?
• 입력으로 어떤 값이 들어오는가?
• 출력해야 하는 값은 무엇인가?
• 조건이나 제한 사항은 무엇인가?
• 예외 상황이 있는가?

특히 최종적으로 구해야 하는 값을 정확히 잡는 것이 중요합니다. 문제의 목표가 흐릿하면 코드도 자연스럽게 복잡해집니다.

문제를 잘못 이해하면, 코드를 아무리 잘 작성해도 정답이 될 수 없습니다.

---

2. 입력값과 출력값 확인하기

문제를 이해했다면 다음으로 입력값과 출력값을 확인해야 합니다. 알고리즘 문제는 대부분 정해진 입력을 받아 정해진 형식으로 출력해야 합니다.

예를 들어 다음과 같은 문제가 있다고 생각해보겠습니다.

N개의 숫자가 주어졌을 때, 그 합을 출력하라.

이 문제에서 확인해야 할 것은 다음과 같습니다.

구분	내용
입력	숫자의 개수 N, N개의 숫자
처리	N개의 숫자를 모두 더함
출력	합계

이렇게 입력, 처리, 출력을 나누면 문제의 구조가 훨씬 선명해집니다.

입력 → 처리 → 출력

알고리즘 문제는 결국 이 흐름을 코드로 옮기는 과정입니다.

---

3. 제한 조건 확인하기

입력과 출력을 확인했다면 반드시 제한 조건을 봐야 합니다. 제한 조건은 어떤 알고리즘을 사용할 수 있는지 알려주는 힌트입니다.

예를 들어 N의 범위가 아래처럼 다를 수 있습니다.

제한 조건	생각해볼 풀이
N ≤ 100	완전탐색, 이중 반복문 가능성 있음
N ≤ 100,000	O(N²)은 위험, O(N log N) 또는 O(N) 고려
N ≤ 1,000,000	O(N) 중심으로 생각
N이 매우 큼	O(log N), O(1), 수학적 규칙 고려

같은 문제처럼 보여도 입력 크기에 따라 풀이 방식은 달라질 수 있습니다. 그래서 제한 조건을 보지 않고 코드를 작성하는 것은 위험합니다.

제한 조건은 문제 안에 숨어 있는 풀이 방향표입니다.

---

4. 예제 데이터를 손으로 계산해보기

문제에 주어진 예제 입력과 예제 출력은 그냥 확인용이 아닙니다. 풀이 흐름을 이해하는 데 중요한 단서입니다.

예를 들어 다음 문제가 있다고 하겠습니다.

배열에서 가장 큰 값을 출력하라.

입력이 아래와 같다면,

5
3 7 2 9 4

직접 손으로 계산해보면 다음과 같습니다.

1. 처음 값을 3으로 잡는다.
2. 7은 3보다 크므로 최댓값을 7로 바꾼다.
3. 2는 7보다 작으므로 그대로 둔다.
4. 9는 7보다 크므로 최댓값을 9로 바꾼다.
5. 4는 9보다 작으므로 그대로 둔다.

따라서 출력은 9가 됩니다.

9

이렇게 손으로 먼저 계산해보면 코드로 옮길 때 필요한 변수와 조건이 자연스럽게 보입니다.

---

5. 필요한 변수 정리하기

바로 코드를 작성하기 전에 어떤 변수가 필요한지 생각해보는 것이 좋습니다. 변수를 먼저 정리하면 코드가 훨씬 덜 흔들립니다.

예를 들어 배열에서 최댓값을 구하는 문제라면 아래 변수가 필요합니다.

변수	역할
arr	입력받은 숫자 배열
max	현재까지 찾은 최댓값
i	배열을 순회하는 인덱스

변수의 역할을 명확히 정하면 코드 안에서 값이 왜 바뀌는지 이해하기 쉬워집니다.

좋은 변수는 코드를 짧게 만드는 것보다, 흐름을 이해하기 쉽게 만드는 데 도움이 됩니다.

---

6. 처리 순서를 글로 적어보기

알고리즘을 코드로 쓰기 전에 먼저 사람 말로 순서를 적어보면 좋습니다. 이 과정을 의사코드라고 부르기도 합니다.

배열에서 최댓값을 구하는 문제를 글로 적으면 다음과 같습니다.

1. 배열의 첫 번째 값을 max로 저장한다.
2. 배열을 처음부터 끝까지 확인한다.
3. 현재 값이 max보다 크면 max를 갱신한다.
4. 반복이 끝나면 max를 출력한다.

이 순서가 잡히면 Java 코드로 옮기는 것은 훨씬 쉬워집니다.

int[] arr = {3, 7, 2, 9, 4};

int max = arr[0];

for (int i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
        max = arr[i];
    }
}

System.out.println(max);

코드는 결국 생각한 처리 순서를 프로그래밍 언어로 옮긴 것입니다. 문제가 어려울수록 이 단계가 중요해집니다.

---

7. 시간복잡도 확인하기

코드를 작성했다면 시간복잡도를 확인해야 합니다. 특히 반복문이 몇 번 도는지 살펴보는 것이 중요합니다.

for (int i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
        max = arr[i];
    }
}

위 코드는 배열을 한 번 순회합니다. 배열의 길이를 N이라고 하면 시간복잡도는 O(N)입니다.

만약 문제의 N이 100,000이라면 O(N)은 대체로 괜찮은 편입니다. 하지만 이중 반복문으로 O(N²)이 된다면 위험할 수 있습니다.

그래서 코드를 작성한 뒤에는 반드시 입력 제한과 시간복잡도가 맞는지 다시 확인해야 합니다.

---

8. 예외 케이스 확인하기

알고리즘 문제에서 예제 입력만 맞았다고 끝이 아닙니다. 예제는 일부 상황만 보여줄 뿐이고, 실제 채점에는 다양한 테스트 케이스가 들어갑니다.

아래와 같은 예외 케이스를 확인해야 합니다.

• 입력값이 가장 작은 경우
• 입력값이 가장 큰 경우
• 모든 값이 같은 경우
• 정답이 없는 경우
• 음수가 포함된 경우
• 중복 값이 있는 경우
• 배열의 첫 번째나 마지막에 정답이 있는 경우

예를 들어 최댓값을 구하는 문제에서 모든 값이 음수일 수도 있습니다. 이때 max를 0으로 시작하면 잘못된 결과가 나올 수 있습니다.

int[] arr = {-5, -2, -9, -1};

int max = 0; // 잘못된 초기값

for (int i = 0; i < arr.length; i++) {
    if (arr[i] > max) {
        max = arr[i];
    }
}

System.out.println(max);

위 코드는 배열 안에 0이 없는데도 0을 출력할 수 있습니다. 따라서 최댓값 문제에서는 보통 배열의 첫 번째 값을 초기값으로 잡는 것이 안전합니다.

int[] arr = {-5, -2, -9, -1};

int max = arr[0];

for (int i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
        max = arr[i];
    }
}

System.out.println(max);

이처럼 예외 케이스를 확인하면 숨은 오류를 줄일 수 있습니다.

---

9. 알고리즘 문제 풀이 순서 정리

알고리즘 문제를 풀 때는 아래 순서로 접근하면 좋습니다.

1. 문제를 끝까지 읽는다.
2. 무엇을 구해야 하는지 확인한다.
3. 입력값과 출력값을 정리한다.
4. 제한 조건을 확인한다.
5. 예제 데이터를 손으로 계산해본다.
6. 필요한 변수와 자료구조를 정리한다.
7. 처리 순서를 글로 적는다.
8. 코드로 옮긴다.
9. 시간복잡도와 공간복잡도를 확인한다.
10. 예외 케이스를 검증한다.

처음에는 이 과정이 느리게 느껴질 수 있습니다. 하지만 문제를 대충 풀다가 계속 틀리는 것보다, 처음부터 차근차근 정리하는 편이 훨씬 안정적입니다.

알고리즘 실력은 코드를 빨리 치는 능력보다, 문제를 정확히 정리하는 능력에서 시작됩니다.

---

10. 정리

이번 글에서는 알고리즘 문제 풀이 순서를 정리했습니다.

• 문제를 읽자마자 코드를 작성하면 조건을 놓치기 쉽다.
• 입력, 처리, 출력을 먼저 구분해야 한다.
• 제한 조건을 보면 가능한 알고리즘을 판단할 수 있다.
• 예제 데이터를 손으로 계산하면 풀이 흐름이 잘 보인다.
• 처리 순서를 글로 적은 뒤 코드로 옮기면 실수를 줄일 수 있다.
• 예외 케이스까지 확인해야 안정적인 풀이가 된다.

알고리즘 문제를 잘 풀기 위해서는 어려운 기법을 많이 외우는 것보다, 문제를 읽고 정리하는 습관을 먼저 만드는 것이 중요합니다.

좋은 풀이는 빠른 손보다 정확한 정리에서 시작됩니다.

---

다음 글 예고

다음 글부터는 본격적으로 기초 구현 영역으로 들어갑니다. 다음 글에서는 배열과 인덱스 처리에 대해 정리해보겠습니다.

배열은 알고리즘 문제에서 가장 자주 등장하는 기본 자료구조입니다. 인덱스 범위, 반복문, 최댓값과 최솟값 처리까지 차근차근 살펴보겠습니다.