PWC 391: 중앙값과 상자 쌓기 — Perl로 푼 두 가지 알고리즘 문제

본문

dev.to의 Bob Lied가 Perl Weekly Challenge(PWC) 391회 두 과제를 Perl로 풀이한 과정을 정리한 글입니다. 첫 번째 과제는 정렬된 두 배열을 병합해 중앙값을 반환하는 것이고, 두 번째는 주어진 상자들을 서로 안에 넣어 단일 스택으로 최대 몇 개까지 쌓을 수 있는지 구하는 문제입니다. 저자는 두 문제 모두에서 "병합(merge)하고 싶은 충동"이 든다고 말하며 순서대로 다룹니다.

Task 1 — 정렬된 두 배열의 중앙값

가장 단순한 해법은 두 배열을 합쳐 정렬한 뒤 가운데를 인덱싱하는 것입니다. 원소 개수가 홀수면 floor(n/2) 위치의 값을, 짝수면 가운데 두 값의 평균을 반환하고, 두 배열이 모두 비어 있으면 undef를 돌려줍니다. 예를 들어 (1,2,3)과 (7,8,9,10)을 합치면 중앙값은 7.0입니다. 이어 Statistics::Basic::Median, Statistics::Descriptive, PDL 같은 통계 모듈을 쓰는 세 가지 변형을 보여줍니다 — 모두 데이터를 모듈에 적재한 뒤 median 함수를 호출하는 동일한 패턴입니다. 이 해법들은 모두 정렬 비용을 동반하므로, 입력이 이미 각각 정렬돼 있다는 조건을 살린 절충안도 제시합니다. 두 배열을 한 번의 패스로 병합하되, 중간 지점에 도달하면 바로 멈추는 방식입니다.

벤치마크: 직접 정렬이 가장 빠르다

100개 원소 배열 두 개를 대상으로 한 측정에서 Statistics::Descriptive(descr)는 38,567/s, 부분 병합(merge)은 75,269/s, Statistics::Basic(basic)은 83,832/s, 직접 정렬(diy)은 222,222/s를 기록했습니다. 저자는 병합 방식이 더 유리할 것이라 예상했지만 결과는 정반대였습니다. Perl의 내장 sort가 병합 정렬 기반이라 이미 정렬된 입력에서는 빠르게 수렴하고, 인터프리트되는 Perl 코드가 아니라 최적화된 컴파일 코드 경로를 타기 때문이라고 분석합니다.

Task 2 — 상자 중첩의 최대 개수

상자가 다른 상자에 들어가려면 두 차원 모두 작아야 합니다. 예시들은 너비 오름차순으로 정렬한 뒤 높이만 추출해 증가 수열을 찾는 방식으로 풀립니다. 예를 들어 ([1,3],[3,5],[6,8],[2,4])는 너비순 정렬 후 높이 (3,4,5,8)이 되어 답은 4입니다. 하지만 저자는 "길쭉하고 납작한 상자가 불편한 위치에 정렬돼 스택을 방해하지 않을까" 확신이 서지 않아 이 문제를 탐색 문제로 취급합니다. 상자 회전이나 큰 상자 안에 작은 상자를 나란히 넣는 경우는 문제 조건에 없으므로 고려하지 않습니다.

Perl 5.44 class 문법과 BFS 탐색

인덱스 0과 1에 의존하는 대신 읽기 쉬운 Box 클래스를 정의합니다. field $w :param(width) :reader처럼 :reader 애트리뷰트로 접근자를 만들고, overload '""'로 문자열 보간 시 표현을 지정하며, canHold 메서드로 한 상자가 다른 상자를 담을 수 있는지 검사합니다. Perl 5.44의 class 기능은 아직 experimental이라 no warnings "experimental::class"로 경고를 끕니다. 탐색은 FIFO 큐 기반 너비 우선입니다. 각 상자를 가장 바깥 용기로 삼아 "지금까지의 스택"과 "안에 들어갈 수 있는 후보 목록"을 큐에 넣고, 꺼낼 때마다 최댓값을 갱신합니다. 후보가 비어 있거나 현재 스택과 남은 후보의 합이 최댓값 이하면 가지치기하고, 그렇지 않으면 다음으로 작은 상자를 하나씩 스택에 추가해 큐를 확장합니다.

원문: dev.to / 번역·요약: Trawling