This is Mi

https://www.acmicpc.net/problem/14891   1. 풀이(n - 1)번째 결과를 바탕으로 가장 최소 비용을 만드는 n번째 선택을 하자.이전 결과를 담을 2차원 리스트가 필요하다. 행은 몇 번째 집인지를 의미하고, 열은 R(0), G(1), B(2) 중 어떤 색을 선택했는지에 대한 정보를 나타낸다.  위 그림은 백준의 첫 번째 입력 예제를 바탕으로 만들어진 2차원 리스트이다.예를 들어 1번 집을 초록색과 파란색 중 더 비용이 작은 색을 칠하고, 2번 집에 빨강(R)을 칠한다면 그 비용은 dp[1][0]에 담긴다. 이를 식으로 나타내면 dp[1][0] = min(dp[0][1], dp[0][2]) + COSTS[1][0]이다.그런데 사실 2번 집에 빨간색이 아니라, 초록색 혹은 파란..

https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 1. 풀이 DP 테이블을 활용하자 아래 9251번 문제와 현재 5582번 문제는 비슷하지만, 확연한 차이점이 하나 있다. 9251번은 공통 부분 문자열 사이에 다른 문자열이 존재해도 괜찮았지만, 현재 5582번은 반드시 공통 서브 문자열이 서로 붙어 있어야 한다. 서브 문자열 사이에 다른 문자가 들어오면 안 된다. [백준] 9251번 LCS 파이썬 풀이 https://www.acmicp..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 1. 풀이 가장 뒤의 문자부터 검사하자 맨 뒤 문자부터 서로 비교하면서 (1) 같으면 두 문자열에서 동시에 마지막 문자를 제거하고 (2) 다르면 문자열1의 마지막 문자만 제거하거나 문자열2의 마지막 문자만 제거하는 식으로 2가지 갈래로 나누어 가자. 더 이상 문자열을 비교할 수 없을 때는, 그 동안 동시에 제거된 문자 (C, E)가 바로 두 문자열의 L..

https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net 1. 접근 방식 작은 문제들을 모아 큰 문제를 해결하는 다이나믹 프로그래밍 기법이다 k원을 구성하는 최소 동전들의 개수는 (k - coin)원을 구성하는 최소 동전 + 1이다. 따라서 1원부터 k원까지 점진적으로 각 금액을 구성하는 최소 동전 개수를 구하면 문제를 해결할 수 있다. 인덱스 i원을 만드는 최소 동전 개수를 담은 1차원 dp 배열을 선언하자 최소 동전 ..

https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 1. 접근 방식 dfs로 접근하면 안 된다 시작점과 끝점이 명확한 그래프 문제처럼 보이지만, DFS로 풀면 시간 초과가 발생한다. bfs로도 접근하면 안 된다 (a - 1, b)에서 (a, b)를 방문하게 되는 경우와 (a, b - 4)에서 (a, b)를 방문하게 되는 경우는 서로 다르게 취급되어야 한다. 그러나 bfs에서 각 노드의 방문 여부를 나타내는 visited라는 배열은 (a ..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 1. 접근 방식 다이나믹 프로그래밍 문제임을 알아채자. 숫자 1, 2, 3의 합으로 어떤 숫자를 나타내는 방법을 구하는 문제이다. 아래 그림으로 숫자 4를 1, 2, 3의 합으로 나타내는 방법의 개수를 구하는 방법을 알아보자. 처음에 1, 2, 3을 각각 1, 2, 3의 합으로 나타낼 수 있는 방법의 개수를 초기화해 놓는다. 4는 (3 + 1), (2 + 2), (1 + 3)으로 나타낼 수 있는데, 이때 3을 만드는 방법, 2를 만드는 방법, 1을 만드는 방법의 개수를 알고 있다면, 그냥 그 방..

https://www.acmicpc.net/problem/2491 2491번: 수열 0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾 www.acmicpc.net 1. 접근 풀이 연속해서 커지는/작아지는 수열 개수를 저장할 increase / decrease 리스트 2개가 필요하다. 각 리스트에 연속해서 커지고 / 작아지고 있는 수열의 개수를 누적해서 저장한다. 예를 들어 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾아내는 과정은 이러하다. 입력 받은 수열의 첫 번째 숫자인 4는 일단 1개로 카운트한다. 두 번째 숫자 1은 4보다 작으므로..

https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 1. 접근 방식 다이나믹 프로그래밍과 그리디, 2가지 버전으로 접근했다. 다이나믹 프로그래밍 문제를 연습하고자 카테고리를 타고 들어온 문제였기 때문에 dp 테이블을 사용하는 다이나믹 프로그래밍 기법에 맞춰 풀이하고자 노력했다. 이후엔 그리디로도 문제를 해결해보았다. 이 문제는 dp 방식보다 그리디 방식이 더욱 빠르고 간단하다. 그리디로 작성한 코드는 3번에서 확인할 수 있다. 2원과 5원 동전만 거슬러 줄 수 있으므로, dp 테이블의 5번 인덱스까지 미리 초기화해두자. dp 리스트에 1원 ~ 5원을 받았을 때 거슬러..

1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 1. 문제 내용 2. 접근 방식 다이나믹 프로그래밍이다. 일반적인 재귀 함수로는 N이 조금만 커져도 시간 초과가 난다. 따라서 다이나믹 프로그래밍 방식으로 접근해야 한다. dp 리스트는 각 n의 0과 1의 개수가 담긴 2차원 리스트이다. 이 문제에서 실제 n = 4일 때의 피보나치 수를 구할 필요가 없다. 단지 n = 4일 때 0과 1이 몇 번 호출되는지만 궁금하기 때문이다. f(5)로 예를 들어보자. f(5)는 위와 같은 f() 함수들이 호출된다. f(2)는 0과 1을 각각 1개씩 가지고 있으므로, [1, 1]로 표현할 수 있다. f(3)은 f(2) 값에서..

2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 1. 문제 내용 2. 접근 방식 다이나믹 프로그래밍(DP) 피보나치를 구하는 가장 일반적인 재귀 함수 방식은 시간 복잡도가 O(2^n)이다. 이 문제에서 n은 90보다 작거나 같은 자연수이므로, 재귀 함수 방식으론 절대 풀 수가 없다. 따라서 작은 문제에서 큰 문제로 차근차근 답을 도출하는 다이나믹 프로그래밍의 상향식 방식을 따라 dp 테이블을 사용하여 피보나치 수를 구한다. 3. 정답 코드 n = int(input()) dp..