문제 링크: https://www.acmicpc.net/problem/1932

문제 상황

            7
          3   8
        8   1   0
      2   7   4   4
    4   5   2   6   5

위 예시와 같은 정수 삼각형이 입력으로 주어지게 된다. 가장 꼭대기에 있는 숫자부터 시작해서 인접한 아래 숫자(대각선 왼쪽 또는 대각선 오른쪽)를 경유하며 가장 아래층까지 내려온다. 이때 경로를 지나는 수들의 합이 최대가 되도록 내려올 때 그 합을 구하라.

입력

Line 1: 삼각형의 크기 \(n(1 ≤ n ≤ 500)\)

Line 2~(n+1): 정수 삼각형이 각 행 별로 주어진다.

출력

합이 최대가 되는 경로에 있는 수의 합을 출력한다.

C99로 구현하였다.

1. 문제 해결 전략

문제에 주어진 예시를 통해 문제해결전략을 연구해보자. (위에서부터 1층이라 부르자.) 우선 컴퓨터 없이 직접 문제를 푼다 생각하고 푸는 방법을 연구해보자.

1. 1층에서 7로 시작한다.
2. 2층의 3으로 오는 경우나 8로 오는 경우나 7로부터 온다.
   • 3: \(7+3=10\)
   • 8: \(7+8=15\)
3. 3층의 경우
   • 8: 3에서 온 합 10 밖에 없다. \(10+8=18\)
   • 1: 3에서 온 합 10과 8에서 온 합 15 중 15가 더 크니 \(15+8=23\)
   • 0: 8에서 온 합 15 밖에 없다. \(15+0=15\)
4. 4층의 경우
   • 2: 8에서 온 합 18 밖에 없다. \(18+2=20\)
   • 7: 8에서 온 합 18과 1에서 온 합 23 중 23이 더 크니 \(23+7=30\)
   • 4: 1에서 온 합 23과 0에서 온 합 15 중 23이 더 크니 \(23+4=27\)
   • 4: 0에서 온 합 15 밖에 없다. \(15+4=19\)
5. 5층의 경우
   • 4: 2에서 온 합 20 밖에 없다. \(20+4=24\)
   • 5: 2에서 온 합 20과 7에서 온 합 30 중 30이 더 크니 \(30+5=35\)
   • 2: 7에서 온 합 30과 4에서 온 합 27 중 30이 더 크니 \(30+2=32\)
   • 6: 4에서 온 합 27과 4에서 온 합 19 중 27이 더 크니 \(27+6=33\)
   • 5: 4에서 온 합 19 밖에 없다. \(19+5=24\)

마지막 5층에서 최종 합이 35가 가장 크므로 35가 정답이다.

1.1 문제해결전략 구현

int N,triangle[??][??]={0,}, sum[??][??]={0,};
scanf("%d",&N);
for(i=0;i<N;++i)
  for(j=0;j<=i;++j)
    scanf("%d",triangle[i]+j);

우선 위와 같은 방법로 정수삼각형의 데이터를 입력받아 저장했을때, 위에서 직접 머리로 풀어본 방법을 코드로 옮겨보자.

int max = max(sum[i-1][j-1],sum[i-1][j]);
sum[i][j] = triangle[i][j] + max;

뭐 대충 이렇게 구현하면 될거 같다. 반복문에 넣어서 삼각형 전 층을 탐색하도록 만들어 주자.

int i,j,max=0;
for(i=0;i<N;++i){
  for(j=0;j<=i;++j){
    max=sum[i-1][j-1];
    if(sum[i-1][j]>max)
    	max=sum[i-1][j];
    sum[i][j]=triangle[i][j]+max;
  }
}

어림도 없다! 암!! 아암!!!

항상 유효한 index범위를 참조하는지 확인해야한다.

int i,j,max=0;
sum[0][0]=triangle[0][0];
for(i=1;i<N;++i){
  for(j=0;j<=i;++j){
    if(j!=0) max=sum[i-1][j-1];
    else max=0;
    if(sum[i-1][j]>max)
    	max=sum[i-1][j];
    sum[i][j]=triangle[i][j]+max;
  }
}

