이 문제에서는 0과 1(불리언 값)로만 구성된 정렬된 배열 bin[]이 주어집니다. 우리의 목표는 이 배열에서 처음으로 1이 나타나는 인덱스를 찾는 것입니다.
문제 이해하기
예시를 통해 문제를 살펴보겠습니다.
입력 : bin[] = {0, 0, 0, 1, 1}
출력 : 3설명 −
배열에서 처음으로 1이 등장하는 위치는 인덱스 3입니다.
해결 접근 방법
이 문제를 해결하려면 배열에서 첫 번째 1의 인덱스를 찾아야 하며, 이를 위해 다양한 탐색 기법을 활용할 수 있습니다.
방법 1: 선형 탐색 (Linear Search)
가장 직관적인 방법은 선형 탐색입니다. 배열을 인덱스 0부터 끝까지 순서대로 순회하면서 처음으로 1을 만나면 해당 인덱스를 반환하고, 배열에 1이 없다면 -1을 반환합니다.
코드 예시
선형 탐색 방식의 동작을 보여주는 프로그램입니다.
#include <iostream>
using namespace std;
int find1stOneInArray(int bin[], int n) {
for (int i = 0; i < n; i++)
if (bin[i] == 1)
return i;
return -1;
}
int main() {
int bin[] = { 0, 0, 0, 1, 1, 1 };
int n = sizeof(bin) / sizeof(bin[0]);
cout<<"배열에서 첫 번째 1의 인덱스는 "<<find1stOneInArray(bin,n);
return 0;
}
출력 결과
배열에서 첫 번째 1의 인덱스는 3
선형 탐색은 구현이 간단하지만, 최악의 경우 시간 복잡도가 O(n)이므로 배열의 크기가 클 때는 비효율적일 수 있습니다.
방법 2: 이진 탐색 (Binary Search)
배열이 이미 정렬되어 있다는 특성을 활용하면 이진 탐색을 적용할 수 있습니다. 이진 탐색은 탐색 범위를 절반씩 줄여가며 검색하기 때문에 시간 복잡도를 O(log n)으로 크게 개선할 수 있습니다.
탐색 과정은 다음과 같습니다.
- 중간 요소가 1이고, 그 앞의 요소가 0이거나 중간 위치가 배열의 시작이라면 해당 인덱스가 첫 번째 1의 위치입니다.
- 중간 요소가 1이지만 그 앞에도 1이 있다면, 왼쪽 절반에서 계속 탐색합니다.
- 중간 요소가 0이라면, 오른쪽 절반에서 계속 탐색합니다.
코드 예시
이진 탐색 방식의 동작을 보여주는 프로그램입니다.
#include <iostream>
using namespace std;
int find1stOneInArray(int bin[], int n) {
int low = 0;
int high = (n - 1);
int mid;
while (low <= high) {
mid = (low + high) / 2;
if (bin[mid] == 1 && (mid == 0 || bin[mid - 1] == 0))
return mid;
else if (bin[mid] == 1)
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
int main() {
int bin[] = { 0, 0, 0, 1, 1, 1, 1 };
int n = sizeof(bin) / sizeof(bin[0]);
cout<<"배열에서 첫 번째 1의 인덱스는 "<<find1stOneInArray(bin,n);
return 0;
}
출력 결과
배열에서 첫 번째 1의 인덱스는 3
마무리
정렬된 0과 1 배열에서 첫 번째 1의 인덱스를 찾는 문제는 선형 탐색과 이진 탐색 두 가지 방법으로 해결할 수 있습니다. 배열이 정렬되어 있는 조건이 주어졌다면 O(log n)의 성능을 내는 이진 탐색을 사용하는 것이 훨씬 효율적입니다. 반면, 코드의 단순함이 우선이라면 선형 탐색도 충분히 좋은 선택이 될 수 있습니다.