[코딩테스트] 정렬, 이진 탐색, 누적합으로 시간 복잡도 줄이기

이번 글의 키워드는 세 가지입니다.

• 정렬 (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 작성하는 패턴에 꼭 익숙해져야 합니다.

 

---

 

Ⅲ. 정렬 후 처리 패턴

대표적인 예로, 회의실 배정 문제(끝나는 시간이 빠른 순서대로 고르기)를 생각해볼 수 있습니다.

1. 회의들을 (시작 시간, 끝나는 시간)으로 입력받는다.
2. 끝나는 시간 기준으로 오름차순 정렬한다.
3. 가장 빨리 끝나는 회의부터 하나씩 선택하면서, 겹치지 않는 회의를 최대한 많이 고른다.

정렬 기준만 잘 세우면 이후 로직은 단순해집니다.

이런 패턴은 나중에 그리디 알고리즘에서 계속 활용됩니다.

 

---

 

Ⅳ. 이진 탐색(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차원 누적합 기본

1. 원본 배열 arr[1...N]이 있다고 할 때
2. prefix[0] = 0
3. 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/그리디 등 이후 모든 알고리즘과 자주 엮여 나오기 때문에,

여태까지의 내용을 반복해서 손코딩해보면 뒤에 나오는 알고리즘들을 이해하는 속도가 훨씬 빨라집니다.