[Programmers]#Level3_정수 삼각형, DP, 동적 프로그래밍, 동적 계획법

 

[Programmers 알고리즘, C++]#Level 3_정수 삼각형

 

Programmers 알고리즘 문제 풀이, Level3_정수 삼각형

DP를 활용하는 문제

 

---

 

Overview

 

1. 문제
2. 풀이
3. 코드

 

#1. 문제

 

#2. 풀이

1. 동적 계획법

[알고리즘]#5_동적 계획법

 

• [정의] : 동적 계획법은 최적화 문제를 해결하는 데 사용되는 알고리즘 디자인 기법 중 하나입니다. 동적 계획법은 입력 크기에 따라 중복되는 하위 문제를 재귀적으로 해결하고, 이 결과 값들을 기억하는 것으로 중복 계산을 피해 최적화를 수행하고  효율적으로 최적해를 찾아내는 알고리즘입니다.
• [Memoization] : Memoization은 동적 계획법의 한 종류로, 중복 계산을 방지하기 위해 이전의 결과 값들을 기억해 두어 재활용하는 방법입니다. 분할-정복 알고리즘과 비슷하지만, Memoization은 부분 문제의 해를 기억하여 중복 계산을 방지하는데 초점을 맞춥니다.

 

2. Bottom-Up

1. 먼저, 삼각형의 가장 밑변에 위치하는 숫자들 중 서로 인접한 위치에 있는 숫자들끼리 더하며, 그 최대 값을 구합니다.
2. Memoization을 통해 밑변부터 그 최대 값을 기억해두고, 삼각형의 밑변부터 꼭짓점까지 한 단계씩 올라가며, 최종적으로 가장 큰 최대 값을 구합니다.

 

#3. 코드

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

using namespace std;


int solution(vector<vector<int>> triangle) {
    int answer = 0;
    
    // 삼각형의 밑변부터, 주어진 2차원 벡터를 역순으로 순회
    for(int i=triangle.size()-1; i>0; i--)
    {
        for(int j=0; j<i; j++)
        {
            triangle[i-1][j] += max(triangle[i][j], triangle[i][j+1]);
        }
    }
    
    answer = triangle[0][0];
    
    return answer;
}