아무튼, 쓰기

#문제         레벨:  G1알고리즘:  dp(팰린드롬)풀이시간: 힌트 참조 유무:https://www.acmicpc.net/problem/1509#문제 풀이        팰린드롬 문자열의 정의: 처음 ~ 끝으로 읽으나 끝 ~ 처음으로 읽으나 같은 문자열1. 팰린드롬 판별 배열palindrom[i][j](i ~ j까지 팰린드롬인지)을 저장한다. 2. 이중 for 문을 돌며 dp[i]값을 저장한다. dp[i] =1 ~ i까지 탐색했을 때 최소 팰린드롬 문자열의 조합 예시)초기화:dp[0] = 0, dp[1~4] = MAXend = 1 ("A" 까지):start = 1: "A"는 팰린드롬dp[1] = min(MAX, dp[0] + 1) = min(MAX, 0 + 1) = 1dp: [0, 1, MAX, ..

#문제         레벨: G4알고리즘: dp풀이시간: 힌트 참조 유무:https://www.acmicpc.net/problem/17404#문제 풀이        dp에서 중요한 것은 아래와 같습니다.1. 상태의 정의2. 점화식의 정의bottom-up방식으로 점화식을 세워보겠습니다.현재 상태에서 가장 최솟값임을 보장하려면, 현재 색깔 + 이전색깔 중 최솟값이어야 합니다. 점화식으로 나타내면dp[i][0] = cost[i][0] + Math.min(dp[i-1][1],dp[i-1][2]);dp[i][1] = cost[i][1] + Math.min(dp[i-1][0],dp[i-1][2]); dp[i][2] = cost[i][2] + Math.min(dp[i-1][0],dp[i-1][1]); 입니다.dp[i..

#문제         레벨: G2알고리즘: 조합, dp풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/1256 #문제 풀이        이 문제에서 얻어갈 점은 두가지입니다.1. 조합을 계산하는 방법(일반 계산, dp로 표현)2. 문제 해결 아이디어문제 해결 아이디어부터 설명드리겠습니다. 문제를 보자마자 모든 알파벳 조합을 만들어 보는 것은 시간제한이 걸린다는 것을 직감할 수 있습니다. 그렇다면 저희가 해야 할 일은 앞에 놓을 수 있는 글자들을 놓아보는 것입니다. 앞에 a가 올려면 a~~~~에 문자열이 K번 째 문자열이 포함된다는 거고 앞에 z가 올려면 z~~~~에 k 번째 문자열이 포함된다는 겁니다.다르게 설명드리면, a~~~~에 놓을 수 있는 경우의 수가 ..

#문제         레벨: G5알고리즘: dp 풀이시간: 20분 힌트 참조 유무: 유https://www.acmicpc.net/problem/2169 #문제 풀이         Top-down DP (DFS + DP):재귀를 사용메모이제이션(기존에 계산한 값을 저장)큰 문제를 작은 문제로 나누어 해결주로 @(재귀 + 메모이제이션) 방식으로 구현Bottom-up DP:반복문을 사용작은 문제부터 차례대로 해결반복문으로 점화식 구현테이블을 채워나가는 방식// top-downint fibonacci(int n) { if (dp[n] != -1) return dp[n]; if (n  #풀이 코드      import java.io.*;import java.util.*;public class Main ..

#문제레벨: G3알고리즘: dp풀이시간: 1:20힌트 참조 유무: 유https://www.acmicpc.net/problem/2629#문제 풀이**첫 번째 접근: 실패처음 보자마자 **브루트 포스로 시간 복잡도가 통과되는지 확인했습니다. 구슬의 조합으로 해당 숫자를 잴 수 있는지 확인하려면, 숫자들의 플러스 마이너스의 조합입니다. 예를 들어 설명하겠습니다.아래 4개의 숫자 사이에 + 혹은 - 를 대입하고 합을 구하면 측정할 수 있는 무게가 됩니다. 만약 모두 -로 값이 음수라면 절대값을 씌우면 됩니다. 모두가 +인 값과 동일하기 때문입니다. 이 방식의 최악의 시간복잡도를 따져보면, 빈칸의 들어갈 조합의 경우의 수이기 때문에 2^30(N 최대값) 입니다. 1,024 x 1,024 x 1,024 = 1,00..

#문제레벨: G1알고리즘: dp + 브루트 포스 + 비트 마스킹풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/2098#문제 풀이TSP(Traveling Salesman Problem)시간 복잡도 O(n^2 * 2^n)이 문제는 전형적인 TSP 문제입니다. 한 노드에서 출발하여 모든 노드를 순회하고 다시 시작점으로 돌아오는데 최소값을 구하는 문제가 TSP입니다.TSP 문제를 가장 무식하게 푸는 방법은 모든 경우의 수를 다 탐색해보는 것입니다. 모든 경우의 수를 탐색해보는 것은 N!인데, 알고리즘에서 가장 나쁜 경우의 수가 N!입니다.저희는 DP를 사용해야 합니다. 큰 문제를 작은 문제로 쪼갠다. N = 3 일 때를 가정하면 아래와 같은 경우의 수가 있습니다.1..

#문제         레벨: G3알고리즘: dp + dfs풀이시간: 힌트 참조 유무:https://www.acmicpc.net/problem/2186#문제 풀이         처음 문제를 봤을 때 별 생각없이 아래와 같이 dfs 코드를 짰다. 코드는 문제에 맞게 구현됐다. 단지, 시간 초과가 날 뿐이다...잠시 이 dfs 코드를 흝어봐주고 내려와주라.dfs코드import java.io.*;import java.util.*;public class Main { static int N, M, K; static char[][] board; static String word; static int[] dx = {-1, 1, 0, 0}; static int[] dy = {0, 0, -1, ..

#문제         레벨: G4알고리즘: dp(기초)풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/7579 #문제 풀이        dp에 담기는 것은 i의 비용으로 비활성화하는 앱들의 비용 합계를 나타낸다.M으로 dp배열을 만들면 메모리 초과가 날 것을 직관적으로 알 수 있다. dp 배열을 cost로 잡는다. 이 dp는 이차원배열 풀이와 일차원 배열 풀이가 있다.이차원 배열 풀이dp[i][j] 에서 i는 1~i 앱까지 탐색했는지 나타내고 j는 cost를 나타낸다. 즉, dp 배열은 1 ~ i번까지 탐색하여 cost j를 이용하여 최대한 비울 수 있는 메모리를 나타낸다. 일차원 배열 풀이dp[i]에서 i는 i의 cost가 주어졌을 때 최대한 비울 수 있는 ..

#문제         레벨: S3알고리즘: dp풀이시간: 30분 힌트 참조 유무:https://www.acmicpc.net/problem/9095#문제 풀이        dp[i] = dp[i-1] + dp[i-2] + dp[i-3]이와 같은 점화식이 세워진 이유는 이러하다. dp[4] = dp[3] +  dp[2] + dp[1] 를 예시로 들어 설명해보겠다.         dp[1] = 1;  // 1         dp[2] = 2;  // 1+1, 2         dp[3] = 4;  // 1+1+1, 1+2, 2+1, 3dp[4]는 dp[1] 마지막에 3을 붙이면 되고 dp[2] 마지막에 2를 붙이면 된다. dp[3] 마지막에 1를 붙이면 된다.1+31+1+2, 2+21+1+1+1, 1+2+1,..