알고리즘 공부 정리

문제를 풀면서 "시간초과를 피하는 사고방식"이 필요하다고 느껴

알고리즘 공부 로드맵 + 해야 할 것들을 정리해 보는 시간을 가져보고자 합니다 !

 

우선 간단한 문제 예시를 살펴보면서 알고리즘 공부법의 중요성을 알아보겠습니다.

https://www.acmicpc.net/problem/13458

 

해당 문제를 가장 처음에는 다음과 같은 코드로 작성했습니다.

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int[] arr = new int[N];
    for(int i = 0; i < N; i++) {
      arr[i] = sc.nextInt();
    }

    int B = sc.nextInt();
    int C = sc.nextInt();

    int result = 0;
    for (int i = 0; i < N; i++) {
      // 총감독관 
      arr[i] = arr[i] - B; 
      result++;
      
      // 부감독관
      if(arr[i] > 0) {
        while(true) {
          if(arr[i] <= 0) {
            break;  
          }
          arr[i] = arr[i] - C;
          result++;
        }
      }
    }
    System.out.println(result);    
  }
}

 

• 한 시험장 반복 횟수 ≈ ⌈max(0, Ai − B)/C⌉
• 최악(N=10^6, Ai=10^6, B=1, C=1) 일 때 전체 반복 ≈ 10^12회 → 사실상 시간초과

 

 

그다음에는 시간복잡도를 고려해 다음 코드를 작성했습니다.

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int[] arr = new int[N];
    for(int i = 0; i < N; i++) {
      arr[i] = sc.nextInt();
    }

    int B = sc.nextInt();
    int C = sc.nextInt();

    int result = 0;
    for (int i = 0; i < N; i++) {
      // 총감독관 
      arr[i] = arr[i] - B; 
      result++;

      // 부감독관
      if(arr[i] > 0) {
        int add = 0;
        if( arr[i] % C !=0 ) {
          add = arr[i] / C + 1;
        } else {
          add = arr[i] / C;
        }
        result += add;
      }
    }
    System.out.println(result); 
  }
}

 

• 남은 학생 수 / C → 필요한 부감독관 수를 한 번에 계산
• 시간복잡도: O(N), 충분히 통과 가능

 

 

분명 답은 다 맞았다고 생각했는데, 왜 틀렸나 살펴보니 result 변수의 오버플로우 문제를 발견했습니다.

 

• 총 감독관 수의 합(결과값)은 최대 10^12 수준까지 커질 수 있음
• int의 최댓값은 2,147,483,647(≈ 2.1 ×10^9)
• 따라서 누적 변수 result는 long이어야 함

수치적으로 다시 확인해 본다면 다음과 같습니다.

- 최악(B=1, C=1)에서 각 시험장 필요 인원 = Ai (총 1명 + 부감독관 Ai−1)

- 총합 = ΣAi

- ΣAi > 2,147,483,647이면 int 오버플로 → long 필수

ex) N=1,000,000이면 평균 A ≥ 2,148부터 이미 위험

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int[] arr = new int[N];
    for(int i = 0; i < N; i++) {
      arr[i] = sc.nextInt();
    }

    int B = sc.nextInt();
    int C = sc.nextInt();

    long result = 0;
    for (int i = 0; i < N; i++) {
      // 총감독관 
      arr[i] = arr[i] - B; 
      result++;

      // 부감독관
      if(arr[i] > 0) {
        int add = 0;
        if( arr[i] % C !=0 ) {
          add = arr[i] / C + 1;
        } else {
          add = arr[i] / C;
        }
        result += add;
      }
    }
    System.out.println(result);
  }
}

 

 

 

 

 

 

1. 입력 크기 → 시간복잡도 감각 익히기

문제 제약 조건(입력 크기와 제한 시간)을 보고 가능한 복잡도를 먼저 가늠합니다.

 

기준표

- N≤ 10^3 → O(N³)까지 가능

- N≤ 10^5 → O(N log N) 정도 필요

- N≤ 10^6 → O(N), O(N log log N) 정도

- N≤ 10^8 → O(N)도 위험, 보통 수학적 공식, 해시, 그리디 등 필요

쿼리 M이 크면 전처리(누적합) or 자료구조 필요

 

문제 조건을 보면 "이건 어떤 복잡도여야 한다"부터 추측하는 습관 들이기 !

 

