개요
앞 편에서 unordered_map이 평균 O(1)을 받는 대신 순서를 포기한다는 데까지 왔다. 이번 편은 순서를 지키면서 O(log N)을 받는 쪽이다.
그리고 마지막에 그래프 탐색이 나오는데, 여기서 이론 정리 - < Big-O, 정렬, DFS/BFS >를 또 열게 됐다. 첫 편에서 Big-O 절의 문장 하나를 고쳤는데, 같은 글의 DFS/BFS 절에도 손볼 데가 두 군데 있었다.
이번 편은 앞의 두 편과 결이 조금 다르다. 앞에서는 모르던 이름이 붙는 쪽이 많았는데, 여기는 대부분 이미 알고 문제도 풀어본 것들이었다. 그런데 설명해보라니까 절차만 나오고 이유가 안 나왔다.
- 절차는 아는데 이유가 없던 것 — 이진 탐색이 왜 정렬된 데이터에서만 되는가
- 조건을 떼고 외우던 것 — BST 탐색 O(log N). 균형 잡혔을 때만 성립하는 결과였다
- 1년 반 전에 내가 조건 없이 적어둔 것 — DFS/BFS 두 문장
이 문장이 언제 참인가? 오늘 고친 것들이 전부 여기 걸렸다.
( 진행 방식은 앞 편들과 같다. 직접 컴파일해서 돌려보지는 않았고, 아래 코드는 전부 개념 예시다 )
1. 이진 탐색의 핵심은 “중간을 본다”가 아니다
이진 탐색은 예전에도 정리했고 문제도 풀어봤다. 그런데 “왜 정렬된 데이터에서만 되는가”라는 질문에는 “중간값과 비교해서 반씩 줄인다”까지만 나왔다.
이건 절차지 이유가 아니다. 이유는 한 단계 앞에 있었다.
정렬되어 있기 때문에, 중간값과 비교하면 한쪽 절반에는 정답이 없다는 것을 보장할 수 있다. 그 보장이 있어서 후보를 버릴 수 있다.
절반씩 줄어드는 건 그 보장의 결과다. 정렬이 안 되어 있으면 중간값을 아무리 봐도 버릴 근거가 없으니, 중간을 보는 행위 자체가 무의미해진다.
복잡도는 여기서 바로 나온다.
N -> N/2 -> N/4 -> N/8 -> ... -> 1
N을 2로 몇 번 나눠야 1이 되는가 — log2 N이다. 그래서 O(log N)이다.
1024개면 10단계다. 이 숫자를 보고 나니 정렬 편에서 O(N²)과 O(N log N)을 비교하던 게 다르게 읽혔다. 로그가 붙는 알고리즘은 대부분 “매 단계 후보를 일정 비율로 버린다”는 구조를 갖고 있다.
2. BST — 복잡도가 N이 아니라 height에 걸려 있다
이진 탐색 트리의 탐색을 O(log N)으로 외우고 있었다. 그런데 정확히는 이쪽이다.
O(height)
트리 높이에 비례한다. N이 아니라 height다. 그리고 height가 log N이 되는 건 트리가 균형 잡혀 있을 때만 성립하는 조건부 결과였다.
| 트리 상태 | height | 탐색 |
|---|---|---|
| balanced tree(균형 트리) | ≈ log N | O(log N) |
| skewed tree(편향 트리) | ≈ N | O(N) |
정렬된 값을 순서대로 넣으면 어떻게 되는가
// 일반 BST에 1, 2, 3, 4, 5 순서로 삽입
1
\
2
\
3
\
4
\
5
왼쪽 자식이 하나도 안 생긴다. 트리라기보다 연결 리스트다. height가 N이 되고 탐색도 O(N)이 된다.
가장 정돈된 입력이 가장 나쁜 트리를 만든다. 무작위로 들어오면 오히려 어느 정도 균형이 잡히는데, 정렬해서 넣으면 최악이 된다.
self-balancing tree(자가 균형 트리)는 삽입/삭제 때 구조를 조정해서 height를 log N 수준으로 유지하려는 자료구조다. AVL이나 Red-Black 같은 이름들이 여기 붙는데, 회전 규칙 세부는 이번엔 안 팠다. 범위를 넓히는 쪽을 먼저 하기로 했으니 여기는 이름만 걸어두고 넘어간다.
3. map과 unordered_map — 뭘 보고 고르나
앞 편의 해시 테이블과 2번의 BST가 여기서 만난다.
unordered_map |
map |
|
|---|---|---|
| 기반 | 해시 테이블 | 균형 트리 (아래 참고) |
| 평균 탐색 | O(1) | O(log N) |
| 최악 탐색 | O(N) — 한 버킷에 몰릴 때 | O(log N) |
| key 순서 | 보장 없음 | 정렬된 순서 |
| 최악 예측 | 어렵다 | 쉽다 |
표준이 강제하는 건 자료구조가 아니라 복잡도다. map이 균형 트리로 구현된다는 건 사실상 모든 구현체가 그렇다는 이야기지 표준 조항은 아니라서, 내부 구조를 단정하는 대신 O(log N)이 보장된다까지만 들고 있기로 했다.
이름만 보면 unordered_map이 항상 빠른 것 같은데, 고르는 축은 속도 하나가 아니었다.
-
key를 순서대로 훑을 일이 있는가 → 있으면
map -
최악 시간을 예측할 수 있어야 하는가 → 그러면
map
두 번째가 게임에서 의외로 걸린다. 평균이 빨라도 하필 그 프레임에 최악이 걸리면 화면에서는 그냥 끊긴 것으로 보인다. 첫 편 6번에서 상각 O(1)을 정리하면서 같은 이야기를 했는데, 여기서 다시 나왔다.
평균이 좋은 것과 최악이 예측 가능한 것은 다른 요구다.
4. 그래프 — 사이클과 visited
Graph(그래프)는 vertex(정점)와 edge(간선)로 연결 관계를 표현한다. 트리와 달리 경로를 따라가다 이미 방문한 정점으로 돌아올 수 있다. 이게 cycle(사이클, 순환)이다.
그래서 그래프 순회에서는 visited(방문 여부) 관리가 필수다. 트리에서는 위에서 아래로만 내려가니까 신경 쓸 일이 없는데, 그래프는 안 챙기면 같은 자리를 돌게 된다.
사이클이라는 말 자체는 < RAII와 스마트 포인터 >에서 shared_ptr 순환 참조로 이미 만났었다. 거기서는 사이클이 참조 카운트가 0이 안 되는 원인이었고, 여기서는 탐색이 안 끝나는 원인이다. 같은 구조가 다른 문제를 만든다.
5. 1년 반 전 DFS/BFS 설명을 다시 봤다
예전 글에는 이렇게 적혀 있다.
DFS — 여러 길을 탐색하는 것보단, 하나의 목표지점을 구할 때 사용합니다.
BFS — 시작지점부터 여러 길을 탐색해가며, 최단경로를 구하는데 주로 사용합니다.
용도로는 자주 그렇게 쓴다. 그런데 설명으로 쓰면 두 군데가 걸린다.
첫째, “여러 길이냐 하나냐”가 둘의 차이가 아니다
DFS도 조건에 따라 그래프 전체를 다 볼 수 있다. visited를 관리하면서 끝까지 돌면 도달 가능한 정점을 전부 방문한다. BFS도 마찬가지다.
둘의 진짜 차이는 완전 탐색을 하느냐가 아니라 탐색 순서다.
| 순서 | 자료구조 | |
|---|---|---|
| BFS | 가까운 깊이부터 층층이 | Queue(큐) |
| DFS | 한 경로를 끝까지 판 뒤 되돌아옴 | Stack(스택) 또는 재귀 |
“하나의 목표지점을 구할 때 DFS”는 결과적으로 그렇게 쓰는 경우가 많다는 관찰이지, 알고리즘이 그것만 할 수 있다는 뜻이 아니었다. 예전 글은 그걸 성질처럼 적어놨다.
둘째, BFS의 최단 경로에는 조건이 빠져 있다
이게 더 중요한 쪽이다. BFS가 최단 경로를 주는 건 조건부다.
unweighted graph(비가중 그래프)이거나, 모든 간선 비용이 동일할 때 — 간선 개수 기준 최단 경로를 보장한다.
간선마다 비용이 다르면 BFS는 최소 비용 경로를 보장하지 않는다. 간선을 적게 지나는 길이 총 비용은 더 클 수 있기 때문이다.
A ---(비용 10)--- B
A --(1)-- C --(1)-- B
간선 개수 : A-B 가 1개로 최소
실제 비용 : A-C-B 가 2로 최소
BFS는 위쪽을 고른다. 가중치가 있는 그래프에서 최소 비용을 원하면 다른 알고리즘이 필요하다.
예전 글에는 이 조건이 없다. 그때는 코딩 테스트에서 만나는 격자 미로만 생각했던 것 같은데, 격자 미로는 모든 이동 비용이 1인 특수한 경우다. 특수한 경우에서 성립한 문장을 조건 없이 적어둔 셈이다.
정리
절차는 알았는데 이유가 없던 것
- 이진 탐색이 반씩 줄인다 — 줄이는 게 아니라, 한쪽에 답이 없음을 보장할 수 있어서 버리는 것이다
- BST 탐색은 O(log N) — 정확히는 O(height)이고, log N은 균형 잡혔을 때의 결과다
1년 반 전 글에서 고친 것
- DFS/BFS의 차이는 완전 탐색 여부가 아니라 탐색 순서다. 둘 다 전체를 볼 수 있다
- BFS의 최단 경로는 비가중 그래프 또는 동일 비용일 때의 보장이다. 조건이 빠져 있었다
이번에 새로 얹은 것
- 정렬된 입력을 순서대로 넣으면 BST가 편향된다. 가장 정돈된 입력이 가장 나쁜 트리를 만든다
-
map과unordered_map은 속도만으로 고르지 않는다. 순서와 최악 예측 가능성이 축이다 - 사이클은 순환 참조에서 만났던 구조와 같다. 거기선 수명이, 여기선 탐색이 안 끝난다
보류한 것
- AVL / Red-Black의 회전 규칙 세부 — 지금은 범위를 넓히는 쪽이 우선이라 판단했다
같은 글을 이틀 사이에 두 번 열어서 두 절을 고치게 됐다. 공통점이 있었는데, 둘 다 특정 상황에서 성립하는 문장을 조건 없이 적어둔 것이었다. Big-O를 최악 경우로 못 박은 것도, BFS 최단 경로에 가중치 조건을 안 단 것도 같은 종류의 생략이다.
그때는 정의를 옮겨 적는 게 목적이었으니 그 목적에는 맞았다. 지금은 면접에서 한 번 더 물어봤을 때 버티는가가 기준이라 같은 문장이 안 버틴다. 기준이 달라진 거지 그때 글이 엉터리였던 건 아니다.
다음은 방향을 바꿔서 성능 디버깅 쪽이다. 지금까지는 자료구조를 하나씩 봤는데, 화면이 실제로 느려졌을 때 무엇부터 의심할 것인가를 순서로 세워볼 차례다.
참고 자료
- cppreference - std::map
- cppreference - std::unordered_map
- cppreference - std::binary_search
- cppreference - std::lower_bound
- 이론 정리 - < Big-O, 정렬, DFS/BFS > — 1년 반 전 정리. DFS/BFS 절 두 군데를 고쳤다
- 이론 정리 - < iterator 무효화와 해시 테이블 > — 이 글의 앞 편. 해시 테이블
- 이론 정리 - < 같은 O(N)인데 왜 속도가 다른가 > — 복잡도 표기와 상각 분석
- 이론 정리 - < RAII와 스마트 포인터 > — 순환 참조라는 같은 구조
- Python - < 5 > — 정렬 8종과 복잡도 비교
소감
1년 반 전 글을 이틀 사이에 두 번 열어보게 될 줄은 몰랐다. 고친 두 문장이 둘 다 조건을 빼먹은 것이라는 게 좀 뜨끔했는데, 반대로 보면 그때는 조건을 붙일 이유가 없었던 것 같기도 하다. 격자 미로만 풀고 있으면 가중치라는 게 존재하지도 않으니까.. BST가 정렬된 입력에서 최악이 되는 건 오늘 처음 봤는데, 깔끔하게 넣을수록 망가진다는 게 좀 얄궂어서 오래 기억에 남을 것 같다.