[AIVLE/알고리즘] 23. 04. 09. 알고리즘 스터디 - 다이나믹 프로그래밍(dp)

우리 반 알고리즘 스터디에 합류하게 되었다! 에이블 코딩 마스터스 이후로 또 긴장이 풀려서 알고리즘 공부를 꾸준히 하지 못했다. 첫 번째 코딩테스트도 잘 못봤고 공부의 필요성을 느끼던 차에 감사하게도 합류하게 되어 좋다. ㅎㅎ 동기부여도 되고, 잘하시는 분들께 배우며 성장해가고자 한다. 😎 !!

...... 라고 말했지만 이번 첫 주에 문제를 너무 못 풀었다.... 다이나믹 프로그래밍 개념은 이번에 스터디 준비하면서 처음 접했는데 도무지 접근법을 이해하기 힘들었다. 그래도 너무 감사하게도 스터디원 분들이 친절하게 코드 설명도 해주시고 질문에 대해 개념 설명도 해주셔서 dp에 대해 좀 더 이해할 수 있었다. 다음 주에는 나도 꼭!! 문제 많이 풀어가야지

---

개념

다이나믹 프로그래밍(dp)이란?

• 한 번 해결된 부분의 정답을 메모리에 기록하여, 한 번 계산한 답은 다시 계산하지 않도록 하는 문제 해결 기법
• i번째까지의 최적의 해를 가지는 점화식을 찾고 이를 코드로 구현하기

dp의 개념 자체는 이해 가능했다. 그러나 이를 문제 상황에 적용하기가 까다롭게 느껴졌고, i-1까지의 최적 값을 i시점에서 다시 사용한다는 것에 대한 개념이 낯설게 느껴졌다. 스터디 시간은 가까워지는데 백지에 끄적이는 내 자신에게 한심함을 느낌.........   

 

++ 현재 스터디는 주제에 맞는 문제 4개, 개인 문제 4개로 진행되기 때문에 모든 문제가 dp 문제는 아닐 수 있다.

 

현 상황 - 스터디 전 푼 문제 ( 0 / 8 ) 스터디 후 복습 완료 ( 3 / 8 )

1. 백준 2579. 계단 오르기

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

문제 설명

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

 

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

 

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

 

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

코드

# 2579

n = int(input())
array = []
dp = [0] * n

for i in range(n):
    a = int(input())
    array.append(a) # 각 계단의 점수를 저장
    
for i in range(n):
    if i == 0:
        dp[0] = array[0]
    elif i == 1:
        dp[1] = array[0] + array[1]
    elif i == 2:
        dp[2] = max(array[0]+array[2], array[1]+array[2])
    else:
        dp[i] = max(dp[i-3]+array[i-1]+array[i], dp[i-2]+array[i])

print(dp[n-1])

dp[2]는 모든 값을 더할 경우 연속된 세 개의 계단을 모두 밟아서는 안 된다는 조건에 위배된다. 따라서 0번 계단과 2번 계단을 더한 값과 1번 계단과 2번 계단을 더한 값 중 더 큰 값으로 지정한다. 이후 dp[i]는 연속 세 개의 계단을 밟지 않기 위해 두 가지 상황을 고려한다. 직전 계단을 밟는 경우와 그 전 계단을 밟는 경우이다. 이를 점화식으로 나타내면 다음과 같다.

따라서 해당 두 계산 값 중 더 큰 값을 택하면 계속 dp 값을 구할 수 있다. 두 번째 경우에서 i-3번째 계단은 이미 dp[i-2]에서 고려되었기 때문에 상관없다. 또한 array[i]를 무조건 더해주기 때문에 마지막 계단도 무조건 밟는다. 

 

2. 백준 11052. 카드 구매하기

https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.

PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다.

• 전설카드
• 레드카드
• 오렌지카드
• 퍼플카드
• 블루카드
• 청록카드
• 그린카드
• 그레이카드

카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.

민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것이라는 미신을 믿고 있다. 따라서, 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다.

예를 들어, 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최댓값은 10원이다. 2개 들어있는 카드팩을 2번 사면 된다.

P1 = 5, P2 = 2, P3 = 8, P4 = 10인 경우에는 카드가 1개 들어있는 카드팩을 4번 사면 20원이고, 이 경우가 민규가 지불해야 하는 금액의 최댓값이다.

