탐색 알고리즘
1. 탐색 알고리즘이란?
탐색(Search)은 주어진 데이터에서 원하는 값을 찾는 과정입니다.
예를 들어 다음과 같은 배열이 있다고 하겠습니다.
int arr[] = {10, 30, 20, 50, 40};여기서 50을 찾는 것이 탐색입니다.
탐색 알고리즘에서는 대표적으로 다음 두 가지를 배웁니다.
- 선형 탐색(Linear Search)
- 이진 탐색(Binary Search)
두 알고리즘의 가장 큰 차이는 데이터를 어떤 방식으로 확인하느냐입니다.
2. 선형 탐색(Linear Search)
선형 탐색은 가장 단순한 탐색 방법입니다.
처음부터 끝까지 데이터를 하나씩 확인합니다.
예를 들어 다음 배열에서 50을 찾는다고 하겠습니다.
[10, 30, 20, 50, 40]처음부터 하나씩 비교합니다.
10 → 30 → 20 → 5050을 발견하면 탐색을 종료합니다.
기본적인 형태
for (int i = 0; i < N; i++)
{
if (arr[i] == target)
{
return i;
}
}i를 이용하여 배열의 첫 번째 요소부터 마지막 요소까지 순서대로 확인합니다.
선형 탐색은 데이터가 정렬되어 있을 필요가 없습니다.
예를 들어:
[50, 10, 90, 20, 30]처럼 정렬되지 않은 데이터에서도 사용할 수 있습니다.
3. 선형 탐색의 시간 복잡도
선형 탐색은 데이터를 하나씩 확인하기 때문에 최악의 경우 모든 데이터를 확인해야 합니다.
예를 들어:
[10, 20, 30, 40, 50, 60, 70, 80]
↑
↑
↑
↑
↑
↑
↑
↑찾는 값이 마지막에 있다면 8개를 전부 확인해야 합니다.
데이터가 N개라면 최대 N번 정도 확인하게 됩니다.
따라서 시간 복잡도는:
O(N)
입니다.
즉 데이터의 크기가 커질수록 탐색에 필요한 작업도 데이터의 크기에 비례해서 증가합니다.
4. 이진 탐색(Binary Search)
이진 탐색은 선형 탐색보다 훨씬 효율적인 탐색 방법입니다.
이진 탐색의 핵심은:
탐색할 범위를 절반씩 줄여나간다.
입니다.
하지만 이진 탐색에는 매우 중요한 조건이 있습니다.
이진 탐색은 정렬된 데이터에서 사용해야 합니다.
예를 들어:
[10, 20, 30, 40, 50, 60, 70, 80]처럼 데이터가 정렬되어 있어야 합니다.
왜 정렬되어 있어야 할까요?
이진 탐색은 가운데 값을 확인한 다음, 찾는 값이 가운데 값보다 작은지 큰지를 이용하여 왼쪽 또는 오른쪽에 있는지를 판단하기 때문입니다.
5. 이진 탐색의 핵심 개념
이진 탐색에서는 반드시 다음 세 가지를 이해해야 합니다.
- left
- right
- mid
예를 들어 다음 배열이 있다고 하겠습니다.
[10, 20, 30, 40, 50, 60, 70, 80]
0 1 2 3 4 5 6 7처음에는 배열 전체를 탐색해야 합니다.
따라서:
left = 0;
right = 7;이 됩니다.
여기서 left와 right는 값이 아니라 인덱스입니다.
6. left란?
left는 현재 탐색 범위에서 가장 왼쪽에 있는 인덱스입니다.
예를 들어:
[10, 20, 30, 40, 50, 60, 70, 80]
↑
left처음에는 배열 전체를 탐색하므로:
left = 0;입니다.
탐색 범위가 줄어들면 left도 이동할 수 있습니다.
7. right란?
right는 현재 탐색 범위에서 가장 오른쪽에 있는 인덱스입니다.
처음에는 배열 전체를 탐색하므로:
right = 7;입니다.
즉:
[10, 20, 30, 40, 50, 60, 70, 80]
↑ ↑
left right현재 left ~ right 사이가 우리가 탐색해야 하는 범위입니다.
따라서:
left와 right는 현재 탐색 범위를 나타낸다.
라고 이해하면 됩니다.
8. mid란?
mid는 현재 탐색 범위의 가운데 인덱스입니다.
기본적인 계산 방법은 다음과 같습니다.
int mid = (left + right) / 2;예를 들어:
left = 0
right = 7이면:
mid = (0 + 7) / 2
= 3입니다.
따라서:
[10, 20, 30, 40, 50, 60, 70, 80]
0 1 2 3 4 5 6 7
↑
midarr[3]인 40을 확인하게 됩니다.
9. mid를 안전하게 계산하는 방법
C++에서는 다음과 같이 작성하는 것도 좋습니다.
int mid = left + (right - left) / 2;일반적인 상황에서는:
(left + right) / 2와 같은 결과를 냅니다.
하지만 left + right가 매우 큰 경우 정수 오버플로가 발생할 가능성이 있기 때문에 다음 방식이 더 안전합니다.
int mid = left + (right - left) / 2;알고리즘 문제에서는 이 형태를 자주 볼 수 있습니다.
10. 이진 탐색 과정
찾고 싶은 값이 70이라고 하겠습니다.
배열:
[10, 20, 30, 40, 50, 60, 70, 80]
0 1 2 3 4 5 6 7처음에는:
left = 0
right = 7
mid = 3입니다.
따라서:
arr[mid] = 40
target = 70을 비교합니다.
40 < 70입니다.
그러면 70은 어디에 있을까요?
데이터가 정렬되어 있기 때문에 40보다 작은 왼쪽 영역에는 70이 있을 수 없습니다.
따라서 왼쪽 영역을 버립니다.
[10, 20, 30, 40] [50, 60, 70, 80]
↑ ↑
left right이때:
left = mid + 1;을 수행합니다.
결과:
left = 4
right = 711. 다시 mid를 계산
현재 탐색 범위는:
left = 4
right = 7입니다.
다시:
mid = left + (right - left) / 2;를 계산하면:
mid = 5입니다.
따라서:
[10, 20, 30, 40, 50, 60, 70, 80]
↑
midarr[5] = 60입니다.
다시:
60 < 70이므로 70은 오른쪽에 있습니다.
따라서:
left = mid + 1;결과:
left = 6
right = 7이 됩니다.
12. 다시 mid를 계산
이번에는:
left = 6
right = 7입니다.
mid = left + (right - left) / 2;를 계산하면:
mid = 6입니다.
따라서:
arr[6] = 70이고:
arr[mid] == target이므로 값을 찾았습니다.
13. 이진 탐색의 전체 과정
결국 이진 탐색은 다음 과정을 반복합니다.
1. 탐색 범위를 설정한다.
↓
2. left와 right로 범위를 표현한다.
↓
3. mid를 계산한다.
↓
4. arr[mid]를 확인한다.
↓
5. target과 비교한다.
↓
6. target이 왼쪽에 있으면 right를 이동한다.
target이 오른쪽에 있으면 left를 이동한다.
↓
7. 탐색 범위를 절반으로 줄인다.
↓
8. 다시 mid를 계산한다.
↓
9. 값을 찾을 때까지 반복한다.14. target이 오른쪽에 있는 경우
다음 상황을 생각해 봅니다.
arr[mid] < target현재 가운데 값보다 target이 더 큽니다.
데이터가 오름차순으로 정렬되어 있기 때문에 target은 가운데보다 오른쪽에 있습니다.
따라서:
left = mid + 1;을 사용합니다.
즉:
왼쪽 부분 → 버림
mid → 이미 확인했으므로 버림
오른쪽 부분 → 탐색입니다.
15. target이 왼쪽에 있는 경우
이번에는:
arr[mid] > target이라고 하겠습니다.
현재 가운데 값보다 target이 더 작습니다.
정렬되어 있기 때문에 target은 가운데보다 왼쪽에 있습니다.
따라서:
right = mid - 1;을 사용합니다.
즉:
왼쪽 부분 → 탐색
mid → 이미 확인했으므로 버림
오른쪽 부분 → 버림입니다.
16. 왜 mid + 1, mid - 1인가?
이 부분은 이진 탐색에서 자주 실수하는 부분입니다.
예를 들어:
left = 0
mid = 3
right = 7이고:
arr[mid] < target이라면 mid에 있는 값은 이미 확인했습니다.
그리고 target이 아니기 때문에 mid를 다시 탐색할 필요가 없습니다.
따라서:
left = mid + 1;이 됩니다.
반대로:
arr[mid] > target이면 mid는 이미 확인했으므로:
right = mid - 1;이 됩니다.
따라서 기본적인 이진 탐색에서는:
left = mid + 1;
right = mid - 1;이 중요한 형태가 됩니다.
17. 이진 탐색 기본 코드
int BinarySearch(const vector<int>& arr, int target)
{
int left = 0;
int right = arr.size() - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (arr[mid] == target)
{
return mid;
}
else if (arr[mid] < target)
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
return -1;
}18. 코드 한 줄씩 이해하기
함수 선언
int BinarySearch(const vector<int>& arr, int target)이진 탐색 함수입니다.
- arr → 탐색할 배열
- target → 찾고 싶은 값
- int → 찾은 값의 인덱스를 반환
const vector<int>&는 배열의 데이터를 복사하지 않고 참조하면서, 함수 내부에서 배열을 변경하지 않겠다는 의미입니다.
탐색 시작점
int left = 0;배열의 첫 번째 인덱스에서 시작합니다.
탐색 끝점
int right = arr.size() - 1;배열의 마지막 인덱스를 의미합니다.
예를 들어 데이터가 8개라면 인덱스는:
0 1 2 3 4 5 6 7이므로:
right = 7입니다.
탐색 범위가 존재하는 동안 반복
while (left <= right)left가 right보다 작거나 같은 동안 탐색합니다.
예를 들어:
left = 3
right = 5이면 아직 탐색할 범위가 있습니다.
하지만:
left = 6
right = 5라면 탐색 범위가 없습니다.
따라서 반복문이 종료됩니다.
가운데 위치 계산
int mid = left + (right - left) / 2;현재 탐색 범위의 가운데 인덱스를 계산합니다.
값을 찾았는지 확인
if (arr[mid] == target)
{
return mid;
}가운데 값이 target과 같다면 값을 찾은 것입니다.
따라서 해당 값의 인덱스를 반환합니다.
오른쪽을 탐색
else if (arr[mid] < target)
{
left = mid + 1;
}가운데 값이 target보다 작다면 target은 오른쪽에 있습니다.
따라서 탐색 범위를:
mid + 1 ~ right로 변경합니다.
왼쪽을 탐색
else
{
right = mid - 1;
}가운데 값이 target보다 크다면 target은 왼쪽에 있습니다.
따라서 탐색 범위를:
left ~ mid - 1로 변경합니다.
값을 찾지 못한 경우
return -1;탐색 범위가 모두 사라질 때까지 target을 찾지 못했다면 일반적으로 -1을 반환하여 값이 존재하지 않는다는 것을 나타냅니다.
19. 왜 이진 탐색은 O(log N)인가?
이진 탐색의 핵심은 매번 탐색 범위를 절반으로 줄이는 것입니다.
데이터가 8개라면:
8
↓
4
↓
2
↓
1데이터가 16개라면:
16
↓
8
↓
4
↓
2
↓
1데이터가 32개라면:
32
↓
16
↓
8
↓
4
↓
2
↓
1이처럼 데이터가 아무리 커져도 한 번 탐색할 때마다 절반을 제거합니다.
그래서 시간 복잡도는:
O(log N)
입니다.
20. O(N)과 O(log N)의 차이
두 알고리즘의 차이를 비교하면 다음과 같습니다.
데이터 크기선형 탐색 O(N)이진 탐색 O(log N)
| 10 | 최대 약 10번 | 약 4번 |
| 100 | 최대 약 100번 | 약 7번 |
| 1,000 | 최대 약 1,000번 | 약 10번 |
| 10,000 | 최대 약 10,000번 | 약 14번 |
| 1,000,000 | 최대 약 1,000,000번 | 약 20번 |
정확한 비교 횟수는 구현 방식과 상황에 따라 조금 달라질 수 있지만 중요한 것은 증가하는 속도입니다.
선형 탐색은 데이터가 10배가 되면 탐색량도 대략 10배 증가합니다.
반면 이진 탐색은 데이터가 2배가 되어도 탐색 단계가 약 1단계 증가하는 정도입니다.
21. 이진 탐색은 무조건 좋은가?
그렇지는 않습니다.
이진 탐색은 정렬된 데이터가 필요하다는 조건이 있습니다.
예를 들어:
[50, 10, 80, 20, 40]이런 데이터에서는 가운데 값을 확인하더라도 target이 왼쪽에 있는지 오른쪽에 있는지 판단할 수 없습니다.
따라서 정렬되지 않은 데이터에서는 일반적인 이진 탐색을 사용할 수 없습니다.
정렬되지 않은 데이터
↓
선형 탐색반면:
정렬된 데이터
↓
이진 탐색 사용 가능입니다.
22. 정렬 비용도 고려해야 한다
정렬되지 않은 데이터를 이진 탐색하고 싶다면 먼저 정렬해야 합니다.
정렬되지 않은 데이터
↓
정렬
↓
정렬된 데이터
↓
이진 탐색따라서 데이터를 한 번만 찾는 상황이라면 정렬하는 비용까지 생각해야 합니다.
반면:
정렬
↓
탐색
탐색
탐색
탐색
탐색
...처럼 같은 데이터를 여러 번 탐색한다면 처음 정렬한 뒤 이진 탐색을 반복하는 것이 매우 효율적일 수 있습니다.
따라서 알고리즘 문제에서 다음 질문을 하는 것이 중요합니다.
"데이터가 정렬되어 있는가?"
23. 선형 탐색 vs 이진 탐색
구분선형 탐색이진 탐색
| 영어 | Linear Search | Binary Search |
| 탐색 방식 | 처음부터 하나씩 확인 | 가운데를 확인하고 범위를 절반으로 줄임 |
| 정렬 필요 | 필요 없음 | 필요함 |
| 탐색 범위 | 한 칸씩 이동 | 절반씩 제거 |
| 시간 복잡도 | O(N) | O(log N) |
| 구현 난이도 | 쉬움 | 상대적으로 어려움 |
| 핵심 | 순서대로 확인 | left, right, mid |
| 장점 | 어떤 데이터에서도 사용 가능 | 정렬된 데이터에서 매우 빠름 |
| 단점 | 데이터가 많으면 느려짐 | 정렬된 데이터가 필요함 |
24. 이진 탐색과 탐색 범위
이진 탐색을 이해할 때 가장 중요한 개념 중 하나가 탐색 범위입니다.
처음에는:
[10, 20, 30, 40, 50, 60, 70, 80]
↑ ↑
left right전체 배열이 탐색 범위입니다.
가운데를 확인하고 왼쪽을 버렸다면:
[10, 20, 30, 40] [50, 60, 70, 80]
↑ ↑
left right탐색 범위가 줄어듭니다.
다시 가운데를 확인하고 일부를 버리면:
[50, 60] [70, 80]
↑ ↑
left right또 줄어듭니다.
결국:
전체
↓
절반
↓
절반
↓
절반
↓
...이 되는 것입니다.
따라서 이진 탐색을 볼 때는 단순히 mid만 보는 것이 아니라:
"현재 탐색 범위가 어디부터 어디까지인가?"
를 항상 생각해야 합니다.
25. 재귀와 이진 탐색의 연결
앞에서 배운 재귀와 이진 탐색도 연결됩니다.
이진 탐색은 매번 문제의 크기를 절반으로 줄입니다.
전체 범위
↓
절반
↓
절반
↓
절반
↓
...이러한 방식은 분할 정복(Divide and Conquer) 사고방식과 연결됩니다.
재귀적인 형태로 생각하면:
현재 범위에서 mid 확인
↓
target이 있는 쪽만 선택
↓
선택한 범위에서 다시 이진 탐색
↓
반복처럼 생각할 수 있습니다.
다만 실제 알고리즘 문제에서는 이진 탐색을 while 반복문으로 구현하는 경우도 매우 많습니다.
26. 이진 탐색에서 자주 하는 실수
① 정렬되지 않은 데이터에 사용
[50, 10, 30, 20, 40]이런 데이터에는 일반적인 이진 탐색을 사용할 수 없습니다.
먼저 정렬되어 있어야 합니다.
② left와 right를 값으로 생각
left = 0;
right = 7;여기서 0, 7은 데이터의 값이 아니라 인덱스입니다.
③ mid를 잘못 계산
기본적인 방법:
int mid = (left + right) / 2;안전한 방법:
int mid = left + (right - left) / 2;④ 탐색 범위를 잘못 줄임
다음처럼 작성하면 문제가 생길 수 있습니다.
left = mid;right = mid;이미 확인한 mid를 다시 탐색하게 될 수 있기 때문에 같은 위치를 반복해서 확인하는 상황이 발생할 수 있습니다.
기본적인 정확한 값 찾기에서는:
left = mid + 1;right = mid - 1;형태를 사용합니다.
⑤ 종료 조건을 헷갈림
일반적인 이진 탐색에서는:
while (left <= right)를 사용합니다.
left > right가 되었다는 것은 현재 탐색 범위가 완전히 사라졌다는 의미입니다.
즉:
left > right
↓
탐색할 데이터가 없음
↓
탐색 실패입니다.
27. 알고리즘 문제에서의 사고 순서
탐색 문제가 나왔을 때 다음 순서로 생각하면 좋습니다.
1. 무엇을 찾는가?
target찾고 싶은 값이 무엇인지 확인합니다.
2. 데이터가 정렬되어 있는가?
정렬되지 않음
↓
선형 탐색 고려
정렬되어 있음
↓
이진 탐색 고려3. 이진 탐색이라면 탐색 범위를 잡는다.
left = 시작 인덱스
right = 마지막 인덱스4. 가운데를 구한다.
mid = left + (right - left) / 25. 가운데 값을 확인한다.
arr[mid]6. target과 비교한다.
arr[mid] == target이면 찾은 것입니다.
arr[mid] < target이면 target은 오른쪽에 있습니다.
left = mid + 1;arr[mid] > target이면 target은 왼쪽에 있습니다.
right = mid - 1;7. 범위가 없어질 때까지 반복한다.
while (left <= right)28. 이번 단계 핵심 정리
선형 탐색
처음부터 끝까지 하나씩 확인
↓
정렬 필요 없음
↓
O(N)선형 탐색은 구현이 쉽고 정렬되지 않은 데이터에서도 사용할 수 있지만, 데이터가 많아질수록 탐색해야 하는 데이터가 많아집니다.
이진 탐색
정렬된 데이터
↓
탐색 범위 설정
↓
left / right
↓
mid 계산
↓
target과 비교
↓
왼쪽 또는 오른쪽 절반 제거
↓
남은 범위에서 반복
↓
O(log N)이진 탐색은 정렬된 데이터라는 조건이 필요하지만, 탐색 범위를 매번 절반으로 줄이기 때문에 매우 빠릅니다.
29. 반드시 연결해서 기억할 것
이번 6단계에서 가장 중요한 연결 관계는 다음과 같습니다.
정렬되지 않은 데이터
↓
선형 탐색
↓
하나씩 확인
↓
O(N)그리고:
정렬된 데이터
↓
이진 탐색
↓
탐색 범위 설정
↓
left / right
↓
mid
↓
target 비교
↓
절반 제거
↓
O(log N)특히 다음 문장은 확실하게 기억해두는 것이 좋습니다.
이진 탐색은 정렬된 데이터에서 left ~ right라는 탐색 범위를 정하고, mid를 기준으로 target과 비교하여 탐색 범위를 절반씩 줄여나가는 알고리즘이다.
30. 앞에서 배운 내용과의 연결
지금까지 배운 내용을 연결하면 다음과 같습니다.
배열
↓
인덱스를 이용하여 데이터에 접근
↓
선형 탐색
↓
정렬된 배열
↓
탐색 범위
↓
left / right
↓
mid
↓
이진 탐색
↓
O(log N)그리고 이전에 배운 재귀와도 연결됩니다.
재귀
↓
문제를 작은 문제로 나눔
↓
이진 탐색
↓
탐색 범위를 절반으로 줄임
↓
분할 정복 사고방식따라서 이번 단계에서 단순히 "이진 탐색은 O(log N)"만 외우는 것보다,
정렬된 데이터 → 탐색 범위 → left와 right → mid → 비교 → 절반 제거 → O(log N)
이라는 흐름을 하나의 과정으로 이해하는 것이 중요