프로그래머스 동적 계획법 정수 삼각형 c++ 풀이

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/43105

코딩테스트 연습 - 정수 삼각형

 

 

문제 설명

 

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

입출력 예

triangle	result
[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]	30

 

 

 

문제 풀이

오답 1: 그냥 전탐색

걍 전탐색 아닐까.. 하고 풀어봤다

#include <string>
#include <vector>

using namespace std;

void recursive(vector<vector<int>> &triangle, int i, int j, double current, int &answer) {
    if (i == triangle.size()-1) {
        int result =  current + triangle[i][j];
        if (answer < result) {
            answer = result;
        }
    } else {
        recursive(triangle, i +1, j, current + triangle[i][j], answer);
        recursive(triangle, i +1, j+1, current + triangle[i][j], answer);
    }
}

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    recursive(triangle, 0,0,0, answer);
    
    return answer;
}

예상은 했지만 정확성에서도 시간 초과가 나다니 심각하다

 

오답 2: 메모화

중복 연산이 될만한게 있나..? 하고 곰곰히 생각해봤지만 아무리 생각해봐도 중복은 없다.

중복은 없었지만 필요 없는 연산은 있었다.

삼각형의 각 원소들은 원소까지의 경로들을 가진다.
해당 원소에서 부터 아래로의 경로는 이전까지의 경로와 아무런 연관관계가 없다.
따라서 어떤 원소까지의 합이 최댓값이 아니라면 이후의 경로들은 연산할 필요가 없다.

이를 구현하기 위해 각 원소까지의 합 중 최댓값을 저장하는 maxMemArr를 만들고 최댓값보다 작거나 같으면 이후의 탐색을 종료했다.

(글 쓰다가 중간에 날려먹어서 코드가 없습니다.)

정확성은 만점인데 효율성이 빵점이었다...

이 방법도 아니군

 

정답: bottom-up (상향식)

너무 생각이 안나서 몇 개월만에(교수님 죄송합니다,,,) 탑코더 책을 펼쳤다.
동적 계획법을 풀이하는 방법은 여러가지가 있는데 그 중 하나가 상향식 방법이라고 한다.

이 정수 삼각형 문제도 상향식으로 풀이하면 간단하게 해결된다!
사실 오답 2의 '최대 합을 가지는 경로만 연산한다'는 것과 비슷한 발상인데, 상향식 해법은 더 확실하게 '계산을 정리해서 같은 계산을 정확리 한 번만 수행'한다.

하향식 방법에서는 그리디하게 더 큰 자식을 고르기만 하면 최댓값을 구할 수 없지만(따라서 전탐색을 해줘야 한다. 오답 2의 방식에서도 최댓값을 찾기 전까지는 경로를 끝까지 조사한다.), 만약 자식에서부터 올라와서 어떤 자식 원소에 대해 이후 경로까지의 최대 합을 구할 수 있다면 부모는 그냥 더 큰 값을 가지는 경로(자식이 아니라 경로!)를 고르면 되는 것이다.

7
3    8
8     1     0

이런 삼각형이 있다고 하면, triangle[1][0]인 3까지의 경로 중(자식에서부터) 최대 합은 8에서부터 시작한 11일 것이다.
같은 방식으로 triangle[1][1]인 8의 최대 합은 1에서 시작한 9이다.

7
11    9

마찬가지로 7까지의 경로 중 최대 합을 가지는건 11을 거치는 18이다.

18

이를 구현한 코드는 다음과 같다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution (vector < vector < int > >triangle)
{
  for (int i = triangle.size () - 2; i > -1; i--)
      for (int j = 0; j < triangle[i].size (); j++)
    	  triangle[i][j] = triangle[i][j] + max (triangle[i + 1][j], triangle[i + 1][j + 1]);

  return triangle[0][0];
}

 

 

다른 사람의 코드

생략

 

 

후기

n을 삼각형의 깊이라고 할 때, 오답 1의 경우 시간 복잡도는 O(2^n) 이다.

오답 2의 경우 1보다는 조금 낫겠지만,,, 어쨌든 해당 원소에 대해 최댓값이 나올 때 까지는 끝까지 탐색을 해야하므로 느리다.
또 적어도 정수 삼각형의 배열 크기만큼은 배열을 하나 더 사용해야 하므로 공간복잡도도 생각해봐야 한다.

마지막 정답 코드의 시간 복잡도는 O(n^2) 으로, O(2^n)에 비하면 매우 양호한 수준이다.

3단계인 것 치고 구현은 쉬웠지만 발상까지가 어려운 문제였다. 내가 쪼랩이라 그런걸지도...
암튼 종강도 했으니 이제 알고리즘 공부뿐이야...(아님)
모두 홧팅~!!