[프로그래머스/고득점Kit] 동적계획법(Dynamic Programming)

동적계획법(Dynamic Programming)

불필요한 계산을 줄이고, 효율적으로 최적해를 찾아야만 풀리는 문제들입니다.

출제 빈도	평균 점수	문제 세트
낮음	낮음	3 / 5

N으로 표현

코드

def solution(N, number):
    total_set = []
    
    for cnt in range(1, 9):
        sub_set = set()
        sub_set.add(int(str(N) * cnt))
        
        for i in range(cnt - 1):
            for a in total_set[i]:
                for b in total_set[-i - 1]:
                    sub_set.add(a + b)
                    sub_set.add(a - b)
                    sub_set.add(a * b)
                    
                    if b != 0:
                        sub_set.add(a / b)
        if number in sub_set:
            return cnt
        
        total_set.append(sub_set)
        
    return -1

아이디어 & 풀이

---

정수 삼각형

코드

def solution(triangle):
    n = len(triangle)
    dp = [[0] * (i + 1) for i in range(n)]
    
    dp[0][0] = triangle[0][0]
    
    for i in range(1, n):
        for j in range(i + 1):
            if j == 0:
                dp[i][j] = dp[i - 1][j] + triangle[i][j]
            elif j == i:
                dp[i][j] = dp[i - 1][j - 1] + triangle[i][j]
            else:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]
            
    return max(dp[-1])

아이디어 & 풀이

일반적인 DP 문제이다.
현재 탐색하고 있는 라인에서 양 끝에 존재하는 원소라면, 그 위 라인의 원소를 그대로 더한다.
만약, 양 끝이 아니라면 그 위 라인의 왼쪽, 오른쪽 원소를 비교해서 더 큰 값을 더한다.

---

사칙연산

코드 #1

def solution(arr):
    n = len(arr)
    _len = n // 2 + 1
    INF = int(1e9)
    num = [int (x) for x in arr[::2]]
    op = [x for x in arr[1::2]]
    
    max_dp = [[-INF] * _len for _ in range(_len)]
    min_dp = [[INF] * _len for _ in range(_len)]
    
    for i in range(_len):
        max_dp[i][i] = num[i]
        min_dp[i][i] = num[i]
    
    # 뒤에서 앞으로 탐색
    for i in range(_len - 2, -1, -1):
        for j in range(i + 1, _len):
            for k in range(i, j):
                if op[k] == '-':
                    max_dp[i][j] = max(max_dp[i][j], max_dp[i][k] - min_dp[k + 1][j])
                    min_dp[i][j] = min(min_dp[i][j], min_dp[i][k] - max_dp[k + 1][j])
                else:
                    max_dp[i][j] = max(max_dp[i][j], max_dp[i][k] + max_dp[k + 1][j])
                    min_dp[i][j] = min(min_dp[i][j], min_dp[i][k] + min_dp[k + 1][j])
    
    return max_dp[0][_len - 1]

코드 #2

# 앞에서 뒤로 탐색
    for step in range(_len):
        for i in range(_len - step):
            j = i + step
            
            if step == 0:
                continue
            else:
                for k in range(i, j):
                    if op[k] == '-':
                        max_dp[i][j] = max(max_dp[i][j], max_dp[i][k] - min_dp[k + 1][j])
                        min_dp[i][j] = min(min_dp[i][j], min_dp[i][k] - max_dp[k + 1][j])
                    else:
                        max_dp[i][j] = max(max_dp[i][j], max_dp[i][k] + max_dp[k + 1][j])
                        min_dp[i][j] = min(min_dp[i][j], min_dp[i][k] + min_dp[k + 1][j])

아이디어 & 풀이

---

등굣길

코드

MOD = 1000000007
def solution(m, n, puddles):
    dp = [[0] * (m + 1) for _ in range(n + 1)] # dp 리스트
    dp[1][1] = 1 # 집
    
    for i in range(1, n + 1):
        for j in range(1, m + 1):
        	# 웅덩이라면 연산 제외
            # puddles는 [열,행]으로 값을 가진다.
            if [j, i] in puddles: 
                continue
            
            # 조건에 맞게 연산후 나눈다.
            dp[i][j] += (dp[i][j - 1] + dp[i - 1][j]) % MOD            
    return dp[n][m]

아이디어 & 풀이

dp 리스트를 초기화하고, 초기 위치는 집이므로 dp[1][1] = 1로 초기화한다.
위치를 모두 탐색하면서,

• 현재 위치가 웅덩이라면, 연산을 하지 않는다.
• 현재 위치가 웅덩이가 아니라면, 문제의 조건에 맞게 연산을 수행한다.

---

도둑질

코드

아이디어 & 풀이

---