[알고리즘] 04. 입력 크기별 알고리즘 선택법

[알고리즘] 04. 입력 크기별 알고리즘 선택법

지난 글에서는 공간복잡도에 대해 정리했습니다. 이번 글에서는 알고리즘 문제를 풀 때 매우 중요한 기준인 입력 크기별 알고리즘 선택법에 대해 알아보겠습니다.

알고리즘 문제를 풀다 보면 같은 문제처럼 보여도 입력 크기에 따라 전혀 다른 풀이가 필요할 때가 있습니다. 입력 개수가 작으면 단순 반복문으로도 충분하지만, 입력 개수가 커지면 더 효율적인 방법을 사용해야 합니다.

입력 크기는 어떤 알고리즘을 사용할 수 있는지 판단하는 가장 중요한 힌트입니다.

---

1. 왜 입력 크기를 먼저 봐야 할까요?

알고리즘 문제를 풀 때 많은 사람이 문제 설명부터 읽고 바로 코드를 작성하려고 합니다. 하지만 실제로는 입력 제한을 먼저 확인하는 습관이 중요합니다.

입력 제한을 보면 어떤 풀이가 가능한지 어느 정도 예상할 수 있습니다. 예를 들어 N이 100인 문제와 N이 1,000,000인 문제는 사용할 수 있는 알고리즘이 달라집니다.

• N이 작으면 완전탐색도 가능할 수 있다.
• N이 크면 중첩 반복문은 위험할 수 있다.
• N이 매우 크면 O(N) 또는 O(log N) 수준의 풀이가 필요할 수 있다.

즉 입력 크기는 단순한 숫자가 아니라, 풀이 방향을 정하는 기준입니다.

---

2. 입력 크기와 시간복잡도의 관계

시간복잡도는 입력 크기 N이 커질 때 연산 횟수가 얼마나 증가하는지를 나타냅니다. 따라서 입력 크기가 커질수록 더 효율적인 알고리즘이 필요합니다.

입력 크기	가능한 시간복잡도	대표 풀이
N ≤ 10	O(N!), O(2ⁿ)	순열, 조합, 백트래킹
N ≤ 100	O(N³)	삼중 반복문, 플로이드 워셜
N ≤ 1,000	O(N²)	이중 반복문, 완전탐색
N ≤ 100,000	O(N log N), O(N)	정렬, 투 포인터, 해시
N ≤ 1,000,000	O(N)	단일 반복문, 누적합
N이 매우 큼	O(log N), O(1)	이분 탐색, 수학 공식

이 표는 절대적인 기준은 아니지만, 문제를 풀 때 빠르게 방향을 잡는 데 도움이 됩니다.

입력 크기가 커질수록 단순한 완전탐색보다 정렬, 해시, 이분 탐색, 누적합 같은 기법을 고려해야 합니다.

---

3. N이 작은 경우 — 완전탐색 가능

입력 크기가 작다면 모든 경우를 직접 확인하는 완전탐색을 사용할 수 있습니다.

예를 들어 N이 100 정도라면 이중 반복문을 사용해도 보통 큰 문제가 되지 않습니다.

int[] arr = {3, 1, 4, 2, 5};
int target = 6;

for (int i = 0; i < arr.length; i++) {
    for (int j = i + 1; j < arr.length; j++) {
        if (arr[i] + arr[j] == target) {
            System.out.println(arr[i] + ", " + arr[j]);
        }
    }
}

위 코드는 모든 두 수의 조합을 확인합니다. 배열 길이가 작다면 충분히 사용할 수 있는 방식입니다.

하지만 N이 100,000이라면 이중 반복문은 매우 많은 연산을 하게 됩니다. 그래서 입력 크기가 커지면 다른 방법을 찾아야 합니다.

---

4. N이 1,000 정도라면 O(N²)을 조심해서 사용

N이 1,000 정도라면 O(N²) 알고리즘이 가능한 경우가 많습니다. N²은 약 1,000,000번 정도의 연산이기 때문입니다.

N	N²
100	10,000
1,000	1,000,000
10,000	100,000,000
100,000	10,000,000,000

문제는 N이 10,000을 넘어가면서부터입니다. O(N²)은 순식간에 연산 횟수가 커지기 때문에 시간 초과가 발생할 가능성이 높아집니다.

그래서 N이 10,000 이상이라면 이중 반복문을 사용하기 전에 한 번 더 의심해보는 것이 좋습니다.

---

5. N이 100,000 이상인 경우

N이 100,000 이상이라면 일반적으로 O(N²) 풀이는 어렵다고 보는 것이 좋습니다. 이때는 보통 O(N log N) 또는 O(N) 풀이를 생각해야 합니다.

자주 사용하는 방법은 다음과 같습니다.

• 정렬
• 해시맵
• 해시셋
• 투 포인터
• 슬라이딩 윈도우
• 누적합
• 이분 탐색

예를 들어 특정 숫자가 존재하는지 여러 번 확인해야 한다면, 배열을 매번 처음부터 끝까지 탐색하는 것보다 해시셋을 사용하는 방식이 더 효율적일 수 있습니다.

