대기업 코딩테스트 준비 6 : 다이나믹 프로그래밍

다이나믹 프로그래밍

중복된 연산을 줄이자
- 메모리 공간 활용을 통해 연산 속도 비약적 향상
- 탑다운
  - 큰 문제를 해결하기 위해 작은 문제 호출
  - 재귀
  - 빅뱅
- 바텀 업
  - 작은 문제부터 점진적 답 도출
  - 반복문
- 메모이제이션
다이나믹
- 프로그램 실행 도중에
- 여기서는 이런 의미 아님
- 점화식
  - 인접항 간 관계식
  - 수열을 리스트로 표현
조건
- 큰 문제를 작은 문제를 나눌 수 있음
- 작은 문제에서 구한 정답은 큰 문제에서도 동일
- 메모이제이션 === 캐싱

practice : 1로 만들기

# 정수 X를 입력 받기
x = int(input())

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 1000001

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
for i in range(2, x + 1):
    # 현재의 수에서 1을 빼는 경우
    d[i] = d[i - 1] + 1
    # 현재의 수가 2로 나누어 떨어지는 경우
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)
    # 현재의 수가 3으로 나누어 떨어지는 경우
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)
    # 현재의 수가 5로 나누어 떨어지는 경우
    if i % 5 == 0:
        d[i] = min(d[i], d[i // 5] + 1)

print(d[x])

practice : 식량 창고

ai = max(ai-1, ai-2+ki)

# 정수 N을 입력 받기
n = int(input())
# 모든 식량 정보 입력 받기
array = list(map(int, input().split()))

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업)
d[0] = array[0]
d[1] = max(array[0], array[1]) 
for i in range(2, n):
    d[i] = max(d[i - 1], d[i - 2] + array[i]) # 안털거나 (그 전꺼 그대로.) 털거나 (전 곳을 못터니 그 직전꺼)

# 계산된 결과 출력
print(d[n - 1])

practice : 바닥 공사

# 정수 N을 입력 받기
n = int(input())

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 1001

# 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업)
d[1] = 1
d[2] = 3
for i in range(3, n + 1):
    d[i] = (d[i - 1] + 2 * d[i - 2]) % 796796

# 계산된 결과 출력
print(d[n])

practice : 효율적인 화폐 구성

# 정수 N, M을 입력 받기
n, m = map(int, input().split())

# N개의 화폐 단위 정보를 입력 받기
array = []
for i in range(n):
    array.append(int(input()))

# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [10001] * (m + 1)

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
d[0] = 0
for i in range(n): # array는 화폐 단위. i는 화폐 단위 인덱스
    for j in range(array[i], m + 1): # m은 만들 금액
        if d[j - array[i]] != 10001: # (i - k)원을 만드는 방법이 존재하는 경우
            d[j] = min(d[j], d[j - array[i]] + 1) # 만약 K가 5면 arr[13] = arr[8]+1 or 이전 동전 결과

# 계산된 결과 출력
if d[m] == 10001: # 최종적으로 M원을 만드는 방법이 없는 경우
    print(-1)
else:
    print(d[m])

1. 금광

첫번째 열부터 출발
금광의 모든 위치에 대하여 저장
- 1. 왼쪽에서 오는 경우
  2. 왼쪽 아래에서 오는 경우
  3. 왼쪽 위에서 오는 경우

    # 테스트 케이스(Test Case) 입력
    for tc in range(int(input())):
        # 금광 정보 입력
        n, m = map(int, input().split())
        array = list(map(int, input().split()))

    # 다이나믹 프로그래밍을 위한 2차원 DP 테이블 초기화
    dp = []
    index = 0
    for i in range(n):
        dp.append(array[index:index + m])
        index += m

    # 다이나믹 프로그래밍 진행
    for j in range(1, m): # column
        for i in range(n): # row
            # 왼쪽 위에서 오는 경우
            if i == 0:
                left_up = 0
            else:
                left_up = dp[i - 1][j - 1]
            # 왼쪽 아래에서 오는 경우
            if i == n - 1:
                left_down = 0
            else:
                left_down = dp[i + 1][j - 1]
            # 왼쪽에서 오는 경우
            left = dp[i][j - 1]
            dp[i][j] = dp[i][j] + max(left_up, left_down, left)

    result = 0
    for i in range(n):
        result = max(result, dp[i][m - 1])

    print(result)

2. 정수 삼각형

대각선 왼쪽 or 대각선 오른쪽 위에 있는 것
- 왼쪽 위 혹은 바로 위
금광과 유사함

n = int(input())
dp = [] # 다이나믹 프로그래밍을 위한 DP 테이블 초기화

for _ in range(n):
    dp.append(list(map(int, input().split())))

# 다이나믹 프로그래밍으로 2번째 줄부터 내려가면서 확인
for i in range(1, n): # row
    for j in range(i + 1): # col
        # 왼쪽 위에서 내려오는 경우 \
        if j == 0:
            up_left = 0
        else:
            up_left = dp[i - 1][j - 1]
        # 바로 위에서 내려오는 경우  /
        if j == i:
            up = 0
        else:
            up = dp[i - 1][j]
        # 최대 합을 저장
        dp[i][j] = dp[i][j] + max(up_left, up)

print(max(dp[n - 1]))

3.퇴사

뒤쪽 날짜부터 거꾸로
dp i 번째 날부터 마지막 날까지 낼 수 있는 최대 이익
dp[i] = max(p[i]+dp[t[i]+i],max_value)
- max_value = 뒤에서부터 계산할 때 현재까지의 최대 상담 금액

n = int(input()) # 전체 상담 개수
t = [] # 각 상담을 완료하는데 걸리는 기간
p = [] # 각 상담을 완료했을 때 받을 수 있는 금액
dp = [0] * (n + 1) # 다이나믹 프로그래밍을 위한 1차원 DP 테이블 초기화
max_value = 0

for _ in range(n):
    x, y = map(int, input().split())
    t.append(x)
    p.append(y)

# 리스트를 뒤에서부터 거꾸로 확인
for i in range(n - 1, -1, -1):
    time = t[i] + i
    # 상담이 기간 안에 끝나는 경우
    if time <= n:
        # 점화식에 맞게, 현재까지의 최고 이익 계산
        dp[i] = max(p[i] + dp[time], max_value)
        max_value = dp[i]
    # 상담이 기간을 벗어나는 경우
    else:
        dp[i] = max_value

print(max_value)

4. 병사 배치하기

가장 긴 증가하는 부분 수열
- 이 문제는 가장 긴 감소하는 부분 수열
- array를 뒤집은 뒤 해당 알고리즘 적용
Longest Increasing Subsequence

n = int(input())
array = list(map(int, input().split()))
# 순서를 뒤집어 '최장 증가 부분 수열' 문제로 변환
array.reverse()

# 다이나믹 프로그래밍을 위한 1차원 DP 테이블 초기화
dp = [1] * n

# 가장 긴 증가하는 부분 수열(LIS) 알고리즘 수행
for i in range(1, n):
    for j in range(0, i):
        if array[j] < array[i]:
            dp[i] = max(dp[i], dp[j] + 1)

# 열외해야 하는 병사의 최소 수를 출력
print(n - max(dp))

5. 못생긴 수

2,3,5 만을 소인수(Prime Factor)로 가지는 수
- 2,3,5 만을 약수로 가지는 합성수
못생긴 수에 2 OR 3 OR 5를 곱한 수도 못생긴 수다.
못생긴 수들을 작은 수부터 차례대로 확인하면서, 각 못생긴 수에 대해 2,3,5의 배수를 고려한다.

n = int(input())

ugly = [0] * n # 못생긴 수를 담기 위한 테이블 (1차원 DP 테이블)
ugly[0] = 1 # 첫 번째 못생긴 수는 1

# 2배, 3배, 5배를 위한 인덱스
i2 = i3 = i5 = 0
# 처음에 곱셈 값을 초기화
next2, next3, next5 = 2, 3, 5

# 1부터 n까지의 못생긴 수들을 찾기
for l in range(1, n):
    # 가능한 곱셈 결과 중에서 가장 작은 수를 선택
    ugly[l] = min(next2, next3, next5)
    # 인덱스에 따라서 곱셈 결과를 증가
    if ugly[l] == next2:
        i2 += 1
        next2 = ugly[i2] * 2
    if ugly[l] == next3:
        i3 += 1
        next3 = ugly[i3] * 3
    if ugly[l] == next5:
        i5 += 1
        next5 = ugly[i5] * 5

# n번째 못생긴 수를 출력
print(ugly[n - 1])

6. 편집 거리

삽입, 삭제 ,교체
- 행과 열에 해당하는 문자가 서로 같다면, 왼쪽 위에 해당하는 수를 그대로 대입
- 행과 열에 해당하는 문자가 서로 다르다면, 왼쪽(삽입), 위쪽(삭제), 왼쪽 위(교체)에 해당하는 수 중 가장 작은 수에 1을 더해 대입
- 왼쪽열에 있는 문자열을 위쪽행에 있는 스트링으로 바꾸는 비용

SUN > SAT 비용 2

+# 최소 편집 거리(Edit Distance) 계산을 위한 다이나믹 프로그래밍
def edit_dist(str1, str2):
    n = len(str1)
    m = len(str2)

    # 다이나믹 프로그래밍을 위한 2차원 DP 테이블 초기화
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    # DP 테이블 초기 설정
    for i in range(1, n + 1):
        dp[i][0] = i
    for j in range(1, m + 1):
        dp[0][j] = j

    # 최소 편집 거리 계산
    for i in range(1, n + 1): # 행
        for j in range(1, m + 1): # 열
            # 문자가 같다면, 왼쪽 위에 해당하는 수를 그대로 대입
            if str1[i - 1] == str2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            # 문자가 다르다면, 세 가지 경우 중에서 최솟값 찾기
            else: # 삽입(왼쪽), 삭제(위쪽), 교체(왼쪽 위) 중에서 최소 비용을 찾아 대입
                dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])

    return dp[n][m]