마지막으로, P1 = 3, P2 = 5, P3 = 15, P4 = 16인 경우에는 3개 들어있는 카드팩과 1개 들어있는 카드팩을 구매해 18원을 지불하는 것이 최댓값이다.

카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 프로그램을 작성하시오. N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능하다. 즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다.

 

입력

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000)

둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

 

출력

첫째 줄에 민규가 카드 N개를 갖기 위해 지불해야 하는 금액의 최댓값을 출력한다.

코드

# 11052

n = int(input())
array = [0] + list(map(int, input().split()))
dp = [0]*(n+1)

for i in range(1, n+1):
    dp_list = [array[i]]
    
    # n개의 카드를 살 수 있는 경우 모두 추가
    for k in range(1, i//2+1):
        dp_list.append(dp[k]+dp[i-k])
  
    dp[i] = max(dp_list)

print(dp[n])

점화식 도출과정을 그림으로 표현하면 다음과 같다. dp의 개념이 낯설 때 이 문제에서 어려웠던 접근법은 카드 4개를 살 때 가능한 경우의 수는 총 5개인데 이걸 dp로 어떻게 표현할 수 있다는 거지? 였다. 4개의 카드를 사는 방법 중 1+1+1+1 과 2+1+1이 있을 때 이미 1+1이냐 2이냐의 문제는 이미 dp[2]에서 고려된 상황이었다. 고로 4개의 카드를 사는 방법에 대해 array[4], dp[3] + da[1], dp[2] + dp[2] 만 고려하면 된다. 따라서 고려해야 하는 값들을 dp_list에 저장하고 이 중 최댓값을 dp[i]에 저장했다. 조원분들은 한 줄 for문으로 간단히 작성하시기도 했는데 아직 그건 좀 어려워서 길게 작성했다. ㅎㅎ

 

3. 백준 1149. RGB 거리

https://www.acmicpc.net/problem/1149

1149번: RGB거리

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

코드

# 1149

n = int(input())
array = []

for i in range(n):
    a = list(map(int, input().split()))
    array.append(a)

# 각 상황에서 최솟값을 저장할 dp 생성
dp = [[0, 0, 0] for _ in range(n)] 
dp[0] = array[0]

for i in range(1, n):
    for k in range(3):
        if k == 0: # 현재가 red -> 이전 green, blue 각 dp의 최솟값에 더해줌
            dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + array[i][0]
        if k == 1: # 현재가 green -> 이전 red, blue 각 dp의 최솟값에 더해줌
            dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + array[i][1]
        if k == 2:  # 현재가 blue -> 이전 red, green 각 dp의 최솟값에 더해줌
            dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + array[i][2]

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

dp의 개념을 뭔가 더 이해할 수 있었던 문제였다. 이전에 문제를 풀 땐 현재 rgb 값의 최솟값만 고려하며 greedy 느낌으로 문제를 풀었다. 그러니 이전 값이 green이나 blue였는지를 어떻게 고려하는 거지? 하며 멘붕에 빠졌었다. 그러나 rgb 모든 상황에서의 최솟값을 비교하고 array와 똑같은 dp 배열을 만듦으로써 이를 해결할 수 있었다. 접근 방식이 이해가 되자 코드는 비교적 수월하게 작성할 수 있었다.

4. 백준 2502. 떡 먹는 호랑이

https://www.acmicpc.net/problem/2502

2502번: 떡 먹는 호랑이

문제

하루에 한 번 산을 넘어가는 떡 장사 할머니는 호랑이에게 떡을 주어야 산을 넘어갈 수 있는데, 욕심 많은 호랑이는 어제 받은 떡의 개수와 그저께 받은 떡의 개수를 더한 만큼의 떡을 받아야만 할머니를 무사히 보내 준다고 한다. 

예를 들어 첫째 날에 떡을 1개 주었고, 둘째 날에는 떡을 2개 주었다면 셋째 날에는 1+2=3개, 넷째 날에는 2+3=5개, 다섯째 날에는 3+5=8개, 여섯째 날에는 5+8=13개를 주어야만 무사히 산을 넘어갈 수 있다. 

우리는 산을 무사히 넘어온 할머니에게 오늘 호랑이에게 몇 개의 떡을 주었는지, 그리고 오늘이 호랑이를 만나 떡을 준지 며칠이 되었는지를 알아내었다. 할머니가 호랑이를 만나서 무사히 넘어온 D째 날에 준 떡의 개수가 K개임을 알 때, 여러분은 할머니가 호랑이를 처음 만난 날에 준 떡의 개수 A, 그리고 그 다음 날에 호랑이에게 준 떡의 개수 B를 계산하는 프로그램을 작성하시오. 이 문제에서는 항상 1 ≤ A ≤ B 이다.

예를 들어 여섯 번째 날에 산을 무사히 넘어온 할머니가 호랑이에게 준 떡이 모두 41개라면, 호랑이를 만난 첫 날에 준 떡의 수는 2개, 둘째 날에 준 떡의 수는 7개이다. 즉 셋째 날에는 9개, 넷째 날에는 16개, 다섯째 날에는 25개, 여섯째 날에는 41개이다. 따라서 A=2, B=7 이 된다. 단 어떤 경우에는 답이 되는 A, B가 하나 이상일 때도 있는데 이 경우에는 그 중 하나만 구해서 출력하면 된다.

 

입력

첫째 줄에는 할머니가 넘어온 날 D (3 ≤ D ≤ 30)와 그 날 호랑이에게 준 떡의 개수 K (10 ≤ K ≤ 100,000)가 하나의 빈칸을 사이에 두고 주어진다. 

 

출력

첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤ A ≤ B)가 존재한다. 

