CodeDrive

문제:

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K무게까지의 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력:

첫 줄에 물품의 수 N(1<=N<=100)과 준서가 버틸 수 있는 무게 K(1<=K<=100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1<=W<=100,000)와 해당 물건의 가치 V(0<=V<=1,000)가 주어진다.

입력으로 주어진느 모든 수는 정수이다.

출력:

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

풀이방법:

knapsack의 가장 기본적인 문제다. dp를 사용해서 간단하게 풀었다.

문제링크:

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

문제:

반도체를 설계할 때 n개의 포트를 다른 n개의 포트와 연결해야 할 때가 있다.

예를 들어 왼쪽 그림이 n개의 포트와 다른 n개의 포트를 어떻게 연결해야 하는지를 나타낸다. 하지만 이와 같이 연결을 할 경우에는 연결선이 서로 꼬이기 때문에 이와 같이 연결할 수 없다. n개의 포트가 다른 n개의 포트와 어떻게 연결되어야 하는지가 주어졌을 때, 연결선이 서로 꼬이지(겹치지, 교차하지) 않도록 하면서 최대 몇 개까지 연결할 수 있는지를 알아내는 프로그램을 작성하시오.

입력:

첫째 줄에 정수 n(1<=n<=40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, ... , n번 포트와 연결되어야 하는 포트 번호가 주어진다. 이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자.

출력:

첫째 줄에 최대 연결 개수를 출력한다.

풀이방법:

복잡해 보이지만 LIS 문제라고 생각하면 쉽게 풀 수 있다. LIS를 푸는 방법에는 여러 가지가 있지만 가장 대표적인 방법인 DP를 사용해서 문제를 풀어보았다.

DP로 푸는 방법은 O(N^2)의 시간 복잡도이기 때문에 시간이 오래 걸리게 된다. 따라서 O(NlogN)으로 푸는 방법이 있다해서 다음을 참고 하였다.

https://dyngina.tistory.com/16

여기서 O(NlogN)이 두 개 있었는데 lower_bound는 python의 bisect를 쓰면 될 것 같다. 이번에는 인덱스 트리를 사용해서 문제를 풀어 보았다. 인덱스 트리를 만들기 위한 과정에서 시간이 많이 소요 되는 것 같아서 이 역시도 pypy3로 통과했다. 아마도 bisect를 사용하면 python으로도 통과할 수 있을 것 같다.

문제링크:

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

문제:

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

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10+20+25+20 = 75점이 된다.

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

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.

2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.

3. 마지막 도착 계단은 반드시 밟아야 한다.

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

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

입력:

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

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

출력:

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

풀이방법:

조건3인 마지막 계단을 무조건 밟아야 하기 때문에 경우의 수는 다음 2개만 존재하게 된다.

1. 마지막칸의 전칸을 밟고 마지막 칸으로 이동하는 경우

2. 마지막의 전전칸을 밟고 마지막칸을 밟는 경우

그런데 1번의 경우에는 조건2가 있기 때문에 이를 고려해 줘야 한다. 

이 것을 코드로 구현하게 되면 다음과 같다. 

1번 -> dp[n-3] + stair[n-1] + stair[n]

2번 -> dp[n-2] + stair[n]

따라서 이 둘중 max 값을 골라서 진행하면 된다.

이를 위해서 dp[0], dp[1], dp[2]를 초기화 해줬는데, 만약 계단의 개수가 이보다 적게 되면 런타임에러가 발생하게 된다.

따라서 stair를 공백의 빈 배열을 만들어도 되긴 하는데, 단순히 조건문을 추가해서 답을 구하도록 만들었다.

문제링크:

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

Youtube에 있는 David Silver의 Reinforcement Learning 강의를 보고 작성하였습니다.

3. Planning by Dynamic Programming

• Model Free : environment에 대한 정보를 가지고 있지 않을 경우
• Model Based : environment에 대한 모델이 있는 경우
  • 이러한 경우에 대해서 Planning, Dynamic Programming을 사용한다.

Introduction

• What is Dynamic Programming?

  알고리즘 문제 기법에서 사용하는 DP, 동적 계획법과 같은 뜻을 가지고 있다. 복잡한 문제에 사용하는 방법으로써 문제를 여러 subproblem으로 쪼갠 뒤에 이 문제를 해결하고 합쳐가면서 풀어가는 방식이다.

  • 다음과 같이 두 가지 특성을 가지는 문제에 대해서 DP를 사용하는 것이 일반적이다.
    • Optimal substructure
      • Optimal한 해는 subproblems들로 분해될 수 있다는 것이다.
    • Overlapping subproblems
      • Subproblem 들이 많이 사용되어서 이를 저장해두었다가 사용할 수 있다.
  • MDP는 위 두 가지 속성을 가지고 있으므로 DP를 사용할 수 있다.
    • Bellman equation은 재귀적으로 분해가 가능하고, value function은 해를 저장하고 재사용할 수 있도록 한다.

• Planning by Dynamic Programming

  DP는 MDP의 모든 것을 알고 있다고 가정한다. 즉 Planning 문제를 해결하는 것이다.

  DP는 크게 두 가지 방법으로 나뉘게 된다.

  • Prediction
    • value function을 학습하는 것
    • MDP, policy가 있을 때 그 policy를 따를 경우의 value function이다.
    • policy evaluation 문제
  • Control
    • optimal 한 policy를 찾는 문제
    • MDP만 있고 optimal 한 policy를 찾아야 한다.
    • policy Iteration, value Iteration

Policy Evalutation

주어진 policy를 평가하는 문제, 이 policy를 따라 간다면 return을 얼마 받는가. 즉 value function을 찾는 문제

초기 value 값을 랜덤하게 초기화 한 후 Bellman Equation을 이용해서 다음 상태 s'를 이용해서 각각의 상태 s의 value 값을 반복적으로 업데이트 한다. 이 때 synchronous backup을 사용한다.

Example

위와 같이 계속해서 반복하다보면 정책이 수렴하는 것을 알 수 있다.

Policy Iteration

위와 같이 반복적인 업데이트를 통해서 모든 상태 s에 대해 value 값을 구할 수 있다.(Evaluate) value 값이 최대가 되는 방향으로 greedy하게 행동하면 초기에 만들었던 Random한 Policy를 개선된 Policy로 만들 수 있다.(Improve) 위와 같은 예시에서는 금방 최적의 Policy로 찾아가는 것을 알 수 있다.

따라서 일반적인 경우에는 Policy를 evaluation해서 value들을 구하고, 그 value들을 바탕으로 Policy를 improvement하는 방향으로 발전시키면 된다.

그런데 과연 greedy 하게 정책을 개선시키는 것이 성능을 항상 좋게 만들까?

다음과 같은 이유들로 항상 그렇다고 하며, 수렴을 하는 포인트는 optimal 하다고 한다.

• Modified Policy Iteration

  하지만 꼭 수렴할 때까지 계속해서 반복해서 진행해야 하는가? 에 대한 의문을 가질 수 있다. 실제로 무한히 반복해서 수렴할 때까지 진행을 하지 않고, k번을 반복해서 그 점을 사용해도 충분히 합리적으로 사용할 수 있다고 한다.

Value Iteration

Value Iteration은 Policy Iteration과는 다르게 Bellman Optimal Equation을 이용하는 것이다.

• Deterministic Value Iteration
  • subproblem의 solution을 알면 Bellman Optimal Equation을 이용해서 s에서의 solution을 알 수 있다.
  • 이러한 반복을 계속해서 한다.
• 아래는 위의 Grid world의 Value Iteration을 적용한 것이다.

• 반복해서 진행하면 세번째 iteration에서 converge 하는 것을 알 수 있다.

Summary of DP Algorithms

문제:

카드게임이 있다. 게임에 사용하는 각 카드에는 양의 정수 하나가 적혀있고 같은 숫자가 적힌 카드는 여러 장 있을 수 있다. 게임방법은 우선 짝수개의 카드를 무작위로 섞은 뒤 같은 개수의 두 더미로 나누어 하나는 왼쪽에 다른 하나는 오른쪽에 둔다.

각 더미의 제일 위에 있는 카드끼리 서로 비교하며 게임을 한다. 게임 규칙은 다음과 같다. 지금부터 왼쪽 더미의 제일 위 카드를 왼쪽 카드로, 오른쪽 더미의 제일 위 카드를 오른쪽 카드로 부르겠다.

1. 언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다.

2. 오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에는 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다.

3. (1)과 (2)의 규칙에 따라 게임을 진행하다가 어느 쪽 더미든 남은 카드가 없다면 게임이 끝나며 그때까지 얻은 점수의 합이 최종 점수가 된다.

왼쪽 더미의 카드에 적힌 정수가 담긴 배열 left와 오른쪽 더미의 카드에 적힌 정수가 담긴 배열 right가 매개변수로 주어질 때, 얻을 수 있는 최종 점수의 최대값을 return 하도록 solution 함수를 작성하시오.

풀이방법:

동적 계획법을 사용해서 푸는 문제이다. 오른쪽을 버릴 때에만 점수를 얻을 수 있으므로, 오른쪽을 많이 버릴 수 있으면 좋다. 그래서 우선 오른쪽을 먼저 버릴 수 있는지 확인을 하고, 왼쪽과 둘 다 버리는 경우를 생각해서 계산한다.

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/42896

문제:

서울에서 경산까지 여행을 하면서 모금 활동을 하려 합니다. 여행은 서울에서 출발해 다른 도시를 정해진 순서대로 딱 한 번 방문한 후 경산으로 도착할 예정입니다. 도시를 이동할 때에는 도보 혹은 자전거를 이용합니다. 이때 도보 이동에 걸리는 시간, 도보 이동 시 얻을 모금액, 자전거 이동에 걸리는 시간, 자전거 이동 시 얻을 모금액이 정해져 있습니다. K시간 이내로 여행할 때 모을 수 있는 최대 모금액을 알아보려 합니다

예를 들어 여행 루트가 다음과 같고 K=1,650 일 때,

1, 2번 구간은 도보로, 3번 구간은 자전거로 이동해 모금액을 660으로 하는 것이 가장 좋은 방법입니다. 이때, 1,600시간이 소요됩니다.

solution 함수의 매개변수로 각 도시를 이동할 때 이동 수단별로 걸리는 시간과 모금액을 담은 2차원 배열 travel과 제한시간 K가 주어집니다. 제한시간 안에 서울에서 경산까지 여행을 하며 모을 수 있는 최대 모금액을 return 하도록 solution 함수를 작성하세요.

풀이방법:

동적계획법을 사용해서 풀어야 하는 문제이다. 0번째 인덱스에는 도보로 걸리는 시간, 2번째 인덱스에는 자전거 이동시 걸리는 시간이 담겨 있으며. 1번째, 3번째 인덱스에는 각각 금액이 담겨져 있다. 따라서 0,2번째로 K시간이 넘어가지 않는 선에서 1,3을 더 했을 때 최대가 되는 값을 찾으면 된다.

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/42899

문제:

n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다.(-_-)

이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 둘 다 소중한 생명이지만 판다가 최대한 오래 살 수 있는지 고민에 빠져 잇따. 우리의 임무는 이 사육사를 도와주는 것이다. n*n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 오래 살려면 어떤 경로를 통하여 움직여야 하는지 구하여라.

입력:

첫째 줄에 대나무 숲의 크기 n(1<=n<=500)이 주어진다. 그리고 둘째 줄부터 n+1번째 줄까지 대나무 숲의 정보가 주어진다. 대나무 숲의 정보는 공백을 사이로 두고 각 지역의 대나무의 양이 정수 값으로 주어진다. 대나무의 양은 1,000,000보다 작거나 같은 자연수이다.

출력:

첫째 줄에는 판다가 최대한 살 수 있는 일수(K)를 출력한다.

풀이방법:

 기본적으로는 dfs를 사용해서 판다의 이동 경로를 알아야 하지만 문제에서 원하는 것은 판다가 최대한 살 수 있는 일수, 즉 최대로 이동 가능한 거리의 길이를 원하고 있다. 작은 크기의 경우에는 시작점을 달리 해서 최대 일수를 찾을 수 있지만 500 x 500의 경우에는 이 것을 다 탐색하기에는 많은 시간이 걸릴 것이다.

 따라서 이를 해결하기 위해서 다이나믹 프로그래밍에서 메모리제이션을 사용한다. 한 점에서 출발을 해서 움직이다가 이미 이전에 다른 곳에서 움직였던 기록이 남아있고 그것을 기록해뒀다면 더 이상 그 길로 이동할 필요없이 그 값을 참조해서 다시 돌아오면 된다. 따라서 dfs로 이동을 하지만 이전에 이 길을 지나간 기록이 있다면 그 값을 가져오고, 그렇지 않다면 더 들어가면서 값을 기록하도록 한다.

 또한 재귀적으로 함수를 구현했기 때문에 깊은 재귀로 인한 에러를 방지하기 위해서 sys.setrecursionlimit를 사용한다.

문제링크:

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

문제:

정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수 있다. 예를 들어 앞에서부터 순서대로 크기가(1,5,2,3,7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자를 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를 넣을 수 있는 방법을 여러 가지가 있을 수 있다. 앞의 예에서 차례대로 크기가 1, 2, 3, 7인 상자를 선택하면 총 4개의 상자가 한 개의 상자에 들어가게 된다.

상자의 크기가 주어질 때, 한 번에 넣을 수 있는 최대의 상자 개수를 출력하는 프로그램을 작성하시오.

입력:

파일의 첫 번째 줄은 상자의 개수 n(1<=n<=1000)을 나타낸다. 두 번째 줄에는 각 상자의 크기가 순서대로 주어진다. 상자의 크기는 1,000을 넘지 않는 자연수이다.

출력:

첫쨰 줄에 한 줄에 넣을 수 있는 최대의 상자 개수를 출력한다.

풀이방법:

앞에 있는 작은 상자를 뒤에 있는 큰 상자에 넣을 수 있으므로 이는 다이나믹프로그래밍을 사용한 LIS 문제와 같다.

LIS에서 lis[i]는 i번째 수열까지 한 번에 넣을 수 있는 최대의 상자 개수이며, i+1을 추가했을 때, boxes[1]~boxes[i]까지 boxes[i+1]보다 작은 값이 있는지 파악하고, 그 수에 해당하는 lis[k] 값들 중에 최댓값에 1을 더해주는 방식으로 진행한다. 그러고 전체 lis에서 최댓값을 출력해주면 된다.

문제링크:

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

문제:

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우) 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력:

첫째 줄에 두 정수 N(1<=N<=200),K(1<=K<=200)가 주어진다.

출력:

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

풀이방법:

동적계획법을 사용해서 이 문제를 풀었다. 점화식은 간단하다. K개의 합이 N이 되었을 때, 맨 마지막 수( l )를 빼면 남은 수는 K-1개로 N-l 이 남는 다는 것이다. 그래서 dp 테이블을 다음과 같이 구성할 수 있다.

dp[ i ][ j ] 는 i개의 수를 가지고 합이 j가 되는 경우를 뜻한다. 따라서 처음에는 1로 초기화되며, 한 층이 지날때마다 경우의 수가 더해져 우리가 원하는 dp[k][n]을 구할 수 있다.

문제링크:

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

문제:

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리는 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N<=M)

재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

입력:

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N,M(0<N<=M<30)이 주어진다.

출력:

각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력한다.

풀이방법:

이 문제는 다이나믹 프로그래밍을 활용해서 풀 수 있는 문제이다. 

왼쪽에 3개의 사이트가 있고, 오른쪽에 5개의 사이트가 있다고 가정하자. 그럼 왼쪽의 3개와 오른쪽의 5개를 이어야 하는 문제가 된다. 하지만 왼쪽의 제일 위 점과 오른쪽의 제일 위 점에 다리를 건설했다고 하자.

이제는 아래 남은 점들은 왼쪽의 2개의 점, 오른쪽의 4개의 점을 이어야 하는 문제가 된다. 이 단계에서 한 번 더 진행하면 이제 왼쪽에는 한 개만 남고 오른쪽에는 3개, 2개 ... 가 남게 된다. 왼쪽이 1개가 되면 오른쪽에 남은 개수가 이을 수 있는 경우의 수가 되므로 이를 활용해서 점화식을 만들 수 있게 된다.

dp[i][j] = d[i-1][k-1]+d[i-1][k-2]+ ... + d[i-1][i-1]

따라서 이를 반복문으로 구현하면 다음과 같게 된다. 

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