알고리즘 마지막날! 풀었다!
https://programmers.co.kr/learn/courses/30/lessons/43105?language=python3
프로그래머스의 정수삼각형문제... 이걸 응용해서 풀라고 하면 못풀었겠지만 이미 튜터님과 함께 메모이제이션으로도 풀어보고 이코테에서 Overlapping Subproblem도 적용해봤고 백준 제출용으로 인풋케이스 변환도 몇번이나 해본 문제라 무척 쉽게 풀었다.
문제
위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.
삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.
풀이
def solution(triangle):
answer = 0
INF = int(1e9)
N = len(triangle)
tri = triangle # 2차원배열을 만든다음에
memo = [[INF] * (i + 1) for i in range(N)] # 메모배열!
memo[0][0] = tri[0][0] # 첫번째칸에는 삼각형의 첫번째 값을 넣어줌
def make(r, c): # 행은 가로 열은 세로!
if not (0 <= r < N and 0 <= c < len(tri[r])):
return 0 # 삼각형의 범위를 벗어나면 0을 반환해!
if memo[r][c] != INF: # 메모에 적혀있다면 적힌 값을 반환해!
return memo[r][c]
memo[r][c] = tri[r][c] + max(make(r - 1, c - 1), make(r - 1, c))
return memo[r][c] # 메모에 안적혀있다면 있는값에다가
# 위에꺼 - 위에옆에꺼 중에 max값을 찾아 더해줘!
for c in range(N): # for문을 돌린다!
make(N - 1, c)
answer = max(memo[N - 1])
return answer핵심 1 - '거쳐간' 숫자의 최대값 구하기!
이건 문제를 쪼개는 개념인데 삼각형은 아래칸으로 이동할 때 두가지 패스로밖에 못간다.
그래서 두개 패스 [r-1, c-1]과 [r -1, c] 중 맥스값만 누적에 계속 더해주는 방식으로 푼다.
핵심 2 - 모험을 기록하는 매크로를 만들자!
이때 빈 메모장(정확히는 메모이제이션 용 무한값이 담긴 메모장)에 패스가 기록되어 있지 않을때만 적어주면서 memo에다가 효율적으로 모든 경로를 입력한다. 시뮬레이션 게임 할때 cg 회수하듯이!
주어진 삼각형의 값과 다 돌았을 때 memo의 값
print(triangle)
[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
print(memo)
[[7], [10, 15], [18, 16, 15], [20, 25, 20, 19], [24, 30, 27, 26, 24]]핵심 3 - 거쳐간 숫자의 "최대값" 구하기!
모든 가능한 경로의 누적값이 표시된 메모장에서 이제 최대값만을 골라 출력해주면 된다.
파이썬의 슬라이싱을 이용해서 마지막 배열로 접근 후, max 함수를 써주면 끝!
