개인 공부겸 알고리즘들에 대허 정리를 하기로 했다.
먼저 이번편에서는 탐색 알고리즘 중 선형 탐색(Linear Search)과 이진 탐색(Binary Search) 대해 적어보겠다.
추가로 투포인터 탐색(Two pointer)에 대해서도 적어 보겠다.
1. 선형 탐색 (Linear Search)
✓ 개념
- 정렬 여부와 상관없이 리스트(배열, 컬렉션 등)의 처음부터 끝까지 차례로 비교하여 원하는 값을 찾는 가장 기본적인 탐색 방법이다.
- 배열이나 리스트의 요소를 하나하나 순차적으로 확인하면서 조건에 맞는 값을 찾는다.
⏱️ 시간 복잡도 (Time Complexity)
- 최악의 경우 (Worst case): O(n) → 마지막 요소까지 전부 확인해야 할 때
- 최선의 경우 (Best case): O(1) → 첫 번째 요소가 정답일 때
- 평균적인 경우 (Average case): O(n)
- 중첩하여 사용할 시: O(n^x) → x는 for문이나 while문의 중첩 개수
💾 공간 복잡도 (Space Complexity)
- O(1) → 추가 메모리를 거의 사용하지 않음
장점
- 간단하고 구현이 쉬움
- 정렬이 필요 없음
- 모든 자료구조에 적용 가능 (배열, 리스트 등)
단점
- 데이터가 많아질수록 속도가 느려짐
- 탐색 효율이 낮음 (특히 대규모 데이터에서 비효율적)
Java에서의 구현 방식
배열에서 선형 탐색
public class LinearSearchExample {
public static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i; // target 찾으면 인덱스 반환
}
}
return -1; // 없으면 -1
}
public static void main(String[] args) {
int[] numbers = {5, 3, 8, 4, 2};
int target = 4;
int result = linearSearch(numbers, target);
System.out.println("Index: " + result); // 출력: Index: 3
}
}리스트에서 선형 탐색
import java.util.List;
import java.util.Arrays;
public class LinearSearchList {
public static int linearSearch(List<Integer> list, int target) {
for (int i = 0; i < list.size(); i++) {
if (list.get(i) == target) {
return i;
}
}
return -1;
}
public static void main(String[] args) {
List<Integer> list = Arrays.asList(10, 20, 30, 40);
System.out.println("Index: " + linearSearch(list, 30)); // 출력: Index: 2
}
}
2. 이진 탐색 (Binary Search)
✓ 개념
- 정렬된 데이터에서만 사용 가능.
- 중앙값을 기준으로 탐색 범위를 절반으로 계속 줄여가며 찾는 방식.
- 비교할 때마다 탐색 범위를 절반씩 줄이므로 매우 빠름.
⏱️ 시간 복잡도 (Time Complexity)
- 최악의 경우 (Worst case): O(log n) → 마지막 요소까지 전부 확인해야 할 때
- 최선의 경우 (Best case): O(1) → 첫 번째 요소가 정답일 때
- 평균적인 경우 (Average case): O(log n)
- 중첩하여 사용할 시: O(n^x) → x는 for문이나 while문의 중첩 개
n개의 요소가 있다면 최대 log₂(n)번만 비교하면 됩니다.
💾 공간 복잡도 (Space Complexity)
- 반복문 구현: O(1)
- 재귀 구현: O(log n) → 재귀 호출이 스택에 쌓이기 때문
장점
- 탐색 속도가 빠름 → 큰 데이터에서도 효율적
- 시간 복잡도 O(log n)으로 성능 우수
단점
- 데이터가 정렬되어 있어야만 사용 가능
- 삽입/삭제가 잦은 경우 정렬 유지가 번거로움
- 구현이 선형 탐색보다 약간 복잡
Java에서의 구현
반복문(while)
public class BinarySearch {
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1; // 오른쪽 절반으로 이동
} else {
right = mid - 1; // 왼쪽 절반으로 이동
}
}
return -1; // 찾지 못했을 때
}
public static void main(String[] args) {
int[] nums = {2, 4, 7, 10, 23, 38, 45};
int index = binarySearch(nums, 10);
System.out.println("Index: " + index); // 출력: Index: 3
}
}재귀 방식
public static int binarySearchRecursive(int[] arr, int target, int left, int right) {
if (left > right) return -1;
int mid = (left + right) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target)
return binarySearchRecursive(arr, target, mid + 1, right);
else
return binarySearchRecursive(arr, target, left, mid - 1);
}자바에서 제공하는 기본 메서드 활용
Arrays.binarySearch()를 사용하면 손쉽게 이진 탐색을 할 수 있다.
import java.util.Arrays;
int[] arr = {3, 6, 8, 10, 15};
int idx = Arrays.binarySearch(arr, 10); // 정렬된 상태여야 함!
System.out.println(idx); // 출력: 3
이진 탐색과 투포인터 탐색의 차이점
구현된 모습을 보면 이진 탐색과 투포인터가 비슷해 보인다.
하지만 이 둘은 별개의 탐색 알고리즘이다.
| 항목 | 투포인터 탐색 | 이진 탐색 |
| 목적 | 주로 쌍 찾기, 구간 합, 정렬된 배열의 조합 찾기 등에 사용 | 정렬된 배열에서 하나의 값을 빠르게 찾기 위해 |
| 반복 방식 | 양쪽 포인터를 이동시키며 조건 만족 여부를 확인 | 중앙값을 기준으로 좌우 범위를 줄여가며 탐색 |
| 시간 복잡도 | 보통 O(n) | O(log n) |
| 전제 조건 | 정렬된 배열이면 좋음, 하지만 필수는 아님 | 정렬된 배열이어야만 함 |
| 아이디어 | 투 포인터가 서로 좁혀오며 탐색 | 중간 값을 기준으로 반씩 잘라서 탐색 |
| 용도 예시 | 두 수의 합 = x, 가장 긴 부분합, 슬라이딩 윈도우 | 특정 값 탐색, lower/upper bound, 이진 결정 등 |
3. 투 포인터 알고리즘 (Two Pointer)
✓ 개념
- 배열이나 리스트에서 두 개의 포인터를 사용해 효율적으로 문제를 해결하는 방식.
- 주로 정렬된 배열에서 사용되며, 포인터를 양 끝이나 한쪽에서 시작해 조건에 맞게 이동한다.
⏱️ 시간 복잡도
- 시간 복잡도: O(n)
두 포인터가 각각 한 번씩만 이동하므로 전체 배열을 한 번만 훑는다. - 공간 복잡도: O(1)
포인터 변수만 쓰기 때문에 추가 공간이 거의 필요 없다.
장점
- 속도가 빠름 (O(n))
- 코드가 간결함
- 정렬된 배열에서 문제를 더 효과적으로 해결 가능
- 다양한 문제에 응용 가능: 부분합, 두 수의 합, 슬라이딩 윈도우 등
단점
- 정렬된 배열/리스트에서만 유용한 경우가 많음
- 문제의 조건에 따라 포인터 이동 방향을 잘 설계해야 함
- 투 포인터 적용이 직관적이지 않은 경우도 있음
Java에서의 구현
예제 1️⃣: 두 수의 합 (Two Sum) – 정렬된 배열에서 O(n)
public boolean hasTwoSum(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) return true;
else if (sum < target) left++;
else right--;
}
return false;
}예제 2️⃣: 가장 긴 부분 배열의 합 ≤ target
public int maxSubarrayLength(int[] arr, int target) {
int left = 0, sum = 0, maxLen = 0;
for (int right = 0; right < arr.length; right++) {
sum += arr[right];
while (sum > target) {
sum -= arr[left++];
}
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}예제 3️⃣: 중복 없는 최장 부분 문자열 (문자열 버전)
public int lengthOfLongestSubstring(String s) {
int left = 0, maxLen = 0;
Set<Character> set = new HashSet<>();
for (int right = 0; right < s.length(); right++) {
while (set.contains(s.charAt(right))) {
set.remove(s.charAt(left++));
}
set.add(s.charAt(right));
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}투 포인터의 대표적인 활용 분야
| 유형 | 예시 |
| 정렬된 배열의 합 | 두 수의 합, 세 수의 합 (Two/Three Sum) |
| 부분합 문제 | 누적합 ≤ target, 최소 길이 구간 등 |
| 문자열 탐색 | 중복 없는 부분 문자열 길이 |
| 슬라이딩 윈도우 | 고정 or 가변 길이 윈도우 탐색 |
개인적인 의견이지만 선형, 이진 탐색과는 별개로 투포인터 탐색은 코딩 문제에서 자주 활용하는 편이다.
LeetCode에서 문자열 탐색이나 부분합 문제 등 여러가지로 활용을 많이하니까 익혀두면 좋을 듯 하다.
Ahan
책, 영화, 게임! 인생의 활력 요소가 되는 취미들을 하자!