최종 도전과 O(N)의 비밀 (두 포인터)
소개
우리는 알고리즘 복잡도 여정을 마무리합니다! Merge Sort O(N log N)의 힘과 이진 탐색 O(log N)의 속도를 살펴봤습니다.
이번 마지막 포스트에서는:
- O(N) 지식을 활용한 고급 도전 과제(“제곱 문제”) 적용;
- Elixir의 Map이 O(1)이라고 약속할 수 있는 기술적 비밀 공개.
문제 다시 보기
정렬된 리스트 nums가 주어지면, 그 숫자들의 제곱을 구한 뒤 역시 정렬된 리스트를 반환하세요.
입력 (nums) | 제곱 (정렬되지 않음) | 정렬된 결과 |
|---|---|---|
[-4, -1, 0, 3, 10] | [16, 1, 0, 9, 100] | [0, 1, 9, 16, 100] |
단순한 해결법
각 요소를 제곱 → O(N)
결과를 정렬 → O(N log N)
총합: O(N log N).
두 포인터를 이용한 O(N) 해결법
핵심은 입력이 이미 정렬돼 있다는 정보를 활용하는 것입니다. 가장 큰 제곱값은 항상 입력 리스트의 양쪽 끝에 위치합니다(절댓값이 큰 음수 때문).
두 포인터 기법은 결과를 뒤에서부터(가장 큰 값부터 작은 값 순) 구성합니다:
- 왼쪽 포인터
l을 시작 위치에 둠(-4); - 오른쪽 포인터
r을 끝 위치에 둠(10); - 양쪽 끝의 제곱값을 비교하고, 더 큰 제곱값을 결과 리스트에 넣음;
- 해당 포인터를 안쪽으로 이동시킴.
복잡도: O(N).
Elixir 구현
Elixir에서는 Enum.reduce를 사용해 포인터 이동을 시뮬레이션하고, [square | acc](prepend)를 이용해 결과를 뒤에서부터 **O(1)**씩 구축합니다.
defmodule SortedSquares do
@doc "두 포인터를 이용한 O(N) 해결법, 역순으로 결과를 구축합니다."
def sorted_squares(nums) do
# l: 왼쪽 포인터 (0), r: 오른쪽 포인터 (N-1)
{result_reversed, _} =
0..(length(nums) - 1)
|> Enum.reduce({[], {0, length(nums) - 1}}, fn _, {acc, {l, r}} ->
left_square = Enum.at(nums, l) * Enum.at(nums, l)
right_square = Enum.at(nums, r) * Enum.at(nums, r)
if left_square > right_square do
# 왼쪽 값이 더 크면 l 포인터를 이동
{[left_square | acc], {l + 1, r}}
else
# 오른쪽 값이 더 크거나 같으면 r 포인터를 이동
{[right_square | acc], {l, r - 1}}
end
end)
result_reversed
end
end두 포인터 기법 결론
이 기법은 각 요소를 정확히 한 번씩만 방문하므로 **O(N)**을 보장하고, 최종 정렬 비용(O(N log N))을 피합니다.
Elixir의 Map 및 MapSet에서 O(1)
이 시리즈 동안 Map과 MapSet의 검색/삽입이 **O(1)**이라고 약속했습니다. 왜 이렇게 빠른지, 그리고 불변성을 유지하면서 어떻게 가능한지 궁금하시죠?
답은 Erlang/Elixir가 사용하는 자료구조, **Hash Array Mapped Tries (HAMT)**에 있습니다.
- Hashing: 키(예:
:user)를 해시 코드(숫자)로 변환합니다. - Trie (디지털 트리): 이 해시 코드를 트리에서 경로를 찾는 데 사용합니다. HAMT는 몇 단계만 내려가면 정확한 위치를 찾을 수 있습니다.
- Array Mapped: 각 레벨마다 많은 포인터 대신 작은 배열(“맵”)을 두어 다음 분기를 빠르게 찾습니다.
불변성의 장점
Elixir에서 MapSet을 업데이트할 때 시스템은 전체 구조를 복사하지 않습니다. 변경되지 않은 트리의 기존 가지를 재사용하고, 수정된 경로에만 새로운 노드를 생성합니다. 이 방식을 구조적 공유 (Structural Sharing) 라고 합니다.
HAMT 덕분에 검색과 삽입이 O(1)(상수 시간)이라는 약속이 유지되며, Elixir 코드는 BEAM 위에서 빠르고 안전하게 동시성을 지원합니다.
최종 요약
이제 복잡도 클래스에 대한 탄탄한 이해를 갖추었으며, O(N²) 병목을 식별하고, Elixir(머지 정렬, MapSet, reduce)를 활용해 작동할 뿐 아니라 효율적으로 확장되는 코드를 작성할 수 있습니다.