꽤 깔끔했던 것 같은데 유효하지 않은 -1 index 참조를 방지하기위해 조건을 달면서 지저분해졌다. 어쨌든 이제 코드를 합쳐보자.

int N,triangle[500][500]={0,}, sum[500][500]={0,};
int i,j,max=0;
scanf("%d",&N);
for(i=0;i<N;++i)
  for(j=0;j<=i;++j)
    scanf("%d",triangle[i]+j);
    
sum[0][0]=triangle[0][0];
for(i=1;i<N;++i){
  for(j=0;j<=i;++j){
    if(j!=0) max=sum[i-1][j-1];
    else max=0;
    if(sum[i-1][j]>max)
    	max=sum[i-1][j];
    sum[i][j]=triangle[i][j]+max;
  }
}

for(max=i=0;i<N;++i)
  if(sum[i]>max) max=sum[i];
printf("%d",max);

2. Dynamic Programming : 동적 계획법

사실 자연스럽게 메모이제이션을 통한 동적계획법으로 문제를 풀었다. 앞서 살펴본 예시에서도 볼 수 있지만, 한번 구한 합계를 두번 쓸 일도 있다. 그래서 sum이라는 ‘해당 요소를 거쳐갈 때 나올 수 있는 최대 합계’를 저장하는 배열을 만들어 미리 저장해놨다가 그 다음 최대 합계를 구할 때 잘 이용하였다.

만약 이 문제를 재귀함수 호출로 풀었다면… 그래도 제한 시간을 만족할 것 같긴 하지만… 비효율적이다… 굳이 해보고 싶진 않다.

파이썬 알고리즘 인터뷰 p.624, 책만, 2020

Dynamic Programming, 동적계획법은 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다. 주어진 문제를 부분 문제로 나누어 각 부분 문제의 답을 계산하고, 이 계산한 결과값을 이용해 원래 문제의 답을 산출하는 접근 방법인 분할정복, 동일한 계산을 반복해야 할 경우 한 번 계산한 결과를 메모리에 저장해 두었다가 꺼내 씀으로써 중복 계산을 방지하는 메모이제이션(Memoization) 등이 이에 해당한다.

앞서 작성한 코드도 경로를 탐색할때 매번 합계를 구하지 않고, 구한 합계를 저장해두었다가 필요할때마다 꺼내 쓴 메모이제이션에 해당한다.

2-1. 최적화

재귀적으로 구현하지 않고 메모이제이션을 통해 필요한 정보를 그때그때 저장하고 꺼내써 불필요한 연산을 방지하여 시간비용을 줄였으나 대신 메모리라는 공간비용을 사용하게 되었다. 숫자가 크지 않아 공간비용이 크지 않지만, 낭비하고 있는 공간이 꽤 있다. 한번 쓰고 버리는 공간들을 찾아보자.

우선 공간비용을 크게 잡아먹는 triangle과 sum을 살펴보아야 할 것 같다. triangle은 언제 사용하는지 주목하자.

sum[i][j]=triangle[i][j]+max;

삼각형 데이터를 입력받을 때를 제외하곤 이 때가 유일하다. 이후 쓸데없이 공간을 차지하고 있다가 main함수가 반환되는 시점에 stack에서 사라질 뿐이다. 때문에 조금만 손보면 sum이라는 저장공간을 쓰지 않고 문제를 해결할 수 있다.

int max = max(triangle[i-1][j-1],triangle[i-1][j]);
triangle[i][j] += max;

triangle에 데이터를 입력받아 놓은 상태지만, 합계를 계산하며 덮어 씌웠다. 어차피 다음에 그 값을 다시 찾을 일이 없고, 합계만 필요하니 아무런 문제가 없다. 하지만 아직 끝이 아니다. 이전의 sum[i-1], 지금 바꾼 코드에서의 triangle[i-1] 역시 저때 한번 최대 합계를 구할 때 쓰고 쓰이지 않는다. 꼼수를 써보자.

