[코딩테스트] 정렬, 이진 탐색, 누적합으로 시간 복잡도 줄이기
이번 글의 키워드는 세 가지입니다.
- 정렬 (Sorting)
- 이진 탐색 (Binary Search)
- 누적합 (Prefix Sum)
이전 글들에서 구현, 완전 탐색, 자료구조를 익혔다면,
이제는 시간복잡도를 줄이는 대표 패턴을 익힐 차례입니다.
이 글에서는 자바를 기준으로 정렬, 이진 탐색, 누적합의 개념과 코드 패턴을 정리합니다.
Ⅰ. 목표
정렬, 이진 탐색, 누적합을 이용해 단순 완전 탐색보다 효율적인 풀이를 설계할 수 있는 상태 만들기
구체적으로는 아래 네 가지를 목표로 합니다.
- Arrays.sort, Collections.sort와 Comparator 사용법 익히기
- 정렬 후 처리 패턴(그리디와 함께 자주 등장)을 이해하기
- 이진 탐색 템플릿을 외워서 바로 코딩할 수 있게 만들기
- 누적합을 사용해 구간 합을 O(1)에 계산하는 패턴 익히기
Ⅱ. 정렬 (Sorting)
- 왜 정렬이 중요한가
정렬은 코딩테스트에서 거의 모든 영역과 연결됩니다.
- 그리디 알고리즘: 정렬 + 한 번 스캔 패턴이 매우 많음
- 이진 탐색: 정렬된 배열에서만 제대로 동작
- 투 포인터, 슬라이딩 윈도우: 대개 정렬된 배열을 전제로 함
따라서 이번 글에서는 자바에서 정렬을 손에 익히는 것이 가장 우선입니다.
- 기본 정렬: Arrays.sort
원시 타입 배열(예: int[])은 Arrays.sort로 쉽게 정렬할 수 있습니다.
import java.util.Arrays;
int[] arr = {5, 3, 9, 1, 4};
Arrays.sort(arr); // 오름차순 정렬
// arr = {1, 3, 4, 5, 9}내림차순 정렬은 래퍼 타입(Integr)과 Comparator가 필요합니다.
import java.util.Arrays;
import java.util.Collections;
Integer[] arr = {5, 3, 9, 1, 4};
Arrays.sort(arr, Collections.reverseOrder()); // 내림차순
- 객체 정렬: Comparator 사용
정렬 기준을 직접 정해야 할 때는 Comparator를 사용합니다.
예를 들어, 사람의 나이와 이름을 기준으로 정하는 경우 아래와 같습니다.
import java.util.*;
class Person {
String name;
int age;
Person(String name, int age) {
this.name = name;
this.age = age;
}
}
public class Main {
public static void main(String[] args) {
List<Person> list = new ArrayList<>();
list.add(new Person("Kim", 25));
list.add(new Person("Lee", 20));
list.add(new Person("Park", 25));
// 나이 오름차순, 나이가 같으면 이름 사전순
list.sort((p1, p2) -> {
if (p1.age == p2.age) {
return p1.name.compareTo(p2.name);
}
return p1.age - p2.age;
});
for (Person p : list) {
System.out.println(p.age + " " + p.name);
}
}
}
실제로 코딩 테스트에서는 좌표 정렬, 회의실 배정, 커스텀 기준 정렬 등이 자주 등장하므로
람다로 Comparator 작성하는 패턴에 꼭 익숙해져야 합니다.
Ⅲ. 정렬 후 처리 패턴
대표적인 예로, 회의실 배정 문제(끝나는 시간이 빠른 순서대로 고르기)를 생각해볼 수 있습니다.
- 회의들을 (시작 시간, 끝나는 시간)으로 입력받는다.
- 끝나는 시간 기준으로 오름차순 정렬한다.
- 가장 빨리 끝나는 회의부터 하나씩 선택하면서, 겹치지 않는 회의를 최대한 많이 고른다.
정렬 기준만 잘 세우면 이후 로직은 단순해집니다.
이런 패턴은 나중에 그리디 알고리즘에서 계속 활용됩니다.
Ⅳ. 이진 탐색(Binary Search)
- 이진 탐색이란?
이진 탐색은 정렬된 배열에서 원하는 값을 찾는 알고리즘입니다.
항상 가운데 값을 기준으로 범위를 반으로 줄여 나가므로 시간 복잡도는 O(log N)입니다.
완전 탐색이 O(N)이라면,
이진 탐색은 그보다 훨씬 빠르게 탐색할 수 있습니다.
- 기본 템플릿 코드
가장 기본적인 값 찾기 템플릿은 다음과 같습니다.
public static boolean binaySearch(int[] arr, int target) {
int left = 0;
int right = arr.length -1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) {
return true; // 찾음
} else if (arr[mid] < target) {
left = mid + 1; // 왼쪽 범위로 이동
} else {
right = mid - 1; // 오른쪽 범위로 이동
}
}
return false; // 못 찾음
}이 템플릿을 외워두면 문제에서 정렬된 리스트에서 수가 있는지 없는지
확인하는 유형이 나오면 바로 가져다 쓸 수 있습니다.
- 예시: 수 찾기
간단한 예시로, N개의 정수 배열과 M개의 쿼리가 주어졌을 때
각 쿼리 값이 배열 안에 존재하는지 O(MlogN)으로 판단하는 문제를 생각해보겠습니다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i=0; i<n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr); // 이진 탐색을 위해 정렬
int m = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
for (int i=0; i<m; i++) {
int target = Integer.parseInt(st.nextToken());
boolean exists = binarySearch(arr, target);
sb.append(exists ? 1 : 0).append('\n');
}
System.out.print(sb);
}
private static boolean binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length -1;
while (left <= right) {
int mid = (left + rigth) / 2;
if (arr[mid] == target) {
return true;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
rigth = mid - 1;
}
}
return false;
}
}이 패턴은 정렬 + 이진 탐색의 가장 기본적인 형태입니다.
Ⅴ. 누적합 (Prefix Sum)
- 왜 누적합을 쓰는가
배열의 구간 합을 자주 구하는 문제에서 매번 합을 직접 계산하면 O(N)이 걸립니다.
하지만 누적합 배열을 한 번 만들어 두면, 어떤 구간 [L, R]의 합도 O(1)에 구할 수 있습니다.
- 1차원 누적합 기본
- 원본 배열 arr[1...N]이 있다고 할 때
- prefix[0] = 0
- prefix[i] = prefix[i-1] + arr[i]로 계산
이때, 구간 [L, R]의 합은 다음과 같이 구합니다.
sum(L, R) = prefix[R] - prefix[L - 1]
arr[i] = prefix[i] - prefix[i-1]
sum(L, R) = arr[L] + arr[L + 1] + ... + arr[R-1] + arr[R]
= (prefix[L] - prefix[L -1]) + (prefix[L + 1] - prefix[L]) + ... + (prefix[R-1] - prefix[R -2]) + (prefix[R] - prefix[R -1])
= prefix[R] - prefix[L - 1]
코드로 보면 아래와 같습니다.
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n + 1];
int[] prefix = new int[n + 1];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i=1; i<=n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
prefix[i] = prefix[i - 1] + arr[i];
}
// 예: 구간 [L, R] 합 구하기
int L = 2;
int R = 5;
int sum = prefix[R] - prefix[L - 1];
- 여러 개의 구간 합 쿼리 처리
예를 들어, 길이가 N인 배열이 있고 M개의 쿼리 [L, R]에 대해 각각 구간 합을 구하는 문제는
누적합으로 해결하면 전체 시간 복잡도가 O(N + M)이 됩니다.
int n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
int[] prefix = new int[n + 1];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i=1; i<=n; i++) {
int x = Integer.parseInt(st.nextToken());
prefix[i] = prefix[i - 1] + x;
}
StringBuilder sb = new StringBuilder();
for (int i=0; i<m; i++) {
st = new StringTokenizer(br.readLine());
int L = Integer.parseInt(st.nextToken());
int R = Integer.parseInt(st.nextToken());
int sum = prefix[R] - prefix[L - 1];
sb.append(sum).append('\n');
}
System.out.print(sb);
- 2차원 누적합
조금 더 나가면, 2차원 누적합을 이용해 2D 배열에서 직사각형 영역의 합을 O(1)에 구할 수 있습니다.
이번 글에서는 1차원 누적합만 확실히 이해하고, 2차원은 이런 것도 있다 정도로 가볍게 보고 넘어가보겠습니다.
Ⅵ. 시간 복잡도 관점에서 내용 정리
- 정렬: O(NlogN)에 데이터 정리 → 이후 한 번 스캔 O(N)
- 이분 탐색: O(log N)에 특정 값 탐색
- 누적합: O(1)에 구간 합 계산(빌드 비용 O(N))
단순 완전 탐색으로 풀면 O(N*N)이나 O(N*N*N)가 나오는 문제도
정렬 + 이분 탐색 + 누적합 등을 잘 조합하면 O(NlogN) 또는 O(N)으로 줄일 수 있습니다.
왜 이 알고리즘을 쓰는지를 시간 복잡도 관점에서 생각해보는 연습을 함께 하는 것이 좋습니다.
Ⅶ. 체크리스트
- Arrays.sort, Collections.sort로 오름차순/내림차순 정렬을 자유롭게 할 수 있다.
- 람다를 이용해 Comparator를 작성하고, 커스텀 기준으로 객체 리스트를 정렬해본 경험이 있다.
- 이분 탐색 템플릿 코드를 외워서, 정렬된 배열에서 특정 값 존재 여부를 O(log N)에 판별할 수 있다.
- 정렬 + 이분 탐색 패턴으로 수 찾기 유형 문제를 풀 수 있다.
- 1차원 누적합 배열을 만들고, [L, R] 구간 합을 O(1)에 구하는 코드를 직접 작성할 수 있다.
- 문제를 보고 "정렬 + 이분 탐색으로 풀 수 있을까?", "누적합을 쓰면 구간 계산이 빨라질까?"를 먼저 떠올릴 수 있다.
다음 글에서는 그래프 알고리즘을 다루어보겠습니다.
- 그래프 표현(인접 리스트 / 인접 행렬)
- DFS(깊이 우선 탐색), BFS(너비 우선 탐색)
- 미로 탐색, 영역 개수 세기, 연결 요소 찾기
정렬, 이분 탐색, 누적합은 그래프/DP/그리디 등 이후 모든 알고리즘과 자주 엮여 나오기 때문에,
여태까지의 내용을 반복해서 손코딩해보면 뒤에 나오는 알고리즘들을 이해하는 속도가 훨씬 빨라집니다.