분할 정복, 정렬 알고리즘, 그래프
1. 오늘의 학습 흐름
- 어제 문제 풀이 (정올 1370 회의실, BOJ 13904 과제)
- 분할 정복 (Divide and Conquer): 거듭제곱, 이진 탐색
- BOJ 2630 색종이 만들기, BOJ 1074 Z
- 정렬 알고리즘 시간복잡도 비교
- 그래프 개념 입문
2. 분할 정복 (Divide and Conquer)
세 단계로 구성된다.
- 분할: 해결할 문제를 여러 개의 작은 부분으로 나눈다
- 정복: 나눈 작은 문제를 각각 해결한다
- 통합: (필요하다면) 해결된 해답을 모은다
대표 알고리즘: 병합 정렬, 퀵 정렬, 이진 탐색
트리 형태로 나뉘면 깊이가 log₂N
n
n/2 n/2
n/4 n/4
n/8 n/8
...
2^h = n → h = log₂n거듭제곱 (PowerTest)
x^n을 구할 때 단순 재귀는 O(N)이다.
public static long powerRec(int x, int n) {
if (n == 1) return x;
return x * powerRec(x, n - 1);
}
// x^2111111111 → 21억 번 호출 → 스택 오버플로우분할 정복으로 O(logN)으로 줄인다.
public static long dcPower(int x, int n) {
if (n == 0) return 1;
if (n == 1) return x;
long half = dcPower(x, n >> 1); // n/2까지만 계산
if (n % 2 == 0) return half * half; // 짝수: x^n = (x^n/2)²
else return half * half * x; // 홀수: x^n = (x^n/2)² * x
}
// x^16 → x^8 → x^4 → x^2 → x^1 → 4번 호출
// x^2111111111 → 약 31번 호출n을 절반씩 줄이기 때문에 깊이가 log₂n이 된다. 같은 값을 두 번 계산하지 않고 half를 재사용하는 것이 핵심이다.
이진 탐색 (BinarySearchTest)
정렬된 배열에서 중간값과 비교해 탐색 범위를 절반씩 줄인다. O(logN).
private static int binarySearch(int key, int start, int end) {
if (start > end) return -1; // 못 찾음
int mid = (start + end) >> 1; // (start + end) / 2
if (values[mid] == key) return mid;
else if (values[mid] > key) return binarySearch(key, start, mid - 1); // 왼쪽
else return binarySearch(key, mid + 1, end); // 오른쪽
}Arrays.binarySearch()가 이미 내장돼 있다. 못 찾으면 -(삽입 위치) - 1을 반환한다. -1 대신 음수를 쓰는 이유는 index 0과 구분하기 위해서다.
Arrays.sort(values); // 이진 탐색은 반드시 정렬 후에 써야 한다
Arrays.binarySearch(values, 65); // 찾으면 index, 못 찾으면 음수BOJ 2630 - 색종이 만들기 (분할 정복)
NxN 배열을 같은 색이면 카운트, 다른 색이면 4등분해서 재귀하는 쿼드트리 문제다.
public static void check(int r, int c, int size) {
if (checkColor(r, c, size)) { // 현재 영역이 단색이면
if (paper[r][c] == 0) white++;
else blue++;
return;
}
int half = size / 2; // 4등분
check(r, c, half);
check(r, c + half, half);
check(r + half, c, half);
check(r + half, c + half, half);
}checkColor()가 O(size²)라 전체 시간복잡도는 O(N² logN)이지만, 단색인 영역은 조기 종료되니 실제로는 훨씬 빠르다.
BOJ 1074 - Z (분할 정복)
2^N × 2^N 배열을 Z 모양으로 순회할 때 (r, c)가 몇 번째로 방문되는지 구하는 문제다. 배열을 실제로 만들면 메모리 초과라서 분할 정복으로 해결한다.
public static void Z(int r, int c, int size, int targetR, int targetC) {
if (size == 1) {
System.out.println(count);
return;
}
size >>= 1; // 절반으로
if (targetR < r + size && targetC < c + size) {
Z(r, c, size, targetR, targetC); // 1사분면
} else if (targetR < r + size && targetC >= c + size) {
count += size * size; // 1사분면 크기만큼 건너뜀
Z(r, c + size, size, targetR, targetC); // 2사분면
} else if (targetR >= r + size && targetC < c + size) {
count += 2 * size * size;
Z(r + size, c, size, targetR, targetC); // 3사분면
} else {
count += 3 * size * size;
Z(r + size, c + size, size, targetR, targetC); // 4사분면
}
}목표 좌표가 어느 사분면에 있는지 판단해서 나머지 사분면의 크기를 count에 더하고, 해당 사분면으로 재귀한다. 탐색 범위를 절반씩 줄이니까 O(logN)이다.
3. 정렬 알고리즘 시간복잡도
| 종류 | 설명 | 평균 | 최악 |
|---|---|---|---|
| 버블 정렬 | 인접한 두 값을 비교해 큰 값을 뒤로 | O(N²) | O(N²) |
| 선택 정렬 | 전체에서 최솟값을 선택해 앞으로 이동 | O(N²) | O(N²) |
| 삽입 정렬 | 정렬된 부분에 알맞은 위치에 삽입 | O(N²) | O(N²) |
| 병합 정렬 | 계속 반으로 나누고 합치면서 정렬. 분할 정복 대표 | O(NlogN) | O(NlogN) |
| 퀵 정렬 | Pivot 기준으로 작은 것/큰 것 나누기. Pivot에 따라 O(N²) 가능 | O(NlogN) | O(N²) |
| Tim 정렬 | 삽입 정렬 + 병합 정렬 하이브리드. Java Arrays.sort() 내부 구현 | O(NlogN) | O(NlogN) |
Java의 Arrays.sort()는 Tim 정렬로 구현되어 있어서 최악의 경우에도 O(NlogN)을 보장한다. 코테에서 직접 정렬을 구현하는 경우는 드물지만, 각 정렬의 특성과 시간복잡도는 알아둬야 한다.
퀵 정렬이 평균 O(NlogN)이지만 Pivot 선택에 따라 최악 O(N²)가 되는 이유: 이미 정렬된 배열에서 첫 번째 원소를 Pivot으로 쓰면 매번 한쪽으로만 분할된다.
4. 그래프 (Graph)
그래프란
정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료구조다. 선형 자료구조나 트리로 표현하기 어려운 N:N 관계를 가지는 원소들을 표현하기에 용이하다.
주요 용어:
- 정점(Node, Vertex): 그래프의 구성 요소. 하나의 연결점. 데이터를 저장하는 데 사용
- 간선(Edge): 노드와 노드를 연결하는 선
- 차수(Degree): 정점에 연결된 간선의 수
- 인접(Adjacent): 두 개의 노드가 간선으로 직접 연결된 상태
- 사이클(Cycle): 동일한 노드로 되돌아오는 경로가 존재하는 상태
- 가중치(Weight): 가중치 그래프에서 간선에 할당된 값 또는 비용
V개의 정점을 가지는 그래프의 최대 간선 수는 V*(V-1)/2개다. (5개 정점이면 최대 10개)
그래프 유형
무향 그래프(Undirected Graph): 방향이 없는 양방향 간선
유향 그래프(Directed Graph): 방향이 있는 간선
가중치 그래프(Weighted Graph): 간선에 비용/거리 등 가중치가 있음
DAG(Directed Acyclic Graph): 방향이 있고 사이클이 없는 그래프
완전 그래프: 정점들에 대해 가능한 모든 간선을 가진 그래프
트리는 사이클이 없는 무향 연결 그래프다.
- 두 노드 사이에 유일한 경로가 존재
- 각 노드는 최대 하나의 부모 노드가 존재
- 각 노드는 자식 노드가 없거나 하나 이상이 존재
그래프 경로
경로(Path): 정점 A에서 시작해 정점 B로 끝나는 순회로, 두 정점 사이를 잇는 간선들을 순서대로 나열한 것
단순 경로: 경로 중 한 정점을 최대 한 번만 지나는 경로
순환 경로(Cyclic Path): 경로의 시작점과 끝점이 같거나, 어떤 정점을 2번 이상 거치는 경우
그래프 표현 방법
간선의 정보를 저장하는 방식이다. 메모리나 성능을 고려해서 결정한다.
인접 행렬 (Adjacent Matrix)
V×V 크기의 2차원 배열로 간선 정보를 저장한다.
int[][] adj = new int[V][V];
// adj[i][j] = 1이면 i→j 간선 존재, 0이면 없음
// 가중치 그래프면 adj[i][j] = 가중치
// 예: 0-1 간선(가중치 5), 0-3 간선(가중치 7) 추가
adj[0][1] = 5; adj[1][0] = 5; // 무향이면 양방향
adj[0][3] = 7; adj[3][0] = 7;무향 그래프: i번째 행의 합 = V_i의 차수
유향 그래프: 열의 합 = V_i의 진출 차수 / 행의 합 = V_i의 진입 차수
메모리: O(V²). 정점이 많고 간선이 적으면 낭비가 심하다.
인접 리스트 (Adjacent List)
각 정점마다 인접한 정점들을 연결 리스트로 저장한다.
ArrayList<Integer>[] adj = new ArrayList[V];
for (int i = 0; i < V; i++) adj[i] = new ArrayList<>();
// 0-1 간선 추가 (무향)
adj[0].add(1);
adj[1].add(0);메모리: O(V + E). 간선이 적을 때 인접 행렬보다 효율적이다.
간선 리스트 (Edge List)
간선(시작 정점, 끝 정점)의 정보를 객체로 표현해 리스트에 저장한다. 최단 경로 알고리즘(Bellman-Ford 등)에서 자주 쓰인다.
| 표현 방식 | 메모리 | 간선 존재 확인 | 인접 정점 탐색 |
|---|---|---|---|
| 인접 행렬 | O(V²) | O(1) | O(V) |
| 인접 리스트 | O(V+E) | O(차수) | O(차수) |
| 간선 리스트 | O(E) | O(E) | O(E) |
그래프 탐색
그래프로 표현된 모든 자료(정점)를 빠짐없이 탐색하는 것이다.
두 가지 방법:
- BFS(Breadth First Search): 너비 우선 탐색 → Queue 사용
- DFS(Depth First Search): 깊이 우선 탐색 → Stack 또는 재귀 사용
BFS는 인접한 정점들을 먼저 모두 방문한 후, 방문했던 정점을 시작점으로 다시 인접 정점들을 차례로 방문하는 방식이다. 선입선출 형태의 Queue를 활용한다.
BFS와 DFS 구현은 다음 TIL에서 코드로 정리한다.
5. 오늘 후기
오늘 거듭제곱 예제가 인상 깊었다. 배열을 실제로 만들면 2^(2N) 크기가 필요해서 메모리 초과가 나지만, "목표 좌표가 어느 사분면인가"만 판단하면 O(logN)으로 해결된다. 분할 정복의 핵심은 "모든 걸 다 보지 않아도 된다"는 것이다.
6. 키워드 정리
분할 정복 Divide and Conquer 그래프
7. 내일의 목표
- 그래프 DFS/BFS 구현 및 문제 풀이
- 백준 문제 풀이