import java.util.HashSet;

HashSet<Integer> set = new HashSet<>();

set.add(10);
set.add(20);
set.add(30);

System.out.println(set.contains(20));

HashSet을 사용하면 특정 값이 있는지 빠르게 확인할 수 있습니다. 입력 크기가 클수록 이런 자료구조 선택이 중요해집니다.

---

6. N이 매우 큰 경우 — 규칙을 찾아야 합니다

N이 1,000,000보다 훨씬 크거나, 1,000,000,000처럼 매우 큰 경우에는 단순 반복문도 부담이 될 수 있습니다. 이때는 반복을 줄이거나 수학적인 규칙을 찾아야 합니다.

예를 들어 1부터 N까지의 합을 구하는 문제를 생각해보겠습니다.

반복문으로 구하면 O(N)입니다.

long sum = 0;

for (int i = 1; i <= n; i++) {
    sum += i;
}

하지만 공식으로 구하면 O(1)입니다.

long sum = (long) n * (n + 1) / 2;

결과는 같지만 실행 방식은 완전히 다릅니다. 입력 크기가 매우 클 때는 이렇게 반복을 줄이는 방법을 고민해야 합니다.

N이 너무 크다면 모든 값을 직접 확인하는 방식이 아니라, 규칙이나 공식이 있는지 먼저 살펴봐야 합니다.

---

7. 제한 시간이 1초라면 어느 정도까지 가능할까요?

알고리즘 문제에서는 보통 제한 시간이 주어집니다. 언어와 환경마다 차이가 있지만, Java 기준으로는 1초에 대략 수천만 번 정도의 연산을 기준으로 생각하는 경우가 많습니다.

정확한 숫자를 외우기보다, 아래처럼 감을 잡는 것이 좋습니다.

연산 횟수	느낌
1,000	매우 여유 있음
1,000,000	대체로 가능
100,000,000	위험할 수 있음
10,000,000,000	대부분 시간 초과

그래서 문제를 풀 때는 내가 작성한 코드가 대략 몇 번 정도 반복될지 계산해보는 습관이 필요합니다.

---

8. 입력 크기별 판단 예시

다음과 같은 문제가 있다고 가정해보겠습니다.

N개의 숫자가 주어졌을 때, 두 수의 합이 특정 값이 되는 쌍이 있는지 확인하라.

만약 N이 100이라면 이중 반복문으로 모든 쌍을 확인해도 괜찮을 수 있습니다.

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        if (arr[i] + arr[j] == target) {
            System.out.println("찾음");
        }
    }
}

하지만 N이 100,000이라면 이 방식은 위험합니다. 이때는 정렬 후 투 포인터를 사용하거나, HashSet을 이용하는 방식이 더 적합합니다.

HashSet<Integer> set = new HashSet<>();

for (int num : arr) {
    int need = target - num;

    if (set.contains(need)) {
        System.out.println("찾음");
        break;
    }

    set.add(num);
}

이처럼 같은 문제라도 입력 크기에 따라 풀이 방식이 달라질 수 있습니다.

---

9. 문제를 풀기 전 확인할 것

알고리즘 문제를 풀기 전에는 아래 순서로 확인하면 좋습니다.

1. 입력 크기 N의 최댓값을 확인한다.
2. 제한 시간을 확인한다.
3. O(N²)이 가능한지 먼저 판단한다.
4. 불가능하다면 O(N log N), O(N), O(log N) 풀이를 생각한다.
5. 메모리 제한도 함께 확인한다.
6. 예제뿐 아니라 최악의 입력도 생각한다.

이 습관이 잡히면 문제를 보고 무작정 코드를 작성하는 일이 줄어듭니다. 그리고 시간 초과가 나는 이유도 더 빨리 찾을 수 있습니다.

---

10. 정리

이번 글에서는 입력 크기별 알고리즘 선택법을 정리했습니다.

• 입력 크기는 풀이 방향을 정하는 중요한 기준이다.
• N이 작으면 완전탐색도 가능할 수 있다.
• N이 커질수록 O(N²) 풀이는 위험해진다.
• N이 100,000 이상이면 O(N log N) 또는 O(N) 풀이를 먼저 생각해야 한다.
• N이 매우 크면 반복보다 규칙, 공식, 이분 탐색을 고려해야 한다.
• 문제를 풀기 전 입력 제한과 시간 제한을 반드시 확인해야 한다.

알고리즘 문제에서 입력 크기를 보는 습관은 정말 중요합니다. 코드를 잘 짜는 것도 중요하지만, 애초에 가능한 풀이인지 판단하는 능력이 먼저 필요합니다.

좋은 풀이는 문제를 읽고 바로 코드를 쓰는 것이 아니라, 입력 크기를 보고 가능한 방법을 고르는 것에서 시작됩니다.

---

다음 글 예고

다음 글에서는 완전탐색이 필요한 상황에 대해 알아보겠습니다.

모든 경우를 확인하는 완전탐색이 언제 필요한지, 그리고 언제 위험한지 예제로 정리해보겠습니다.