코드  (아직 구현 중)

# 2502

 

 

5. 체스

https://www.acmicpc.net/problem/1986

1986번: 체스

문제

n×m 크기의 체스 판과, 상대팀의 Queen, Knight, Pawn의 위치가 주어져 있을 때, 안전한 칸이 몇 칸인지 세는 프로그램을 작성하시오. (안전한 칸이란 말은 그 곳에 자신의 말이 있어도 잡힐 가능성이 없다는 것이다.)

참고로 Queen은 가로, 세로, 대각선으로 갈 수 있는 만큼 최대한 많이 이동을 할 수 있는데 만약 그 중간에 장애물이 있다면 이동을 할 수 없다. 그리고 Knight는 2×3 직사각형을 그렸을 때, 반대쪽 꼭짓점으로 이동을 할 수 있다. 아래 그림과 같은 8칸이 이에 해당한다.

이때 Knight는 중간에 장애물이 있더라도 이동을 할 수 있다. 그리고 Pawn은 상대팀의 말은 잡을 수 없다고 하자(즉, 장애물의 역할만 한다는 것이다).

예를 들어 다음과 같이 말이 배치가 되어 있다면 진하게 표시된 부분이 안전한 칸이 될 것이다. (K : Knight, Q : Queen, P : Pawn)

 

입력

첫째 줄에는 체스 판의 크기 n과 m이 주어진다. (1 ≤ n, m ≤ 1000) 그리고 둘째 줄에는 Queen의 개수와 그 개수만큼의 Queen의 위치가 입력된다. 그리고 마찬가지로 셋째 줄에는 Knight의 개수와 위치, 넷째 줄에는 Pawn의 개수와 위치가 입력된다. 즉 둘째 줄, 셋째 줄, 넷째 줄은  k, r1, c1, r2, c2, ..., rk, ck 이 빈 칸을 사이에 두고 주어진다는 것이다. 여기서 ri는 i번째 말의 행 위치, ci는 i번째 말의 열 위치를 의미한다. 한 칸에는 하나의 말만 놓인다고 가정한다. Knight, Queen, Pawn의 개수는 각각 100을 넘지 않는 음이 아닌 정수이다.

 

출력

첫째 줄에 n×m 체스판에 안전한 칸이 몇 칸인지 출력하시오.

 

코드 (아직 구현 중)

# 1986

 

6. 백준 25215. 타이핑

https://www.acmicpc.net/problem/25215

25215번: 타이핑

문제

민겸이는 영어 소문자와 대문자로 이루어진 문자열을 타이핑하기로 했다. 민겸이가 사용할 수 있는 버튼은 26개의 영어 알파벳 버튼과 마름모(◆) 버튼, 별(★) 버튼이다. 각 버튼은 아래와 같이 작동한다.