int N,triangle[500]={0,}, prev[500]={0,}, tmp[500]={0,};
int i,j,max=0;
scanf("%d",&N);

for(i=0;i<N;++i){
    memcpy(tmp,prev,500*sizeof(int));
    memcpy(prev,triangle,500*sizeof(int));
    memcpy(triangle,tmp,500*sizeof(int));

    for(j=0;j<=i;++j){
        max = (j ? prev[j-1] : 0);
        if(prev[j]>max) max=prev[j];
        
        scanf("%d",triangle+j);
        triangle[j]+=max;
    }
}

for(max=i=0;i<N;++i)
  if(triangle[i]>max) max=triangle[i];
printf("%d",max);

데이터 입력과 합계를 구하는 연산은 사실 한번에 처리가 가능하기 때문에 같은 반복문 안에서 처리하였다. 어차피 이전 층까지의 각 합계들과 현재 층 숫자만 알면 되기 때문에 한 줄을 충분히 저장할 공간 2개와 swap용 임시 저장공간만 선언했다. 계속 두 배열공간을 swap하고 재활용하면 된다. 덕분에 불필요한 공간을 줄였다.

3. Pointer Swap

하지만 앞선 단계에서 빈번한 swap으로 인한 memcpy의 오버헤드를 간과하였다. memcpy가 빠르긴 하다만 \(500×4\) byte의 공간을, 3번씩, \(2^N-1\) 회씩 복사하는 작업은… 부담스럽다. 그런데 C에서는 이 부담스러운 크기의 배열 복사를 간단히 해결하고 있다. (사실 복사는 아니다.)

잘 알다시피 함수의 매개변수로 전달될 때 일반 변수와 배열은 차이가 있다.

물론 C언어에 Call by reference는 없다. 모두 call by value이다. 모든 함수의 매개변수들은 그 함수의 정적 변수로서 생성되고 그 매개변수로 전달 받은 값이 복사되었다가, 함수의 반환과 함께 stack에서 사라지는 변수들이다. 일반 변수이든, 포인터이든.

하지만 배열이 함수 인자로 들어오는 경우, 모든 원소들이 복사되어 그 함수의 스택에 생성되지 않는다. 그냥 주소값이 전달되어 포인터에 복사될뿐. (값이 전달되었기 때문에 여전히 값에 의한 호출이다.) 덕분에 참조에 의한 호출도 아니고, 값을 반환하지도 않지만 함수 외부의 변수에 접근 및 쓰기가 가능하다.

배열과 포인터는 밀접한 관계를 가지고 있다. 사실 위에서 쓰인 수준의 배열 원소 접근 및 연산 수준은 포인터로 대신하더라도 가능하다. 때문에 기존의 배열공간은 따로 선언후 그대로 두고, triangle, prev라는 포인터를 선언후 각각을 참조하게 하고, 매 반복시마다 포인터의 주소값만 교환해주자. 그럼 메모리 저장공간은 그대로여서 비싼 메모리 복사비용이 들지 않겠다. 또 한 포인터에 계속 메모리주소가 번갈아 가며 저장되므로, 접근하는 데이터는 앞서 구현한 것과 동일하다!

3-1. 최종 코드

어차피 필요한 공간은 입력되는 N에 따라 가변적이므로 동적 메모리 할당으로 바꿔주었다.

#include <stdio.h>
#include <malloc.h>

int main(void){
    int N,i,j,max,*triangle,*prev,*tmp;
	
    scanf("%d",&N);
    prev=calloc(N,sizeof(int));
    triangle=calloc(N,sizeof(int));
    
    for(i=0;i<N;++i){
    	tmp=prev; prev=triangle; triangle=tmp;
        
        for(j=0;j<=i;++j){
            max = (j ? prev[j-1] : 0);
            if(prev[j]>max) max=prev[j];
            
            scanf("%d",triangle+j);
            triangle[j]+=max;
        }
    }
    
    for(max=i=0;i<N;++i)
    	if(triangle[i]>max) max=triangle[i];
    printf("%d",max);
    
    free(prev); free(triangle);
    return 0;
}

제출 소스 확인하기