줄바꿈 최적화(그리디 vs 최적) 계산기

아닙니다. 브라우저와 대부분의 편집기가 쓰는 그리디는 한 줄에 들어갈 만큼 넣고 안 들어가면 넘기는 방식이라, 앞 줄을 꽉 채우려는 판단이 뒤 줄을 크게 비게 만드는 일이 잦습니다. 너비 11에 aaa bb cc dddd를 넣으면 그리디는 벌점 53, 최적은 41입니다. 줄 수는 둘 다 2줄로 같고 균형만 다릅니다.

줄마다 남는 칸의 제곱을 더한 값(벌점)이 작을수록 좋다고 봅니다. 그냥 더하면 어떻게 나눠도 합이 거의 같아 구별이 안 갑니다. 제곱으로 매기면 한 줄이 크게 비는 것을 여러 줄이 조금씩 비는 것보다 훨씬 나쁘게 보므로, 오른쪽 끝이 고르게 맞는 배치가 이깁니다.

동적 계획법입니다. dp[i]를 «낱말 i부터 끝까지의 최소 벌점»으로 두면 dp[i] = min_j (벌점(i..j) + dp[j+1])입니다. 첫 줄에 어디까지 넣을지를 모두 시도하고 나머지는 이미 구한 답을 씁니다. 이 계산기는 낱말이 18개 이하일 때 모든 줄바꿈 조합(2^(n−1)가지)을 전수로 세어 같은 값이 나오는지 함께 확인합니다.

문단의 마지막 줄은 원래 짧기 때문입니다. 그것까지 벌점에 넣으면 마지막 줄을 채우려고 앞 줄들을 억지로 늘리게 되어 오히려 어색해집니다. TeX도 마지막 줄에는 벌점을 매기지 않습니다. 이 계산기는 두 방식을 모두 골라 볼 수 있게 해 두었습니다.

뼈대만 같습니다. 크누스–플라스 알고리즘은 낱말 사이 공백을 늘였다 줄였다 할 수 있는 «고무줄»로 보고, 하이픈 넣기·연속된 줄의 하이픈 벌점·문단을 넘기는 벌점까지 함께 최소화합니다. 이 계산기는 «문단을 통째로 보는 동적 계획법»이라는 핵심만 다룹니다.

어디에 두어도 줄을 넘치므로 혼자 한 줄을 쓰게 하고 벌점을 매기지 않습니다. 실제 조판에서는 이 자리에서 하이픈을 넣거나 글자를 잘라 넣습니다. 이 계산기는 그 줄을 «넘침»으로 표시합니다.

푸는 문제가 다릅니다. 텍스트 폭 계산기는 «이 글자열이 이 글꼴에서 몇 픽셀인가»를 잽니다. 이 계산기는 폭이 이미 정해졌다고 보고 «어디서 줄을 바꿀 것인가»를 정합니다. 폭을 무엇으로 재든 알고리즘은 그대로이므로, 픽셀 폭이 필요하면 그쪽에서 재어 여기에 넣으면 됩니다.

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