# 두 문자열을 입력 받기
str1 = input()
str2 = input()

# 최소 편집 거리 출력
print(edit_dist(str1, str2))

'ETC' 카테고리의 다른 글

대기업 코딩테스트 8 : 그래프 이론 (0)	2021.02.14
대기업 코딩테스트 준비 7 : 최단 경로 (0)	2021.02.14
대기업 코딩테스트 준비 5 : 이진 탐색 (0)	2021.02.14
대기업 코딩테스트 준비 5 : 정렬 (0)	2021.02.14
대기업 코딩테스트 준비 3 : 구현 (0)	2021.02.13

Development & Investing

대기업 코딩테스트 준비 6 : 다이나믹 프로그래밍

다이나믹 프로그래밍

practice : 1로 만들기

practice : 식량 창고

practice : 바닥 공사

practice : 효율적인 화폐 구성

1. 금광

2. 정수 삼각형

3.퇴사

4. 병사 배치하기

5. 못생긴 수

6. 편집 거리

'ETC' 카테고리의 다른 글

티스토리툴바

대기업 코딩테스트 준비 6 : 다이나믹 프로그래밍

다이나믹 프로그래밍

practice : 1로 만들기

practice : 식량 창고

practice : 바닥 공사

practice : 효율적인 화폐 구성

1. 금광

2. 정수 삼각형

3.퇴사

4. 병사 배치하기

5. 못생긴 수

6. 편집 거리

'ETC' 카테고리의 다른 글

'ETC' Related Articles

티스토리툴바