문제 설명
주어진 정수 배열 arr에서 특정한 정수 x의 존재 여부를 확인하는 문제입니다. 정수 x가 배열에 존재하면 true를 반환하고, 존재하지 않으면 false를 반환해야 합니다.
입력 형식
- 정수 배열
arr(1 ≤arr.Length≤ 100,000) - 검색할 정수
x(-1,000,000 ≤x≤ 1,000,000)
출력 형식
- 정수
x가 배열에 존재하면true, 아니면false를 반환해야 합니다.
예시 입력과 출력
입력: arr = [1, 2, 3, 4, 5], x = 3
출력: true
입력: arr = [1, 2, 3, 4, 5], x = 6
출력: false문제 접근 방법
이 문제를 해결하는 데에는 여러 가지 방법이 있습니다. 가장 간단한 방법은 배열을 순차적으로 탐색하여 주어진 정수가 존재하는지 확인하는 것입니다. 하지만 배열의 크기가 커질수록 성능이 떨어질 수 있으므로, 더 효율적인 알고리즘을 사용할 필요가 있습니다.
효율적인 접근법
정수 배열이 정렬되어 있다면 이진 탐색(Binary Search) 알고리즘을 사용할 수 있습니다. 이진 탐색은 배열을 반으로 나누어가며 검색을 수행하기 때문에 평균적으로 O(log n) 시간 복잡도로 실행됩니다.
선택 가능한 방법
- 순차 탐색(Linear Search): O(n) – 배열의 각 요소를 하나씩 비교.
- 이진 탐색(Binary Search): O(log n) – 배열이 정렬되어 있을 경우.
- 해시셋(HashSet) 사용: O(1) – 해시셋을 이용해 빠른 검색 시간 확보.
코드 구현
위에서 설명한 방법 중 이진 탐색을 사용하여 코드를 구현해보겠습니다. 아래는 C# 언어로 작성된 코드입니다.
using System;
class Program
{
static void Main()
{
int[] arr = { 1, 2, 3, 4, 5 };
int x = 3;
bool result = Contains(arr, x);
Console.WriteLine(result); // true
x = 6;
result = Contains(arr, x);
Console.WriteLine(result); // false
}
static bool Contains(int[] arr, int x)
{
int left = 0;
int right = arr.Length - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
// x가 중간값과 같으면 true 반환
if (arr[mid] == x)
return true;
// x가 중간값보다 작으면 왼쪽 부분 탐색
else if (arr[mid] > x)
right = mid - 1;
// x가 중간값보다 크면 오른쪽 부분 탐색
else
left = mid + 1;
}
return false; // x가 배열에 존재하지 않음
}
}복잡도 분석
시간 복잡도
이진 탐색의 경우, 최악의 경우에도 O(log n)의 효율성을 보입니다. 이는 탐색할 수 있는 범위가 절반씩 줄어들기 때문입니다.
공간 복잡도
이 알고리즘은 O(1)의 공간 복잡도를 가집니다. 추가적인 데이터 구조를 사용하지 않기 때문에 매우 메모리 효율적입니다.
마무리
이번 강좌에서는 원하는 정수를 찾는 문제를 다뤄보았습니다. 배열의 크기나 특성에 따라 다양한 알고리즘을 사용할 수 있으며, 각 알고리즘의 장단점을 이해하는 것이 중요합니다. 이진 탐색 외에도 해시셋과 같은 자료구조를 활용하면 원소의 존재 여부를 더욱 빠르게 확인할 수 있습니다. 앞으로도 다양한 문제를 풀어보며 더 많은 경험을 쌓기를 바랍니다.