배열은 가장 기본적인 자료구조 중 하나로, 다음과 같은 고유한 특성을 가집니다.
- 0-기반 인덱싱: 첫 번째 요소는 항상 인덱스 0으로 접근합니다.
- 연속적인 메모리 할당: 메모리상에 요소들이 순서대로 저장되어 있어, 인덱스를 통한 빠른 접근이 가능합니다.
이러한 특성 때문에 배열을 조작할 때는 인덱스 관리에 특히 유의해야 하며, 요소의 삽입이나 삭제 시에는 인접한 요소들을 이동(쉬프트)시켜야 하는 비용이 발생할 수 있습니다. (실제 삭제는 다른 값으로 덮어쓰는 형태로 이루어지는 경우가 많습니다.)
1. 이진 탐색을 활용한 탐색 (좌우 투 포인터)
정렬된 배열에서 특정 값을 효율적으로 찾기 위한 기법입니다. left와 right 두 개의 포인터를 사용하여 탐색 범위를 절반씩 줄여나갑니다.
이진 탐색 기본 구조 (C++)
int binarySearch(const std::vector<int>& arr, int target) {
int left = 0;
int right = arr.size() - 1; // [left, right] 범위 (양쪽 닫힌 구간)
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; // 타겟을 찾지 못함
}
이진 탐색 기본 구조 (Python)
def binary_search(arr, target):
left = 0
right = len(arr) - 1 # [left, right] 범위 (양쪽 닫힌 구간)
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid # 타겟을 찾음
elif arr[mid] < target:
left = mid + 1 # 타겟이 중간값보다 크므로 오른쪽 부분 탐색
else:
right = mid - 1 # 타겟이 중간값보다 작으므로 왼쪽 부분 탐색
return -1 # 타겟을 찾지 못함
탐색 범위 경계 처리:
이진 탐색 구현 시 while문의 조건(left <= right 또는 left < right)과 left, right 포인터 업데이트 방식은 탐색 범위 설정에 따라 달라집니다.
[left, right](양쪽 닫힌 구간):while (left <= right),left = mid + 1,right = mid - 1[left, right)(왼쪽 닫히고 오른쪽 열린 구간):while (left < right),left = mid + 1,right = mid
활용 문제 유형:
- 특정 값의 존재 여부 및 인덱스 찾기
- 정렬된 배열에서 값의 삽입 위치 결정
- 정렬된 배열에서 특정 값의 첫 번째/마지막 등장 위치 찾기
- 정수/실수 범위에서 특정 조건을 만족하는 값 찾기 (예: N제곱근)
2. 일반적인 좌우 투 포인터 기법
탐색 외의 다양한 문제 해결에 사용되는 투 포인터 기법입니다. 보통 left는 배열의 시작, right는 배열의 끝에서 시작하여 특정 조건을 만족할 때까지 서로를 향해 이동합니다.
활용 문제 유형:
- 정렬된 배열의 변환: 예: 정렬된 배열의 각 원소를 제곱한 후 다시 정렬된 배열로 만드는 문제 (양 끝에서부터 결과를 채워나감).
- N-Sum 문제 (합이 특정 값인 N개 원소 찾기): 배열을 정렬한 후, 고정된 포인터와 좌우 투 포인터를 사용하여 중복 없이 목표 합을 찾는 문제 (예: 세 수의 합, 네 수의 합).
- 배열/문자열 뒤집기: 좌우 포인터를 사용하여 원소들을 교환하며 전체를 뒤집는 문제.
- 구간 병합: 정렬된 구간들을 순회하며 겹치는 구간들을 하나로 합치는 문제.
- 회문 검사 및 부분 문자열 찾기: 문자열의 중심(홀수 길이) 또는 두 중심(짝수 길이)에서부터 양쪽으로 포인터를 확장하여 회문 여부를 검사하거나 회문 부분 문자열을 세는 문제.
3. 빠르고 느린 투 포인터 (Fast & Slow Pointers)
두 포인터가 서로 다른 속도로 이동하며 배열(또는 연결 리스트)을 순회하는 기법입니다. 주로 특정 조건을 만족하는 요소를 건너뛰거나, 배열의 특정 부분을 압축하거나, 주기성을 탐지하는 데 사용됩니다.
활용 문제 유형:
- 특정 요소 제거: 빠른 포인터로 배열 전체를 순회하고, 느린 포인터로 조건을 만족하는 요소만 새로운 위치에 채워 넣어 특정 요소를 제거한 배열을 효율적으로 구성하는 문제.
- 문자열 공백 처리 및 단어 뒤집기: 문자열에서 불필요한 공백을 제거하고 단어들을 뒤집는 과정에서, 빠른 포인터로 원본을 읽고 느린 포인터로 새로운 문자열을 구성.
- 정렬된 배열에서 중복 제거: 빠른 포인터로 다음 고유 요소를 찾고 느린 포인터로 고유 요소를 덮어쓰는 방식으로 중복을 제거.
- 두 포인터 간의 상대적 위치 비교: 연결 리스트의 중간 노드 찾기, 사이클 탐지 등.
- 부분 시퀀스 확인: 하나의 포인터는 전체 시퀀스를, 다른 포인터는 부분 시퀀스를 따라가며 존재 여부를 확인.
4. 슬라이딩 윈도우 투 포인터
배열이나 문자열의 연속적인 부분 배열/부분 문자열에서 특정 조건을 만족하는 가장 긴 또는 가장 짧은 구간을 찾을 때 유용합니다. left와 right 포인터가 윈도우의 시작과 끝을 나타내며, right 포인터로 윈도우를 확장하고, 조건이 만족되지 않거나 특정 조건을 충족하면 left 포인터로 윈도우를 축소하는 방식입니다.
슬라이딩 윈도우 기본 구조 (C++)
int slidingWindowMinLength(const std::vector<int>& arr, int target_sum) {
int min_len = arr.size() + 1; // 최소 길이 저장 (초기값: 최대 가능 길이 + 1)
int current_sum = 0;
int left = 0;
for (int right = 0; right < arr.size(); ++right) {
current_sum += arr[right]; // 윈도우 확장
while (current_sum >= target_sum) { // 조건 만족 시 윈도우 축소 시도
min_len = std::min(min_len, right - left + 1); // 현재 윈도우 길이 업데이트
current_sum -= arr[left]; // 왼쪽 끝 요소 제거
left++; // 윈도우 축소
}
}
return (min_len == arr.size() + 1) ? 0 : min_len; // 조건 만족하는 윈도우가 없으면 0 반환
}
슬라이딩 윈도우 기본 구조 (Python)
def sliding_window_min_length(arr, target_sum):
min_len = len(arr) + 1 # 최소 길이 저장 (초기값: 최대 가능 길이 + 1)
current_sum = 0
left = 0
for right in range(len(arr)):
current_sum += arr[right] # 윈도우 확장
while current_sum >= target_sum: # 조건 만족 시 윈도우 축소 시도
min_len = min(min_len, right - left + 1) # 현재 윈도우 길이 업데이트
current_sum -= arr[left] # 왼쪽 끝 요소 제거
left += 1 # 윈도우 축소
return 0 if min_len == len(arr) + 1 else min_len # 조건 만족하는 윈도우가 없으면 0 반환
활용 문제 유형:
- 최소/최대 길이 부분 배열/문자열: 특정 합을 가지는 최소 길이 부분 배열, k가지 종류의 과일을 담을 수 있는 최대 길이 부분 배열 등.
- 중복 없는 최장 부분 문자열: 중복 문자가 없는 가장 긴 부분 문자열 찾기.
- 단조 큐와 결합: 슬라이딩 윈도우 내의 최댓값/최솟값을 효율적으로 찾기 위해 단조 큐를 활용 (예: 슬라이딩 윈도우 최댓값).
- 연속 부분 시퀀스: 가장 긴 연속 증가 부분 시퀀스 등.
5. 나선형 행렬 (Spiral Matrix) 순회
정사각형 또는 직사각형 행렬을 시계 방향(또는 반시계 방향)으로 나선형으로 순회하며 요소를 처리하는 문제입니다. 경계 추적 또는 레이어별 접근 방식이 주로 사용됩니다.
해결 기법:
- 경계 축소 방식:
top,bottom,left,right네 개의 변수를 사용하여 현재 순회 중인 영역의 경계를 나타냅니다. 한 변을 순회할 때마다 해당 변의 경계를 안쪽으로 한 칸씩 이동시킵니다. 모든 요소가 처리될 때까지 이 과정을 반복합니다. - 레이어별 접근 방식: 각 "레이어"의 시작점을 설정하고, 현재 레이어의 길이에 따라 순회하며 요소를 채우거나 읽어옵니다.
활용 문제 유형:
- 주어진 크기의 나선형 행렬 생성 (예: N*N 행렬에 1부터 N^2까지 나선형으로 채우기).
- 주어진 행렬의 요소를 나선형 순서로 반환.
6. 누적 합 (Prefix Sum)
배열의 특정 인덱스까지의 모든 요소의 합을 미리 계산해 둠으로써, 임의의 구간 합을 O(1) 시간에 빠르게 조회할 수 있도록 하는 기법입니다.
누적 합 계산 기본 구조 (C++)
std::vector<int> calculatePrefixSums(const std::vector<int>& data) {
int n = data.size();
std::vector<int> prefix_sums(n + 1, 0); // prefix_sums[0] = 0
for (int i = 0; i < n; ++i) {
prefix_sums[i + 1] = prefix_sums[i] + data[i];
}
// prefix_sums[k]는 data[0]부터 data[k-1]까지의 합을 저장합니다.
// 따라서, data의 구간 [i, j] (0-based)의 합은 prefix_sums[j + 1] - prefix_sums[i] 입니다.
return prefix_sums;
}
누적 합 계산 기본 구조 (Python)
def calculate_prefix_sums(data):
n = len(data)
prefix_sums = [0] * (n + 1) # prefix_sums[0] = 0
for i in range(n):
prefix_sums[i + 1] = prefix_sums[i] + data[i]
# prefix_sums[k]는 data[0]부터 data[k-1]까지의 합을 저장합니다.
# 따라서, data의 구간 [i, j] (0-based)의 합은 prefix_sums[j + 1] - prefix_sums[i] 입니다.
return prefix_sums
활용 문제 유형:
- 구간 합 쿼리: 다양한 구간의 합을 효율적으로 계산해야 하는 문제.
- 동적 계획법(DP) 최적화: 특정 구간 합을 필요로 하는 DP 문제에서 전이식을 최적화.
- 해시 테이블과의 결합: 특정 조건을 만족하는 부분 배열을 찾을 때, 누적 합과 해시 테이블을 함께 사용하여
O(N)시간 안에 해결 (예: 합이 K인 부분 배열의 개수, 문자와 숫자로 구성된 배열에서 문자와 숫자의 개수가 같은 가장 긴 부분 배열).