줄 바꿈(Word Wrap) 문제: 동적 계획법으로 균형 잡힌 텍스트 줄 나누기

줄 바꿈 문제란?

여러 개의 단어로 이루어진 시퀀스가 주어지고, 각 줄에 들어갈 수 있는 최대 문자 수에는 제한이 있습니다. 이때 줄 바꿈 위치를 적절히 조정하여 모든 줄이 깔끔하게 인쇄되도록 만드는 것이 이 문제의 목표입니다.

단순히 글자 수 제한만 지키는 것으로는 부족합니다. 어떤 줄은 여백이 많고 어떤 줄은 여백이 거의 없다면 전체적인 모양이 지저분해 보입니다. 따라서 이 알고리즘은 각 줄의 남는 공간(여분의 공백)을 최대한 비슷하게 분배하여 줄과 줄 사이의 균형을 맞춥니다.

최종적으로 이 알고리즘은 한 줄에 몇 개의 단어를 배치할 수 있는지, 그리고 전체 텍스트를 출력하는 데 몇 줄이 필요한지를 계산해 줍니다.

입력과 출력

Input:
단어 길이 배열 {3, 2, 2, 5}, 최대 폭(maxWidth) = 6
Output:
Line number 1: Word Number: 1 to 1 (첫 번째 단어만 배치)
Line number 2: Word Number: 2 to 3 (두 번째, 세 번째 단어 배치)
Line number 3: Word Number: 4 to 4 (네 번째 단어만 배치)

알고리즘

wordWrap(wordLenArr, size, maxWidth)

입력 − 단어 길이 배열, 배열의 크기(size), 한 줄의 최대 폭(maxWidth)

출력 − 한 줄당 배치되는 단어 목록

동작 원리

이 알고리즘은 세 단계로 진행됩니다.

extraSpace 계산: i번째부터 j번째 단어까지 한 줄에 배치했을 때 남는 공백의 개수를 구합니다.
lineCost 계산: 남는 공백이 음수면 해당 단어들을 한 줄에 넣을 수 없으므로 비용을 무한대(∞)로 설정하고, 마지막 줄은 비용을 0으로, 그 외에는 공백 수의 제곱을 비용으로 둡니다. 공백의 제곱을 사용하면 여백이 불균형할 때 페널티가 커져 자연스럽게 균형 잡힌 배치가 유도됩니다.
totalCost 계산(동적 계획법): j번째 단어까지 배치하는 최소 비용을 bottom-up 방식으로 누적하며, solution 배열에 각 줄의 시작 단어 위치를 기록합니다.

Begin
    define two square matrix extraSpace and lineCost of order (size + 1)
    define two array totalCost and solution of size (size + 1)

    for i := 1 to size, do
        extraSpace[i, i] := maxWidth – wordLenArr[i - 1]
        for j := i+1 to size, do
            extraSpace[i, j] := extraSpace[i, j-1] – wordLenArr[j - 1] - 1
        done
    done

    for i := 1 to size, do
        for j := i+1 to size, do
            if extraSpace[i, j] < 0, then
                lineCost[i, j] = ∞
            else if j = size and extraSpace[i, j] >= 0, then
                lineCost[i, j] := 0
            else
                lineCost[i, j] := extraSpace[i, j]^2
        done
    done

    totalCost[0] := 0
    for j := 1 to size, do
        totalCost[j] := ∞
        for i := 1 to j, do
            if totalCost[i-1] ≠∞ and lineCost[i, j] ≠ ∞ and
               (totalCost[i-1] + lineCost[i,j] < totalCost[j]), then
                totalCost[j] := totalCost[i – 1] + lineCost[i, j]
                solution[j] := i
        done
    done
    display the solution matrix
End

C++ 구현 예제

#include<iostream>
using namespace std;

int dispSolution (int solution[], int size) {
    int k;
    if (solution[size] == 1)
        k = 1;
    else
        k = dispSolution (solution, solution[size]-1) + 1;
    cout << "Line number "<< k << ": Word Number: " <<solution[size]<<" to "<< size << endl;
    return k;
}

void wordWrap(int wordLenArr[], int size, int maxWidth) {
    int extraSpace[size+1][size+1];
    int lineCost[size+1][size+1];
    int totalCost[size+1];
    int solution[size+1];

    for(int i = 1; i<=size; i++) {      //모든 줄의 여분 공백 계산
        extraSpace[i][i] = maxWidth - wordLenArr[i-1];

        for(int j = i+1; j<=size; j++) {   //i번째부터 j번째 단어까지 한 줄에 넣을 때의 여분 공백
            extraSpace[i][j] = extraSpace[i][j-1] - wordLenArr[j-1] - 1;
        }
    }

    for (int i = 1; i <= size; i++) {   //계산된 여분 공백 배열로 줄 비용(line cost) 산출

        for (int j = i; j <= size; j++) {

            if (extraSpace[i][j] < 0)
                lineCost[i][j] = INT_MAX;
            else if (j == size && extraSpace[i][j] >= 0)
                lineCost[i][j] = 0;
            else
                lineCost[i][j] = extraSpace[i][j]*extraSpace[i][j];
        }
    }

    totalCost[0] = 0;
    for (int j = 1; j <= size; j++) {   //단어 배치의 최소 비용 계산
        totalCost[j] = INT_MAX;

        for (int i = 1; i <= j; i++) {
            if (totalCost[i-1] != INT_MAX && lineCost[i][j] != INT_MAX && (totalCost[i-1] + lineCost[i][j] < totalCost[j])){
                totalCost[j] = totalCost[i-1] + lineCost[i][j];
                solution[j] = i;
            }
        }
    }

    dispSolution(solution, size);
}

main() {
    int wordLenArr[] = {3, 2, 2, 5};
    int n = 4;
    int maxWidth = 6;
    wordWrap (wordLenArr, n, maxWidth);
}

실행 결과

위 코드를 실행하면 단어 길이가 {3, 2, 2, 5}이고 최대 폭이 6일 때, 다음과 같이 균형 잡힌 줄 배치 결과가 출력됩니다.

Line number 1: Word Number: 1 to 1
Line number 2: Word Number: 2 to 3
Line number 3: Word Number: 4 to 4