동적 계획법(DP) 프로그래머스 문제

접근법. DP는 메모리를 사용해서 실행 시간을 줄여야 하는 알고리즘 -> 중간중간의 결과값을 저장해서 실행시간을 줄이는 방법으로 접근하는게 포인트 

 

Level 3

N으로 표현

코딩테스트 연습 - N으로 표현

# dynamic_1.py
N = 5  # 2
number = 12  # 11
# 4, 3


def solution(N, number):
    S = [0, {N}]

    if N == number:
        return 1

    for i in range(2, 9):
        case_set = {int(str(N)*i)}
        for j in range(1, i//2+1):  # S[i_half] S[1]
            for x in S[j]:
                for y in S[i-j]:
                    case_set.add(x+y)
                    case_set.add(x-y)
                    case_set.add(y-x)
                    case_set.add(x*y)
                    if x != 0:
                        case_set.add(y//x)
                    if y != 0:
                        case_set.add(x//y)
        if number in case_set:
            return i
        S.append(case_set)
    return -1


print(solution(2, 11))
print(solution(N, number))

 

Level 3

정수 삼각형

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

# dynamic_2.py
triangle = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]


def solution(triangle):
    def ref(arr1, arr2):
        arr2[0] = arr2[0] + arr1[0]
        arr2[-1] = arr2[-1] + arr1[-1]
        for i in range(1, len(arr2) - 1):
            arr2[i] = max(arr1[i-1], arr1[i]) + arr2[i]

    if len(triangle) == 1:
        return triangle[0][0]
    else:
        for i in range(1, len(triangle)):
            ref(triangle[i-1], triangle[i])

    return max(triangle[-1])


print(solution(triangle))

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])])

 

Level 3

등굣길

 

코딩테스트 연습 - 등굣길

def solution(m, n, puddles):
    # 1부터 시작하는 (1,1) ~ (n, m) 2차원 배열
    memo = [[0 for _ in range(m+1)] for _ in range(n+1)] # 0으로 초기화

    # 주의 ! - 문제에서 주어지는 row, col는 반대
    for col, row in puddles:
        memo[row][col] = -1 # 갈수 없는 물 웅덩이 표시
    memo[1][1] = 1 # 출발 지점 1로 지정

    def dp(row, col):
        if row < 1 or col < 1 or memo[row][col] < 0:
            return 0
        # 이미 계산한 값이 있으면 값을 바로 가져옴
        if memo[row][col] > 0:
            return memo[row][col]

        memo[row][col] = dp(row, col-1) + dp(row-1, col)
        return memo[row][col]

    return dp(n, m) % 1000000007

# def solution(m, n, puddles):
#     answer = 0
#     info = dict([((2, 1), 1), ((1, 2), 1)])
#     for puddle in puddles:
#         info[tuple(puddle)] = 0
#
#     def func(m, n):
#         if m < 1 or n < 1:
#             return 0
#         if (m, n) in info:
#             return info[(m, n)]
#         return info.setdefault((m, n), func(m - 1, n) + func(m, n - 1))
#     return  func(m, n) % 1000000007

 

Level 4

도둑질

코딩테스트 연습 - 도둑질

money = [1, 2, 3, 1, 3]


def solution(money):
    arr1 = [0] * len(money)
    arr1[0] = money[0]
    arr1[1] = max(money[0], money[1])

    for i in range(2, len(money)-1):    # 첫 집을 무조건 터는 경우
        arr1[i] = max(arr1[i-1], money[i]+arr1[i-2])

    arr2 = [0] * len(money)
    arr2[0] = 0
    arr2[1] = money[1]

    for i in range(2, len(money)):  # 마지막 집을 무조건 터는 경우
        arr2[i] = max(arr2[i-1], money[i]+arr2[i-2])

    return max(max(arr2), max(arr1))  # 두 경우 중 최대


def solution1(a):
    x1, y1, z1 = a[0], a[1], a[0]+a[2]      # 첫번째 집을 들릴 때
    x2, y2, z2 = 0, a[1], a[2]          # 마지막 집을 들릴 때
    for i in a[3:]:
        x1, y1, z1 = y1, z1, max(x1, y1)+i      # 인접한 수 중 큰 것을 더하고 x1, y1 초기화
        x2, y2, z2 = y2, z2, max(x2, y2)+i      #
    return max(x1, y1, y2, z2)


print(solution(money))