DP

https://www.acmicpc.net/problem/16500 머리말 완전 탐색인 줄 알고 왜 시간 초과가 나지 쩔쩔 맺던.. (테스트케이스 완전 불친절하다 😇) 이 문제는 dp 문제이다. 가만 생각해보면 중복 연산이 많으니 메모이제이션을 당연히 해야 한다. 처음 참고한 블로그도 좋은 풀이법이지만, 다른 분(cozyyg)의 풀이가 더 직관적이어서 그 풀이로 다시 공부하였다. 접근 방법 dp 배열에는 해당 인덱스까지 A에 포함된 문자열로 표현할 수 있는지 여부를 0, 1로 저장한다. 초기값 dp[0]은 1(True)로 두고, 우리의 목표는 dp[len(s)]값이 무엇인지 찾는 것이다. 계산 편의를 위해 +1 위치에 결괏값을 저장한다. 추가 테스트 케이스 1 [input] aaaaaaaaaa 2 aaa..

https://acmicpc.net/problem/12865 머리말 0/1 Knapsack 문제 DP로 유명한 문제이자 NP-hard 문제로 유명한 문제.. 작년 알고리즘 수업시간 때 배웠던 부분이 기억이 잘 나지 않아 첨부하였다. 수업 노트 코드 n, k = map(int, input().split()) weights = [-1] values = [-1] for i in range(n): w, v = map(int, input().split()) weights.append(w) values.append(v) dp = [[0] * (k + 1) for _ in range(n + 1)] for i in range(1, n + 1): for w in range(1, k + 1): if weights[i]

https://www.acmicpc.net/problem/1162 머리말 오랜만에 9시에 일어나서 백준 문제를 풀어봤다. 일찍 일어난거 맞지..? 어떤 문제를 풀지 고민하다가 최근 수업시간에 다루었던 다익스트라 문제를 골랐다. 1시간 30분 고민해서 풀었다가 6%에서 바로 틀렸다. 허허 아직 부족하다. 나의 접근 방법 다익스트라 문제라는 것만 생각하고 어떻게 문제에 다익스트라를 녹여낼까 고민했던 것 같다. 모든 가중치를 priority queue에 넣고 크기가 큰 순으로 weight를 0으로 집어 넣고 다익스트라를 적용시켰다. 하지만, 조금만 생각해보면 당연히 잘못된 풀이법이다. weight가 큰 것을 포장 도로로 만들 필요가 없기 때문이다. 또한 'k번 이하'라는 조건에 주의를 기울여야 했을 것이다. ..

문제 링크 1. 영상제작 외주를 받아서 잠시 공부를 하지 못했다. 오랜만에 문제를 풀었는데, 문제를 잘못 골랐는지 엄청 힘들었다. 나름 규칙을 찾아 점화식을 세웠는데, 틀렸다. 해설을 찾아 보았는데, 자세한 해설을 적어 놓은 사람을 찾기 힘들었고 적었더라도 이해가 되지 않았다. 풀이 이해하는데만 1시간 넘게 걸린거 같다. 머리가 나쁜건지 문제가 어려운건지.. 이 문제의 정답률은 35% 인데, 좀 높게 잡히지 않았나 싶다. 2. 진짜 엄청 상세한 풀이 블로그를 찾아서 참고에 넣어두었다. 천천히 계속 읽어보자. 3. import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scan..

문제 링크 1. 처음 보고 정확한 식은 기억이 안 났지만, 고등학교 확통 시간에 배운 내용이 대략적으로 떠올랐다. 이 문제는 수학과 DP를 섞어 푸는 문제이다. 2. 기억이 안났던 식은 다음 식이였다. $_{n}C_{r}=_{n-1}C_{r-1}+_{n-1}C_{r}$ 이 공식은 파스칼의 삼각형에서도 구할 수 있다. 관련 내용은 아래 참고 블로그에서 공부하자. 3. import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); int[][]..

문제 링크 1. 이전에 풀었던 동전 1과 유사한 문제. 해당 문제의 풀이를 보고 복습하며 풀었다. 2. 동전 1 문제의 해설을 보고 이 해설을 보도록 하자. 차이점은 동전 1에서는 k 원을 만들 수 있는 모든 경우의 수를 구하지만, 동전 2에서는 최소한의 동전을 사용해서 만들 때 사용한 동전의 개수를 구하는 문제이다. 이를 위해서 다음과 같은 점화식을 세운다. dp[j] = Math.min(dp[j], dp[j - coin[i]] + 1) 유의할 점은 다음과 같다. 1. dp 배열을 모두 100001로 초기화 한다. 사용한 동전의 개수가 최악일 경우 100,000개이다. (동전의 가치가 최대 100,000원이기 때문이다.) 따라서 이 최대 + 1인 100001로 초기화한다. 2. dp[0] = 0이다. ..

문제 링크 1. 예전에 풀었던 가장 긴 증가하는 부분 수열 (11053)의 응용문제이다. 해당 문제의 풀이법을 잊었었는데, 다시 복습하며 문제를 풀었다. 복습의 중요성을 깨닫는다. 2. 이번에 알게 된 것인데, 가장 긴 증가하는 부분 수열을 구하는 알고리즘을 부르는 명칭이 존재했다. 이는 LIS 알고리즘으로, Longes Increasing Subsequence 의 줄임말이다. 이번 바이토닉 부분 수열을 구할 때에 이 LIS 알고리즘을 잘 적용하여야 한다. 가장 긴 바이토닉 부분 수열은 증가하다가 감소하는 부분 수열의 길이가 가장 긴 것을 구해야 한다. 이를 다시 말하면, 1. 증가하는 부분 수열의 길이 값도 최대로 2. 감소하는 부분 수열의 길이 값도 최대로 하여야 한다. 즉, 증가하는 부분 수열의 d..

문제 링크 1. 익숙한 DP 문제. 비슷한 유형의 문제를 풀어봐서 그런지 점화식이 딱 보였다. 2. dp[i][j]는 지금까지 가져올 수 있는 사탕의 개수의 최댓값이다. 이는 위, 왼쪽, 왼쪽 위 중 큰 값을 기준으로 현재 위치의 사탕 값을 더 해주면 된다. 다만, 나는 왼쪽 위를 기준으로 잡지 않았다. 이는 최단 경로를 구하는 문제라면 고려해줘야 하겠지만 사탕 개수의 최대를 구하는 문제인데 사탕 개수가 감소할 일이 없기 때문에 그렇다. 3. import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int n =..