팬케이크 정렬(뒤집기 횟수) 계산기

임의의 두 원소를 바로 교환할 수 없고, "맨 앞부터 k개를 통째로 뒤집는다"는 연산 하나만 허용됩니다. 세는 것도 원소 비교 횟수가 아니라 이 뒤집기(플립) 횟수입니다.

아직 정렬 안 된 범위에서 가장 큰 값을 찾아, 맨 앞에 없으면 먼저 맨 앞으로 뒤집어 올린 뒤, 범위 전체를 뒤집어 그 값을 제자리(범위의 맨 끝)로 보냅니다. 범위를 하나씩 줄여 가며 반복하면 최대 2n−3번(n≥2) 안에 끝납니다.

한 바퀴에 최대 2번(맨 앞으로 올리기 + 제자리로 보내기)씩, n−1바퀴를 돌면 얼핏 2(n−1)=2n−2번처럼 보입니다. 하지만 마지막 바퀴(남은 2개)는 최대 1번이면 충분해 상한이 2n−3번으로 줄어듭니다. 이 상한을 처음 증명한 논문(Gates & Papadimitriou, 1979)이 빌 게이츠가 하버드 학부 시절 쓴 유일한 학술논문으로 유명합니다.

아닙니다. 그리디는 "충분히 좋은" 해를 빠르게 찾을 뿐이고, 정말로 최소 횟수를 구하는 문제 자체는 NP-난해로 알려져 있습니다(Bulteau, Fertin & Rusu, 2015). 이 계산기는 n≤8까지는 순열 전체(n!가지) 상태공간에서 너비우선탐색(BFS)으로 진짜 최적해를 구해 그리디와 비교해 보여 줍니다.

상태 수가 n!로 늘어나기 때문입니다. 8!(=40,320)까지는 브라우저에서 감당할 수 있지만, 9!(=362,880)부터는 매 상태마다 최대 n번의 플립을 시도해야 해서 계산이 무거워집니다. 그 이상에서는 그리디 결과만 보여 줍니다.

너비우선탐색은 정의상 가중치 없는 그래프에서 최단 경로를 찾는 알고리즘입니다. 상태(순열)를 정점, 플립을 간선으로 보면 이 문제는 정확히 그 형태이므로, 별도의 정답지 없이도 BFS가 찾은 경로가 최소 횟수임이 보장됩니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이뤄지고 입력값은 이 기기에만 남습니다.