2. 기초 알고리즘/자료구조 확실히 다지기

 

(1) 배열/문자열

- 누적합(1D, 2D prefix sum), 투포인터, 슬라이딩 윈도우

- 문자열 처리(KMP, Rabin-Karp, Z 알고리즘)

 

(2) 자료구조

- 스택/큐/덱 (O(1) push/pop)

- 힙(우선순위큐) → Dijkstra 등

- 해시맵/셋 (O(1) 평균 탐색)

- 트리와 기본 그래프 구조

 

(3) 그래프 탐색

- DFS/BFS, 백트래킹

- 최단거리 (Dijkstra, BFS, Bellman-Ford, Floyd-Warshall)

 

(4) 정렬/탐색

- 기본 정렬 (퀵/병합/힙) → O(N log N)

- 이분 탐색 (parametric search 포함)

- LIS (이분 탐색 활용)

 

3. 시간 줄이는 핵심 도구

(1) 누적합 (prefix sum)

- 쿼리 많은 합 문제의 기본 (11660 같은 문제)

 

(2) 그리디 vs DP 판단

- 부분 최적해로 전체 최적? → 그리디

- 겹치는 부분 문제? → DP

 

(3) 세그먼트 트리 / 펜윅트리

- 구간 합/최댓값 쿼리 + 업데이트

 

(4) 그래프 알고리즘

- 다익스트라 / MST = 최소 스패닝 트리(Kruskal, Prim)

 

(5) Union-Find (Disjoint Set)

- 집합 관리, 사이클 판별

 

(6) 비트마스킹

- 부분집합, DP 최적화

 

(7) 수학적 최적화

- 최대공약수/최소공배수, 에라토스테네스 체, 모듈러 연산, 조합 DP

 

4. 입출력 최적화

(Java 기준)

- 입력: BufferedReader + StringTokenizer

- 출력: StringBuilder

 

Scanner는 편리하지만 느림 → 입력이 많은 문제는 반드시 교체

알고리즘이 맞아도 I/O 병목이면 TLE → 습관적으로 빠른 입출력 사용

 

 

 

5. 문제 접근 프로세스 (시간초과 방지 습관)

(1) 입력 크기 확인

→ 대략 허용 시간복잡도 예측

 

(2) 브루트포스 가능?

→ 안 되면 최적화 필요

 

(3) 반복되는 연산은 없는가?

→ 있으면 전처리/누적합

 

(4) 데이터가 계속 바뀌는가?

→ 세그먼트트리/펜윅트리

 

(5) 그래프인가?

→ BFS/DFS/다익스트라 중 선택

 

(6) 최적화 여지 확인

- 중복 연산 제거

- DP 메모이제이션

- 수학적 공식 유도

 

(7) I/O 최적화까지 체크

 

6. 실전 대비 문제 유형

시간초과를 피하려면 이 유형들 반드시 익혀야 합니다 !

 

(1) 누적합/슬라이딩 윈도우

- BOJ 11659 (1D 합), 11660 (2D 합)

 

(2) 정렬 + 이분탐색

- BOJ 1920 (수 찾기), 10816 (숫자 카드 2)

 

(3) 세그먼트 트리/펜윅트리

- BOJ 2042 (구간 합 구하기)

 

(4) 그래프 최단거리

- BOJ 1753 (다익스트라), 11404 (플로이드)

 

(5) 그리디

- BOJ 11047 (동전 0), 1931 (회의실 배정)

 

(6) DP

- BOJ 1003 (피보나치 함수), 1149 (RGB거리)

 

(7) 수학/에라토스테네스

- BOJ 1929 (소수 구하기), 11401 (이항계수)

 

7. 공부 습관 들이기

- 문제 풀 때마다 시간복잡도 계산식 직접 적기

- 틀리면/시간초과 나면 → 왜 TLE인지 분석 기록하기

- 같은 유형 반복해서 풀어보기 (프리픽스 합, 세그먼트 트리 등)

 

정리

알고리즘 공부할 때 "시간초과를 피하는 사고"를 위해서 다음 3가지를 습관화하고자 합니다.

1. 입력 크기로 복잡도 한계 잡기
2. 반복 연산 줄이는 전처리/자료구조 선택
3. I/O 최적화