문제 소개
이번 튜토리얼에서는 다음과 같은 문제를 함께 해결해 보겠습니다.
주어진 배열에서 인덱스와 값이 동일한 숫자, 즉 고정점(Fixed Point)을 찾는 것입니다. 고정점은 함수 관점에서 f(x) = x를 만족하는 지점을 뜻하며, 배열에 적용하면 arr[i] == i가 성립하는 인덱스 i를 의미합니다.
접근 방법
가장 직관적인 해결 방법은 선형 탐색(linear search)입니다. 배열의 처음부터 끝까지 차례대로 순회하면서 현재 인덱스와 그 위치의 요소 값이 일치하는지 확인하고, 조건을 만족하는 첫 번째 인덱스를 반환하면 됩니다. 끝까지 찾지 못했다면 -1을 반환하여 고정점이 존재하지 않음을 알립니다.
C++ 코드
#include <bits/stdc++.h>
using namespace std;
int linearSearch(int arr[], int n) {
for(int i = 0; i < n; i++) {
if(arr[i] == i) {
return i;
}
}
return -1;
}
int main() {
int arr[] = {10, 20, 30, 40, 50, 5, 60};
cout << linearSearch(arr, 7) << endl;
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
5
코드 동작 원리
배열 {10, 20, 30, 40, 50, 5, 60}에서 각 인덱스와 값을 비교해 보겠습니다.
- 인덱스 0: 값 10 → 불일치
- 인덱스 1: 값 20 → 불일치
- 인덱스 2: 값 30 → 불일치
- 인덱스 3: 값 40 → 불일치
- 인덱스 4: 값 50 → 불일치
- 인덱스 5: 값 5 → 일치! 따라서 5를 반환
인덱스 5에서 arr[5] == 5 조건을 만족하므로 프로그램은 5를 출력합니다.
시간 복잡도
- 시간 복잡도: O(n) — 최악의 경우 배열 전체를 순회해야 합니다.
- 공간 복잡도: O(1) — 추가 메모리를 사용하지 않습니다.
정렬된 배열이라면 이진 탐색으로 최적화 가능
만약 입력 배열이 오름차순으로 정렬되어 있다면 이진 탐색(binary search)을 활용해 시간 복잡도를 O(log n)까지 줄일 수 있습니다. 중간 위치의 값이 인덱스보다 크면 왼쪽 절반을, 작으면 오른쪽 절반을 탐색하면 됩니다.
#include <bits/stdc++.h>
using namespace std;
int binarySearch(int arr[], int n) {
int low = 0, high = n - 1;
while(low <= high) {
int mid = (low + high) / 2;
if(arr[mid] == mid) {
return mid;
} else if(arr[mid] > mid) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
마무리
지금까지 C++에서 배열 내 고정점을 찾는 두 가지 방법을 살펴봤습니다. 배열이 정렬되어 있지 않다면 선형 탐색을, 정렬되어 있다면 이진 탐색을 선택하는 것이 효율적입니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.