[프로그래머스 level3] 정수 삼각형 | Python (동적계획법)

🔒 문제

https://school.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

 

---

🔓 풀이

🔑 문제 해결 / 코드

def solution(triangle):
    n = len(triangle) - 1
    # 0층은 계산할 필요가 없어서 1층부터 시작
    floor = 1
    index = 0
    
    # 0층       7
    # 1층     10 15
    # 2층    18 16 15
    # 3층   20 25 20 19
    # 4층  24 30 27 26 24

    while True:
        # 해당층 마지막 원소    
        if index == len(triangle[floor]) - 1:
            triangle[floor][index] += triangle[floor-1][index-1]
            # 마지막 층이면 while문 탈출
            if floor == n:
                break
            else:
                floor += 1
                index = 0
                continue
        
        # 연산: 현재 원소의 인덱스가 0이라면 전층의 인덱스 0의 원소와 더하기
        # 아니라면, 전층의 현재 원소 인덱스 - 1의 원소와 현재 원소 인덱스의 원소 중 큰 수와 더하기
        if index == 0:
            triangle[floor][index] += triangle[floor-1][index]
        else:
            if triangle[floor-1][index] >= triangle[floor-1][index-1]:
                triangle[floor][index] += triangle[floor-1][index]
            else:
                triangle[floor][index] += triangle[floor-1][index-1]
        # 다음 원소 검사
        index += 1
    return max(triangle[-1])
    
print(solution([[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]))

---

🍏 Story

이 문제를 풀면서 동적계획법 이란 단어를 처음 들어봐서 구글에 검색을 해봤다.

최적화 이론의 한 기술이며, 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다.

조금 장난스럽게 말해서 답을 재활용하는 거다. 앞에서 구했던 답을 뒤에서도 이용하고, 옆에서도 이용하고...엄밀히 말해 동적 계획법은 구체적인 알고리즘이라기보다는 문제해결 패러다임에 가깝다. 동적 계획법은 "어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는" 방식의 알고리즘을 총칭한다.

답을 구하기 위해서 했던 계산을 또 하고 또 하고 계속해야 하는 종류의 문제의 구조를 최적 부분 구조(Optimal Substructure)라고 부른다. 동적 계획법은 이런 문제에서 효과를 발휘한다.

 

동적계획법에 대해 읽어보던 중 최적 부분 구조라는 단어도 생소해서 찾아보니 그리디와 관련이 있었다.

문제의 최적 해결 방법은 부분 문제에 대한 최적 해결 방법으로 구성된다. 이러한 구조를 최적 부분 구조라 한다.

 

처음엔 감이 잡히지 않아서 손에 잡히는 대로 코딩을 하다 보니,, 완전 탐색 형식의 알고리즘을 작성했다. 

모든 경우의 수를 구해서 가장 큰 값을 리턴했고, 당연하게도 효율성이 나쁜 코드였다.

# 전역 변수인 answer를 함수안에서 막 참조하니 문제 풀기위한 방법이긴 해도 좋은 코드는 아니다
answer = []

def special_solution(triangle, floor, max_floor, index=0, result=0):
    if floor == max_floor:
        answer.append(triangle[floor][index] + result)
        return
    special_solution(triangle, floor+1, max_floor, index, result+triangle[floor][index])
    special_solution(triangle, floor+1, max_floor, index+1, result+triangle[floor][index])


def solution(triangle):
    special_solution(triangle, 0, len(triangle)-1)
    return max(answer)

 

이건 아니다 싶어서 동적계획법의 설명을 다시 읽어보던 중 문제를 쪼개고, 답을 재활용한다는 키워드로 아이디어가 떠올랐다.

 

🍎 Idea

그림의 문제를 쪼개서 생각해보니 해법이 보였다. 

 

이 문제에서 7(0층)부터 시작해 마지막 층까지 합을 구할 때 총 3가지 패턴이 존재한다. 

 

1. 현재 층의 0번째 인덱스의 원소는 무조건 전 층의 0번째 인덱스의 원소와 더해야 한다.

2. 현재 층의 마지막 인덱스의 원소는 무조건 전 층의 마지막 인덱스의 원소와 더해야 한다.

3. 위 두가지 경우의 수를 제외한 원소는 2개의 경우의 수가 생긴다.

    - 전 층의 현재 인덱스의 원소와 더하기

    - 전 층의 현재 인덱스에 1을 뺸 인덱스의 원소와 더하기

 

3번의 패턴에서는 그리디 방법을 통해 2가지 경우에서 가장 큰 수와 더하게 되면  큰 피라미드가 작은 피라미드로 쪼개지게 되고, 작은 피라미드에서 구한 값을 큰 피라미드 결과를 구하기 위해 계속 사용되어 동적 계획법에 따른 알고리즘이 만들어졌다.

 

위 그림으로 예를 들면 더 이해가 쉬울거라 생각한다.

0층의 7은 이전에 더할 층이 없으므로 7이 된다. (계산 로직에서 제외, 코드에서도 0층이 아닌 1층부터 시작한다)
1층의 3과 8은 1,2번 패턴에 의해 더할 값이 7로 제한된다. 따라서 10 15가 되는 게 최적이다.
2층의 8 1 0 중 8은 1번패턴 0은 2번 패턴으로 계산되고 1은 3번 패턴에 의해 계산된다. 
2층은
    8은 10을 더해서 18
    1은 10과 15중 큰 수와 더해서 16
    0은 15를 더해서 15
가 되는게 최적이다.

이렇게 계산을 이어가다 보면 4층에서는 24 30 27 26 24가 최적이 되고 가장 큰 수는 30이다.

 

 

JS언어로도 풀어보고 싶지만 이 문제에서는 지원하지 않아서 PASS

 

 

🥦 참고자료

https://namu.wiki/w/%EB%8F%99%EC%A0%81%20%EA%B3%84%ED%9A%8D%EB%B2%95#toc

동적 계획법 - 나무위키