2026-06-10 TIL (73일차)
알고리즘: lower_bound 와 upper_bound
C++ <algorithm> 라이브러리에서 제공하는 lower_bound와 upper_bound는 이진 탐색(Binary Search)을 기반으로 배열에서 특정 값을 찾는 함수입니다.
직접 이진 탐색을 구현하지 않아도 단 한 줄로 특정 데이터의 위치나 개수를 파악할 수 있어 코딩 테스트에서 사용됩니다.
전제 조건
두 함수 모두 이진 탐색을 기반으로 동작하므로, 탐색할 배열(또는 벡터)이 반드시 오름차순으로 “정렬(Sorted)”되어 있어야 합니다. (시간 복잡도: O(log N))
1. lower_bound (하한선)
- 정의: 찾고자 하는 값(Target) 이상(>=)의 값이 처음으로 나타나는 위치를 반환합니다.
- 사용 목적: “이 데이터가 들어갈 수 있는 가장 왼쪽 위치는 어디인가?”를 찾을 때 사용합니다.
2. upper_bound (상한선)
- 정의: 찾고자 하는 값(Target)을 초과(>)하는 값이 처음으로 나타나는 위치를 반환합니다.
- 사용 목적: “이 데이터가 들어갈 수 있는 가장 오른쪽 위치는 어디인가?”를 찾을 때 사용합니다.
예시
정렬된 배열 A = [1, 2, 4, 4, 4, 6, 8] 이 있고, 타겟 값이 4라고 가정해 봅시다.
lower_bound(4):4와 같거나 큰 값이 처음 나오는 위치 👉 인덱스 2 (첫 번째 4의 위치)upper_bound(4):4보다 엄격하게 큰 값이 처음 나오는 위치 👉 인덱스 5 (6의 위치)
실전 활용 (특정 값의 개수 구하기) 타겟 값
4의 개수를 알고 싶다면?upper_bound 인덱스(5)-lower_bound 인덱스(2)= 3개 배열 안에 4가 3개 들어있다는 것을 반복문 없이 O(log N) 만에 구해낼 수 있습니다!
C++ 코드 사용법 및 주의사항
두 함수는 인덱스(int)가 아니라 반복자(Iterator, 포인터와 유사)를 반환합니다. 따라서 실제 인덱스 번호를 정수로 얻으려면 벡터의 첫 번째 주소인 v.begin()(배열의 경우 배열 이름)을 빼주어야 합니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <vector>
#include <algorithm> // lower_bound, upper_bound, sort 사용
using namespace std;
int main() {
vector<int> v = {1, 2, 4, 4, 4, 6, 8};
// 이진 탐색 함수들을 사용하기 전 반드시 정렬! (이미 정렬되어 있다면 생략 가능)
sort(v.begin(), v.end());
int target = 4;
// 1. lower_bound 사용법
// v.begin()을 빼주어야 실제 인덱스(정수) 값을 얻을 수 있습니다.
int lower_idx = lower_bound(v.begin(), v.end(), target) - v.begin();
// 2. upper_bound 사용법
int upper_idx = upper_bound(v.begin(), v.end(), target) - v.begin();
cout << "target(" << target << ") 이상이 처음 나타나는 위치(lower): 인덱스 " << lower_idx << "\n";
cout << "target(" << target << ") 초과가 처음 나타나는 위치(upper): 인덱스 " << upper_idx << "\n";
// 3. 특정 구간의 데이터 개수 구하기
cout << "배열 내 " << target << "의 개수: " << upper_idx - lower_idx << "개\n";
return 0;
}
[출력 결과]
1
2
3
target(4) 이상이 처음 나타나는 위치(lower): 인덱스 2
target(4) 초과가 처음 나타나는 위치(upper): 인덱스 5
배열 내 4의 개수: 3개
요약 (C++)
C++ 함수명 (<algorithm>) | 찾는 기준 | 조건식 | 반환 형태 |
|---|---|---|---|
lower_bound | 타겟 이상의 값이 처음 나오는 위치 | Value >= Target | 해당 위치의 반복자(Iterator) |
upper_bound | 타겟 초과의 값이 처음 나오는 위치 | Value > Target | 해당 위치의 반복자(Iterator) |
※ 주의: 두 함수 모두 반복자(Iterator)를 반환하므로, 배열이나 벡터의 실제 인덱스(정수)를 구하려면 반환값에서 시작 주소(예:
v.begin())를 빼주어야 합니다.
이진 탐색(Binary Search)의 함정: 정수 오버플로우 방지 원리
이진 탐색 알고리즘을 구현할 때, 탐색 범위를 반으로 나누기 위해 중간 인덱스(mid)를 구해야 합니다. 이때 무심코 작성하는 코드 한 줄에 버그가 숨어있을 수 있습니다.
1. 왜 (left + right) / 2는 위험할까?
일반적으로 가장 많이 떠올리는 중간값 계산 공식은 다음과 같습니다.
1
int mid = (left + right) / 2; // 위험한 코드
값은 약 21억(2,147,483,647)입니다. 만약 배열의 크기가 매우 커서 left와 right가 각각 15억이라고 가정해 봅시다.
left + right = 15억 + 15억 = 30억 30억은 int의 최댓값(21억)을 초과하므로 정수 오버플로우(Integer Overflow)가 발생합니다. 그 결과, 컴퓨터는 30억을 인식하지 못하고 이상한 음수 값(예: -12억)으로 변환해 버립니다. 이 음수를 2로 나누면 mid는 결국 음수가 되고, 배열의 인덱스로 접근할 때 IndexOutOfBoundsException 같은 에러를 발생시키며 프로그램이 터지게 됩니다.
2. left + (right - left) / 2는 왜 안전할까?
이 문제를 해결하기 위한 안전한 코드는 다음과 같습니다.
1
int mid = left + (right - left) / 2; // 오버플로우 방지 (안전한 코드)
이 코드가 안전한 이유는 ‘덧셈 연산을 먼저 하지 않고, 거리(차이)를 먼저 구하기 때문’입니다.
동작 원리 (거리 개념 적용)
- (right - left): left부터 right까지의 ‘거리’를 먼저 구합니다. right가 아무리 큰 21억 이하의 숫자라도, 그보다 작은 left를 빼기 때문에 이 값은 절대 int의 최댓값을 넘지 않는 안전한 양수가 됩니다.
- / 2: 구한 거리를 반으로 나눕니다. 즉, left와 right 사이의 ‘절반 거리’를 구합니다.
- left +: 시작점인 left에서 방금 구한 ‘절반 거리’만큼만 앞으로 전진합니다.
결과적으로 최종 위치(mid)는 무조건 right보다 작거나 같으므로, int 범위를 절대 초과하지 않으면서도 정확히 중간 지점을 가리키게 됩니다.
3. 요약 및 교훈
- 수학적으로는 동일하지만, 컴퓨터 구조상으로는 완전히 다르다!
- 수학 공식: $\frac{L + R}{2} = L + \frac{R - L}{2}$
- 수학적으로는 위 두 식이 완전히 똑같은 결과를 냅니다. 하지만, 컴퓨터의 메모리(자료형 크기 제한) 공간 안에서는 덧셈(L + R)이 먼저 발생하는 순간 한계치를 뚫고 나가버릴 위험이 있습니다.
결론: 이진 탐색을 비롯해 매우 큰 수의 중간값을 구할 때는 항상 시작점에 절반 거리를 더하는 방식(left + (right - left) / 2)을 사용하는 습관을 들여야 합니다.
B-Tree와 데이터베이스 인덱스의 원리
1. B-Tree: 이진 탐색의 진화
실제 데이터베이스(DB)에서는 단순한 이진 트리(Binary Tree)가 아닌 B-Tree 자료구조를 사용합니다.
- 구조적 특징: 하나의 노드에 하나의 Key만 갖는 이진 트리와 달리, 하나의 노드에 여러 개의 Key를 저장하고 여러 갈래로 분기하는 형태를 띱니다.
- 압도적인 검색 속도: “해리포터(H)”를 검색한다고 가정할 때,
M보다 앞 ➡️ D~H 범위 ➡️ H 발견과 같이 100만 건의 데이터 중에서도 단 3단계 만에 데이터를 찾아낼 수 있습니다.
2. 왜 이진 트리가 아니라 ‘B-Tree’를 사용할까?
기본적인 이진 탐색의 원리(반으로 나누어 탐색)는 같지만, 하드웨어(디스크)의 물리적 특성에 맞게 진화한 결과입니다.
- 이진 트리의 한계: 노드를 하나씩 따라갈 때마다 매번 디스크 I/O(입출력)가 발생하여 물리적인 탐색 속도가 매우 느려집니다.
- 디스크 I/O 효율성: 하드디스크에서 데이터를 읽을 때는 여러 번 조금씩 읽는 것보다 “한 번에 많이 읽어오는 것”이 훨씬 효율적입니다.
- B-Tree의 장점: 노드 하나에 여러 Key를 블록 단위로 모아두기 때문에 디스크 I/O 발생 횟수를 획기적으로 최소화할 수 있습니다.
참고: MySQL, PostgreSQL, Oracle 등 거의 모든 관계형 DB의 인덱스(Index)는 이 B-Tree(또는 변형 구조)를 사용합니다. 우리가
SELECT쿼리를 날릴 때마다 내부에서는 이진 탐색의 후예가 열심히 일하고 있는 것입니다.
3. 트레이드오프 (Trade-off): 정렬의 비용 vs 검색의 이익
인덱스를 생성하는 것은 마법이 아닙니다. ‘검색 속도’를 얻는 대신, 데이터를 ‘삽입/갱신하는 비용’과 ‘저장 공간’을 지불하는 구조입니다.
| 항목 | 인덱스 없음 | 인덱스 있음 |
|---|---|---|
| 검색 (Search) | O(n) (느림) | O(log n) (빠름) |
| 삽입 (Insert) | O(1) (빠름) | O(log n) (느림, 인덱스 갱신 비용 발생) |
| 저장 공간 (Space) | 데이터만 보관 | 데이터 + 인덱스 저장 공간 추가 |
결론: 왜 인덱스 도입이 표준일까?
대부분의 서비스에서는 데이터를 쓰고 수정하는 일보다, 조회하고 검색하는 일이 압도적으로 빈번하게 발생합니다. 따라서 데이터를 기록할 때 속도가 조금 느려지더라도, “정렬에 투자하여 탐색 속도를 비약적으로 끌어올리는 것”이 전체 시스템 성능에 훨씬 이득이 됩니다.
완전 탐색: 순열, 조합, 부분집합
알고리즘 문제를 풀다 보면 “모든 경우의 수를 다 확인해봐야겠다!”라고 생각할 때가 있습니다. 이것을 완전 탐색(Brute Force)이라고 부릅니다.
그렇다면 완전 탐색을 구현할 때 왜 항상 순열, 조합, 부분집합이 등장할까요? 그리고 이들의 결정적인 차이는 무엇일까요?
1. 왜 완전 탐색에서 이 3가지를 사용할까?
완전 탐색의 핵심은 “단 하나도 빠짐없이, 그리고 중복 없이 모든 경우를 만들어 내는 것”입니다.
문제를 풀 때 우리가 마주하는 상황은 결국 다음 세 가지 중 하나로 귀결됩니다.
- “이 숫자들을 어떤 순서로 나열해야 최적일까?” 👉 순열
- “이 중에서 몇 개를 뽑아야 조건에 맞을까?” 👉 조합
- “각 아이템을 포함할까 말까?” 👉 부분집합
즉, 순열, 조합, 부분집합은 ‘모든 경우의 수를 체계적으로 만들어내는 가장 완벽한 수학적 도구(틀)’이기 때문에 완전 탐색의 핵심 뼈대로 사용되는 것입니다.
2. 순열 vs 조합: “순서가 다르면 다른 것인가?”
순열과 조합을 헷갈리게 만드는 가장 큰 원인은 ‘순서(Order)’의 개념입니다. 이것만 기억하세요.
- 순열 (Permutation): 순서가 다르면 ‘다른 경우’로 취급합니다.
- 조합 (Combination): 순서가 달라도 구성품이 같으면 ‘같은 경우’로 취급합니다.
직관적인 예시: 반장 선거 vs 청소 당번
A, B, C 3명의 학생 중 2명을 뽑는다고 가정해 봅시다.
1. 순열 (순서 O) - “반장 1명, 부반장 1명 뽑기”
- [A 반장, B 부반장]과 [B 반장, A 부반장]은 완전히 다른 결과입니다.
- 나오는 경우의 수:
(A,B),(A,C),(B,A),(B,C),(C,A),(C,B)👉 총 6가지 - 코딩 테스트 적용: “비밀번호 자물쇠 풀기”, “최단 경로 방문 순서 정하기”
2. 조합 (순서 X) - “청소 당번 2명 뽑기”
- [A, B 청소]나 [B, A 청소]나 결국 청소하는 사람은 A와 B로 똑같습니다. (순서 무시)
- 나오는 경우의 수:
(A,B),(A,C),(B,C)👉 총 3가지 - 코딩 테스트 적용: “로또 번호 고르기”, “팀 나누기”
3. 3대장 상세 분석
① 순열 (Permutation)
서로 다른 $n$개에서 $r$개를 선택하여 순서대로 나열하는 경우의 수입니다.
- 기호: $_n\mathrm{P}_r$
- 수식: $_n\mathrm{P}_r = \frac{n!}{(n-r)!}$
- 특징:
[1, 2, 3]과[1, 3, 2]를 다른 것으로 셉니다.
② 조합 (Combination)
서로 다른 $n$개에서 순서를 생각하지 않고 $r$개를 선택만 하는 경우의 수입니다.
- 기호: $_n\mathrm{C}_r$
- 수식: $_n\mathrm{C}_r = \frac{n!}{r!(n-r)!}$
- 특징:
[1, 2, 3]과[1, 3, 2]를 같은 것으로 치고 하나만 남깁니다.
③ 부분집합 (Subset)
어떤 집합의 원소들로 만들 수 있는 모든 집합입니다.
- 원리: 각 원소 입장에서 “들어간다(O)” 또는 “안 들어간다(X)” 2가지 선택지가 있습니다.
- 경우의 수: 원소가 $n$개일 때, $2^n$가지
- 특징: 조합의 확장판입니다. 원소를 0개 뽑는 조합부터 $n$개 전부 뽑는 조합까지 모두 더한 것과 같습니다.
- 코딩 테스트 적용: “가방에 물건을 넣을지 말지 결정하기(배낭 문제)”, “특정 조건을 만족하는 그룹 찾기”
4. 한눈에 보는 요약 표
| 구분 | 개념 | 순서 중요도 | 예시 | 경우의 수 (n=3, r=2) |
|---|---|---|---|---|
| 순열 (Permutation) | n개 중 r개를 순서대로 나열 | 중요함 (O) | 비밀번호 생성 | 6 (3 * 2) |
| 조합 (Combination) | n개 중 r개를 순서 없이 선택 | 안 중요함 (X) | 로또 번호 뽑기 | 3 (6 / 2!) |
| 부분집합 (Subset) | 집합의 원소로 만들 수 있는 모든 경우 | - | 햄버거 토핑(넣기/빼기) | 8 ($2^3$) |
요약: 문제를 읽었을 때 “순서가 결과에 영향을 미치는가?”를 먼저 고민하세요. 순서가 영향을 미치면 순열, 단순히 뽑기만 하면 되면 조합, 넣을지 말지 각각 결정해야 하면 부분집합 알고리즘(주로 재귀/백트래킹)을 설계하면 됩니다!
백트래킹(Backtracking): 완전 탐색 + 가지치기
1. 백트래킹의 핵심 요약
강의 슬라이드에서 강조하는 백트래킹의 4가지 핵심 포인트는 다음과 같습니다.
- 원리:
완전 탐색 + 가지치기(Pruning) - 유망성 판단(Promising): “현재 경로로 계속 진행했을 때 정답이 나올 가능성이 있는가?”를 묻는 과정.
- 코드 패턴:
선택➡️검증➡️재귀➡️되돌림(상태 복구) - 효과: 무식하게 모든 경우를 다 찾는 완전 탐색 대비 탐색량을 획기적으로 절감할 수 있습니다.
2. 백트래킹이란? (완전 탐색과의 관계)
- 완전 탐색 (Exhaustive Search / Brute Force): “모든 경우의 수를 전부 다 확인해보자!”는 접근입니다. 순열, 조합, 부분집합 등이 여기에 속합니다. 확실하게 답을 찾을 수 있지만, 경우의 수가 많아지면 시간이 너무 오래 걸린다는 치명적인 단점이 있습니다.
- 백트래킹 (Backtracking): 완전 탐색을 기반으로 하되, 탐색하는 도중에 “어? 이 길은 끝까지 가봐야 정답이 아니겠는데?” 싶으면 과감하게 포기하고 뒤로 돌아가는(Back-track) 기법입니다.
👉 즉, 백트래킹은 똑똑한 완전 탐색입니다. 쓸데없는 경로를 미리 차단(가지치기)하여 실행 시간을 대폭 줄이는 것이 목적입니다.
3. 어떻게 ‘건너뛰는가’? (가지치기와 유망성 판단 코드)
질문해주신 “필요 없다고 판단되는 곳을 어떻게 건너뛰는지”는 백트래킹 코드의 핵심입니다. 주로 if 조건문과 continue 또는 return을 사용하여 유망하지 않은(Not Promising) 경우 재귀 호출을 아예 실행하지 않고 스킵합니다.
아래의 C++ 표준 백트래킹 코드 템플릿을 확인해 보세요.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <vector>
using namespace std;
// 전역 변수 설정 (예시)
int target_depth = 3;
int options_count = 5;
// 유망성 판단 함수 (조건에 맞는지 검사)
bool isValid(int i, const vector<int>& path) {
// 여기에 조건 로직 구현
// 예: 이미 방문한 숫자인지 확인, 특정 조건 불만족 시 false 반환 등
return true;
}
// 정답을 저장하거나 출력하는 함수
void saveAnswer(const vector<int>& path) {
for (int num : path) {
cout << num << " ";
}
cout << "\n";
}
// 백트래킹 핵심 함수
void backtrack(int depth, vector<int>& path) {
// 1. 종료 조건: 원하는 깊이나 조건에 도달하여 정답을 찾은 경우
if (depth == target_depth) {
saveAnswer(path);
return;
}
// 2. 가능한 모든 경우의 수 탐색
for (int i = 0; i < options_count; i++) {
// [핵심] 유망성 판단 (Promising) 및 가지치기 (Pruning)
// 만약 'i'를 선택하는 것이 조건에 위배된다면?
if (!isValid(i, path)) {
continue; // 재귀를 타지 않고 다음 선택지로 바로 건너뜁니다! (가지치기)
}
// 3. 선택 -> 검증 -> 재귀 -> 되돌림 패턴
path.push_back(i); // [선택] 현재 값을 경로에 추가
backtrack(depth + 1, path); // [재귀] 다음 단계로 깊이 탐색 진행
path.pop_back(); // [되돌림] 탐색을 마치고 돌아오면 다음 경우의 수를 위해 원상 복구!
}
}
int main() {
vector<int> current_path;
// 백트래킹 시작 (깊이 0부터)
backtrack(0, current_path);
return 0;
}
[건너뛰는 원리 상세 설명] 위 코드에서 isValid(i, path) 함수가 현재 선택(i)이 유효한지 검사합니다. 만약 유효하지 않다면(가망이 없다면) continue를 만나 아래의 재귀 함수(backtrack(depth + 1, path))를 호출하지 않습니다. 이로 인해 해당 선택지 아래로 뻗어 나갈 수 있었던 수만 개의 파생 경우의 수가 단 한 번의 continue로 모두 잘려 나갑니다. 이것이 바로 ‘가지치기(Pruning)’의 위력입니다.
4. 백트래킹의 3단계 패턴과 실제 코드 구현의 차이 (최적화 팁)
강의 등에서 백트래킹의 핵심 패턴을 보통 ① 선택 ➡️ ② 검증 ➡️ ↻ 재귀 ➡️ ③ 되돌림 순서로 배웁니다. 하지만 위의 실제 C++ 코드를 보면 순서가 살짝 다릅니다.
[패턴과 실제 코드의 매칭]
- ② 검증 (Check):
if (!isValid(i, path)) { continue; } - ① 선택 (Choose):
path.push_back(i); - ↻ 재귀 (Recurse):
backtrack(depth + 1, path); - ③ 되돌림 (Un-choose):
path.pop_back();
팁: 왜 실제 코드에서는 ‘검증’을 ‘선택’보다 먼저 할까?
개념적으로는 ‘선택하고 검증한다’가 자연스럽지만, 실제 코딩 테스트용 코드를 짤 때는 위처럼 ② 검증 ➡️ ① 선택 순서로 작성하는 것이 훨씬 안전하고 효율적입니다.
- 이유: 만약
선택(push_back)을 먼저 하고검증(isValid)을 해서 가망이 없다고continue로 넘겨버리면, 마지막에되돌림(pop_back)을 하지 않고 반복문이 다음으로 넘어가 버려서 배열에 쓰레기값이 계속 쌓이는 버그가 발생할 수 있습니다. - 따라서, “일단 검증해서 통과한 유망한 녀석들만(Check), 배열에 넣고(Choose), 재귀 돌리고(Recurse), 다시 뺀다(Un-choose)” 순서로 구현하는 것이 정석이자 가장 깔끔한 방법입니다. 개념적인 흐름과 본질적인 원리는 100% 동일합니다!
5. 코딩 테스트에서 백트래킹이 자주 나오는 유형
백트래킹은 보통 주어진 제한 조건이 매우 까다로운 완전 탐색 문제에서 주로 사용됩니다. (보통 DFS 기반으로 구현합니다.)
- N-Queen 문제: 체스판 위에 N개의 퀸을 서로 공격할 수 없게 배치하는 문제 (가장 대표적인 백트래킹 예제).
- 스도쿠(Sudoku) 풀기: 빈칸에 1~9 숫자를 넣어보면서, 가로/세로/네모 조건에 안 맞으면 바로 되돌아가는 문제.
- 조건이 붙은 순열/조합: “N개의 숫자 중 M개를 고르는데, 연속된 숫자는 고를 수 없다” 같은 제약 조건이 추가된 경우.
- 미로 찾기 / 경로 탐색: 목적지로 가는 도중 벽에 막히거나 이미 방문한 곳이면 더 이상 가지 않고 돌아오는 경우.