• 알파벳 버튼을 누르면 소문자 또는 대문자 중 하나가 입력된다. 이때, 마름모 버튼이 활성화되어있다면 대문자, 아니라면 소문자가 입력된다. 마름모 버튼은 처음에 비활성화되어있다.
• 마름모 버튼은 한번 누를 때마다 활성화 및 비활성화 여부가 바뀐다.
• 별 버튼을 누르면 마지막으로 입력한 알파벳의 대소문자 여부가 바뀐다. 예를 들어 대문자가 마지막으로 입력되었을 경우 소문자로 바뀌고, 소문자가 마지막으로 입력되었을 경우 대문자로 바뀐다. 만약 마지막으로 입력한 알파벳이 없다면 작동하지 않는다.

민겸이는 사용할 수 있는 28개의 버튼을 이용해 어떤 문자열을 입력하려고 한다. 이때, 가능한 한 적은 횟수만큼 버튼을 누르고 싶다. 민겸이가 해당 문자열을 입력하기 위해 버튼을 최소 몇 번 눌러야 하는지 알려주자.

 

입력

입력은 한 줄로 주어진다.

첫 번째 줄에 민겸이가 타이핑할 문자열이 주어진다.

 

출력

민겸이가 해당 문자열을 입력하기 위해 버튼을 최소 몇 번 눌러야 하는지 출력한다.

코드 (아직 구현 중)

# 25215

 

7. 백준 1679. 숫자놀이

https://www.acmicpc.net/problem/1679

1679번: 숫자놀이

문제

홀순이(holsoon)와 짝순이(jjaksoon) 둘이서 숫자 게임을 한다. 예를 들어, 정수 1과 3이 주어지고, 이 둘을 통틀어 5번까지 마음대로 사용하여 그 합을 구하여 1,2,3,…을 만드는 놀이다. 이 경우 먼저 홀순이가 1 하나만을 사용하여 1을 만든다. 짝순이는 1+1로 1을 두 번 사용하여 2를 만들고, 다시 홀순이는 3을 만들어야하는데 1+1+1로 1을 세 번 사용하거나 3을 한 번 사용하여 3을 만든다. 짝순이는 1+1+1+1, 1+3으로 4를 만든다. 서로 번갈아서 상대방의 수보다 1이 큰 수를 만들어야 한다. 단, 1과 3을 통틀어 최대 5번 사용한다. 이런 식으로 진행하면 13까지는 만들 수 있지만 14를 만들지 못하게 되므로 짝순이가 졌다. 

숫자 게임에서 사용하는 정수 N개와 최대 사용 횟수 K가 주어질 때, 누가 어느 수에서 이기는지를 판별하는 프로그램을 작성해보자. 사용하는 정수에는 반드시 1이 포함된다. 그렇지 않으면 홀순이가 1을 만들지 못하므로 무조건 지게 된다. 1이 꼭 있으니 상대방이 만든 방법에 1만 한 번 더 쓰면 된다고 생각하기 쉽지만, 최대 사용 횟수가 정해져 있으므로, 이 방법이 수가 커지는 경우에는 잘 되지 않는다. 위에서 13을 홀순이가 만들었지만 짝순이는 최대 사용 횟수 때문에 14를 만들지 못하고 진다.

 

입력

첫째 줄에 숫자 게임에서 사용하는 정수의 수 N이, 둘째 줄에는 사용하는 정수가 크기 순으로 주어진다. 셋째 줄에는 최대 사용 횟수 K가 주어진다.

 

출력

첫째 줄에 누가 몇 번째 수에서 이겼는지를 출력한다. 예제에서는 짝순이가 14를 못 만들어서, 홀순이가 14에서 이겼다.

코드 (아직 구현 중)

# 1679

 

8. 백준 11000. 강의실 배정

https://www.acmicpc.net/problem/11000

11000번: 강의실 배정

문제

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

 

입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 10^9)

 

출력

강의실의 개수를 출력하라.

코드 (아직 구현 중)

# 11000

 

---

 

  dp도 낯선 사람으로서 아직 모든 문제를 마스터하진 못했지만 스터디를 회고하고자 블로그를 먼저 작성했다. ( 앞으로 꾸준히 복습하면서 남은 코드도 작성해나가겠습니다! )

 

오늘의 짤은 이걸로...