반응형
알고리즘 문제를 풀다 보면 "동작은 하지만 더 효율적으로 할 수 있지 않을까?" 라는 생각이 들 때가 있습니다. 오늘은 백준 11728번 '배열 합치기' 문제를 통해 단순한 접근법에서 최적화된 해결책으로 발전하는 과정을 살펴보겠습니다.
문제 분석
문제 설명
백준 11728번: 배열 합치기
- 시간 제한: 1.5초
- 메모리 제한: 256MB
- 정답 비율: 46.789%
문제 내용: 이미 정렬되어 있는 두 배열 A와 B가 주어질 때, 두 배열을 합친 다음 정렬해서 출력하는 프로그램을 작성해야 합니다.
입력 조건
- 첫째 줄: 배열 A의 크기 N, 배열 B의 크기 M (1 ≤ N, M ≤ 1,000,000)
- 둘째 줄: 배열 A의 내용 (정렬된 상태)
- 셋째 줄: 배열 B의 내용 (정렬된 상태)
- 배열 원소: 절댓값이 10⁹보다 작거나 같은 정수
예제 입력/출력
| 입력 | 출력 |
|---|---|
2 23 52 9 |
2 3 5 9 |
2 14 71 |
1 4 7 |
4 32 3 5 91 4 7 |
1 2 3 4 5 7 9 |
첫 번째 접근법: 무차별 대입
처음 문제를 접했을 때 가장 직관적으로 떠오르는 방법입니다.
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
# 두 배열을 합치고 정렬
C = A + B
C.sort()
print(" ".join(map(str, C)))동작 과정
- 두 배열 A와 B를 단순히 연결 (
A + B) - 합쳐진 배열을 정렬 (
C.sort()) - 결과 출력
시간 복잡도 분석
- 배열 합치기: O(N + M)
- 정렬: O((N + M) log(N + M))
- 전체: O((N + M) log(N + M))
이 방법의 가장 큰 문제점은 이미 정렬된 배열의 특성을 전혀 활용하지 못한다는 것입니다. 마치 이미 정리된 두 개의 책장에서 책을 모두 꺼내서 다시 섞어서 정리하는 것과 같습니다.
두 번째 접근법: 투 포인터 (Two Pointers)
핵심 아이디어: 이미 정렬된 두 배열의 특성을 활용하여, 각 배열의 앞에서부터 비교해가며 작은 값부터 차례로 선택합니다.
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
i = j = 0 # 각 배열의 포인터
result = []
# 두 배열을 모두 순회할 때까지 반복
while i < N and j < M:
if A[i] <= B[j]:
result.append(A[i])
i += 1
else:
result.append(B[j])
j += 1
# 남은 원소들 추가
result.extend(A[i:]) # A 배열에 남은 원소들
result.extend(B[j:]) # B 배열에 남은 원소들
print(" ".join(map(str, result)))동작 과정 시각화
두 배열 A = [2, 3, 5, 9], B = [1, 4, 7]을 병합하는 과정을 살펴보겠습니다:
초기 상태:
A: [2, 3, 5, 9] i=0 (가리키는 값: 2)
B: [1, 4, 7] j=0 (가리키는 값: 1)
result: []
1단계: A[0]=2 vs B[0]=1 → 1이 더 작음
A: [2, 3, 5, 9] i=0
B: [1, 4, 7] j=1 (가리키는 값: 4)
result: [1]
2단계: A[0]=2 vs B[1]=4 → 2가 더 작음
A: [2, 3, 5, 9] i=1 (가리키는 값: 3)
B: [1, 4, 7] j=1
result: [1, 2]
3단계: A[1]=3 vs B[1]=4 → 3이 더 작음
A: [2, 3, 5, 9] i=2 (가리키는 값: 5)
B: [1, 4, 7] j=1
result: [1, 2, 3]
... (계속)
최종 결과: [1, 2, 3, 4, 5, 7, 9]시간 복잡도 분석
- 비교 연산: 최대 N + M 번
- 배열 복사: O(N + M)
- 전체: O(N + M)
성능 비교
시간 복잡도 비교
| 방법 | 시간 복잡도 | N=M=500,000일 때 |
|---|---|---|
| 무차별 정렬 | O((N+M) log(N+M)) | 약 19,930,000 연산 |
| 투 포인터 | O(N+M) | 약 1,000,000 연산 |
성능 향상: 약 20배 빠름
실제 실행 시간 측정
import time
import random
def generate_sorted_array(size):
"""정렬된 배열 생성"""
arr = [random.randint(1, 1000000) for _ in range(size)]
return sorted(arr)
# 테스트 데이터 생성
N = M = 100000
A = generate_sorted_array(N)
B = generate_sorted_array(M)
# 방법 1: 무차별 정렬
start_time = time.time()
C1 = A + B
C1.sort()
time1 = time.time() - start_time
# 방법 2: 투 포인터
start_time = time.time()
i = j = 0
C2 = []
while i < N and j < M:
if A[i] <= B[j]:
C2.append(A[i])
i += 1
else:
C2.append(B[j])
j += 1
C2.extend(A[i:])
C2.extend(B[j:])
time2 = time.time() - start_time
print(f"무차별 정렬: {time1:.4f}초")
print(f"투 포인터: {time2:.4f}초")
print(f"성능 향상: {time1/time2:.1f}배")투 포인터 기법의 핵심 원리
1. 정렬된 자료구조의 특성 활용
투 포인터 기법은 이미 정렬된 자료구조의 순서 정보를 최대한 활용합니다. 각 배열의 현재 위치에서 가장 작은 값끼리만 비교하면 되므로, 불필요한 비교를 줄일 수 있습니다.
2. 탐욕적 선택 (Greedy Choice)
각 단계에서 현재 상황에서 최선의 선택을 합니다. 두 포인터가 가리키는 값 중 작은 값을 선택하는 것이 항상 최적해가 됩니다.
3. 분할 정복의 병합 단계
이 기법은 사실 병합 정렬(Merge Sort)의 병합 단계와 동일한 원리입니다. 이미 정렬된 두 부분을 효율적으로 합치는 핵심 알고리즘입니다.
실무 응용 사례
1. 데이터베이스 조인 최적화
-- 정렬된 두 테이블을 병합할 때 사용되는 Sort-Merge Join
SELECT * FROM tableA A
JOIN tableB B ON A.id = B.id
ORDER BY A.id, B.id;2. 로그 파일 병합
def merge_log_files(file1_path, file2_path, output_path):
"""시간 순으로 정렬된 두 로그 파일을 병합"""
with open(file1_path) as f1, open(file2_path) as f2, \
open(output_path, 'w') as out:
line1 = f1.readline()
line2 = f2.readline()
while line1 and line2:
time1 = extract_timestamp(line1)
time2 = extract_timestamp(line2)
if time1 <= time2:
out.write(line1)
line1 = f1.readline()
else:
out.write(line2)
line2 = f2.readline()
# 남은 라인들 처리
out.writelines(f1)
out.writelines(f2)3. 실시간 데이터 스트림 병합
def merge_sorted_streams(stream1, stream2):
"""정렬된 두 데이터 스트림을 실시간으로 병합"""
try:
val1 = next(stream1)
val2 = next(stream2)
while True:
if val1 <= val2:
yield val1
val1 = next(stream1)
else:
yield val2
val2 = next(stream2)
except StopIteration:
# 한 스트림이 끝나면 나머지 스트림의 데이터를 모두 반환
yield from stream1
yield from stream2주의사항과 예외 처리
1. 빈 배열 처리
def merge_arrays_safe(A, B):
"""빈 배열을 고려한 안전한 병합"""
if not A:
return B
if not B:
return A
i = j = 0
result = []
while i < len(A) and j < len(B):
if A[i] <= B[j]:
result.append(A[i])
i += 1
else:
result.append(B[j])
j += 1
result.extend(A[i:])
result.extend(B[j:])
return result2. 메모리 효율성 고려
def merge_arrays_generator(A, B):
"""메모리 효율적인 제너레이터 버전"""
i = j = 0
while i < len(A) and j < len(B):
if A[i] <= B[j]:
yield A[i]
i += 1
else:
yield B[j]
j += 1
yield from A[i:]
yield from B[j:]
# 사용 예시
result = list(merge_arrays_generator(A, B))확장 응용: K개 배열 병합
import heapq
def merge_k_sorted_arrays(arrays):
"""K개의 정렬된 배열을 효율적으로 병합"""
# 힙을 사용한 K-way merge
heap = []
result = []
# 각 배열의 첫 번째 원소를 힙에 추가
for i, arr in enumerate(arrays):
if arr: # 빈 배열이 아닌 경우
heapq.heappush(heap, (arr[0], i, 0))
while heap:
val, arr_idx, elem_idx = heapq.heappop(heap)
result.append(val)
# 해당 배열의 다음 원소가 있다면 힙에 추가
if elem_idx + 1 < len(arrays[arr_idx]):
next_val = arrays[arr_idx][elem_idx + 1]
heapq.heappush(heap, (next_val, arr_idx, elem_idx + 1))
return result
# 시간 복잡도: O(N log K), N은 총 원소 개수, K는 배열 개수마무리
배열 합치기 문제를 통해 단순한 해결책에서 최적화된 해결책으로 발전하는 과정을 살펴보았습니다.
핵심 포인트
- 문제의 조건을 잘 관찰하기: "이미 정렬된 배열"이라는 조건이 핵심
- 시간 복잡도 분석의 중요성: O(N log N)에서 O(N)으로 약 20배 성능 향상
- 투 포인터 기법의 범용성: 다양한 실무 상황에서 활용 가능
- 점진적 최적화: 동작하는 코드부터 시작해서 단계적으로 개선
개발자로서의 인사이트
좋은 개발자는 "동작하는 코드"에서 멈추지 않고 "더 나은 코드"를 고민합니다. 특히 대용량 데이터를 다루거나 실시간 처리가 필요한 상황에서는 이런 최적화가 서비스의 성패를 좌우할 수 있습니다.
알고리즘 문제 풀이는 단순히 정답을 맞히는 것을 넘어서, 효율적인 사고방식을 기르는 훈련입니다. 오늘 배운 투 포인터 기법을 다른 문제에도 적용해보시기 바랍니다.
참고 자료
반응형
'Algorithm > 백준' 카테고리의 다른 글
| [백준 / 2578 / Python] 빙고 (2) | 2025.06.14 |
|---|---|
| [백준 / 2239 / Python] 스도쿠 (0) | 2025.06.13 |
| [백준 / 17404 / Python] RGB거리 2 (2) | 2025.06.13 |
| [백준 / 2342 / Python] Dance Dance Revolution (0) | 2025.06.13 |
| [백준 / 2143 / Python] 두 배열의 합 (0) | 2025.06.13 |