[프로그래머스] '정수 삼각형' 알고리즘 풀이 - Python

Contents

1. 문제 설명
   
   [제한사항]
   
   [입출력 예]
2. 알고리즘 분석 
   
   [나의 풀이]
   
   [Most 1 의 풀이]

---

 

문제 설명

 

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

알고리즘 분석

 

풀이를 작성하기에 앞서 확실하게 알고 넘어가야하는 부분이 있습니다. 

 

그것은 바로 '동적 계획법(Dynamic Progamming)'입니다.

 

동적 계획법은 간단하게 말해서 큰 문제를 여러개의 작은 문제로 나눠서 푸는 것입니다. 여러개의 하위 문제를 푼 결과를 종합하여 큰 문제를 해결하는 것이죠. 

 

주로 최단 경로 문제, 행렬의 제곱 문제 등을 풀기위해 사용됩니다. 

 

동적 계획법의 구현 방식에는 두가지 방법이 있습니다. 

1. Top-down : 큰 문제를 작은 문제로 쪼개면서 푼다. 재귀로 구현
2. Bottom-up : 작은 문제부터 차례대로 푼다. 반복문으로 구현

이번에는 이 두가지 방법을 모두 사용해서 문제를 풀어보겠습니다. 

 

 

• 나의 풀이

# 재귀함수로 구현한 솔루션 
def dynamic(triangle, xidx, yidx):
    t_len = len(triangle) - 1
    if t_len > xidx: # 현재 숫자를 아래 두 숫자에 각각 더했을 때, 큰값을 반환 
        return max(triangle[xidx][yidx] + dynamic(triangle, xidx + 1, yidx),
                   triangle[xidx][yidx] + dynamic(triangle, xidx + 1, yidx + 1))
    else: # t_len == xidx가 되면 재귀의 끝에 도달했으므로 끝의 숫자를 반환 
        return triangle[xidx][yidx]

def solution(triangle):
    answer = dynamic(triangle, 0, 0)
    return answer
    
# 반복문으로 구현한 솔루션
def solution(triangle):
    for i in range(1, len(triangle)): # 세로
        for j in range(i+1):  # 가로
            if j == 0: 
                triangle[i][j] += triangle[i-1][j]
            elif j == i:
                triangle[i][j] += triangle[i-1][j-1]
            else: # 중간의 숫자들은 두개의 경우 중 큰값을 사용한다. 
                triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])
    return max(triangle[-1])

이렇게 두개의 방식으로 풀어보았습니다. 

 

그렇다면 여기서 '재귀' vs 'for문' 중에 어떤 코드가 더 효율적인가? 

 

정답은 'for문' 입니다. 실제로 재귀함수로 구현한 코드는 프로그래머스에서 탈락합니다. 정답은 틀리지 않았지만 시간이 너무 오래걸리네요. 동적계획법을 재귀함수로 구현할 때, 효율을 높혀주는 메모제이션(Memoization)도 사용하지 않아서 더 오래걸리는 것 같습니다. 

 

 

• Most 1의 풀이

solution = lambda t, l = []: max(l) 
if not t else solution(t[1:], [max(x,y)+z for x,y,z in zip([0]+l, l+[0], t[0])])

 

황당하게 한 줄(가독성을 높이기 위해 두 줄로 나눴습니다)로 푼 코드도 있습니다.  이 코드도 재귀함수로 구현되었는데, 한 줄짜리 코드임에도 위의 두 코드보다 효율성이 좋습니다... 

 

결국 재귀함수가 이겼군요... 

 

위의 코드를 읽기 쉽게 함수로 표현해보았습니다.

 

def solution(triangle, l = []):
    if not triangle:
        return max(l)
    else:
        return solution(triangle[1:], [max(x,y)+z for x,y,z in zip([0]+l, l+[0], triangle[0])])

 

원래 제 코드보다 훨씬 효율성이 뛰어나고 가독성도 좋은 코드가 나왔습니다.