IT 개발 돼지의 일상

출저 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4yC3pqCegDFAUx "와 어려웠다.인수분해" 처음엔 0~9 까지 숫자를 눌러 X를 구하려고 했다. 굉장히 구현이 잘 되지 않았다. 1 = 11*1 = 11*1*1 = 1 이런 경우 어떻게 처리할까.. 그래서. 약간의 기초적인 수학적인 지식이 필요했다. 어떤 수들을 곱해서 X가 만들어 졌고, X를 계속 인수분해 하다보면 계산기를 눌러 가능한 a * b *.. *... * 의 형태로 나올 것이다.. 따라서 해당 문제에서는 주어진 X값을 인수분해 하여 해당 a * b 의 형태로 바꾼 후에, a와 b를 계산기로 칠 수 있는지 확인하고, 그렇지 않다면 다시 ..

출저 : https://www.acmicpc.net/problem/1463 "DP DP 딥" 1을 가지고 N을 만든다고 역으로 생각하자. dp[3] 까지 최소값을 구한다. 1이 되겠다. 그 이후에 4를 만드려면 어떤 방법이 있을까? 2 에서 2를 곱하거나 3에서 더하기 1을 하거나. dp[n/2] + 1 ( n % 2 == 0 )dp[n] = dp[n/3] + 1 ( n % 3 == 0 ) dp[n-1] 이중에 최소값을 dp[n]으로 한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344import java.util.Scanner; public class Main { static int n; static int..

출저 : https://www.acmicpc.net/problem/2579 "DP 쓸 때, dp값과 map에 값을 활용해보자.." 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader; public class Main { static int N; static int[] dp; static int[] map; public static void main(String[] args) throws IOException{ BufferedReader br = n..

출저 : https://www.acmicpc.net/problem/1149 "DP" 어려웠다. 기초적인 dp문제라고 했는데 왜 이리 어려웠지...ㅎㅎ dp[x] = dp[x-1] + min(x) ; 까지는 생각을 하고, 해답을 봤다. 그리고 최초 dp[0] 가 R,G,B 일 때를 모두 체크하기위해 dp[x][3] 배열을 만들어 해당 dp 값을 이용한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringToken..

출저 : https://www.acmicpc.net/problem/1003 "DP" 12345678910111213141516171819202122232425262728293031323334353637import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader; public class Main { static int T,N; static int z, o; static int dp[][]; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws IOException { BufferedReader b..

출저 : https://www.acmicpc.net/problem/1932 "DP, bottom-up / DP라고 무조건 재귀 생각하지말자." 알고리즘은 삼각형의 맨 밑부분부터 시작해서 dp 갱신을 시작한다. 처음에 재귀로 구현했는데 시간초과가 났다. dp 값을 비교해서 기존 dp 값보다 작으면 탐색하지 못하게 하였는데??? 라고 생각했다. dp 값이 나중에 큰 값으로 갱신된다면, 이전 까지 탐색 경로들은 그냥 지나칠 거임.. 따라서 해당 지점에 가능한 가장 큰 값이 맨 나중에 갱신되는 데이터가 주어졌다면 아마 dp 값 비교를 통한 가지치기는 적용 안될듯. 1234567891011121314151617181920212223242526272829303132333435363738394041424344impo..

출저 : https://www.acmicpc.net/problem/1937 "DP" DP를 이용한 문제이다. top down 방식을 사용한다. 재귀를 할 때, 리턴 값이 있는 경우 처리를 잘해 주어야 겠다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer; public class Main { s..

출저 : https://www.acmicpc.net/problem/1890 "DP 와 2^63" 전형적인 DP 문제로서 Top-down 방식의 메모이제이션을 사용한다. Start 부터 시작해서 End 까지 탐색한다. 검색 중에 End 에 도착했다면 한 가지 방법이 있는 것이므로 1을 리턴하고 이 값은 함수를 호출한 dp[x] 에 누적된다. 아래 예를 보면 4,5,6 번 노드가 이와 같다. 이런식으로 "누적"을 하게 되면 해당 노드에서 End로 갈 수 있는 방법의 수가 dp[x]에 저장된다. DFS 나 BFS 로 풀면 시간초과가 날 것이 왜 dp를 쓰면 시간이 단축 되나? 라는 질문에 답은 7번 노드를 보면 된다. 7번 노드까지 탐색한 후에 6번 노드의 dp값을 체크하였더니 1이 저장되어 있더라. 6번 이..

출저 : https://www.acmicpc.net/problem/15486 "DP" 다시 보기. 12345678910111213141516171819202122232425262728293031323334353637383940import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main { static int n; static int[][] map; static int[] dp; public static void main(String[] args) throws IOException { BufferedReader br..

출처 : https://www.acmicpc.net/problem/2186 "전형적인 DP 문제, 재귀 호출 및 리턴에 대해 잘 알고있자." N,M 의 범위를 고려하면 100,000 개의 칸이 존재한다. 대략 계산해 봤을 때, 100*100 개 칸에서 갈 수 있는 방법의 개수는 4가지 방향에 최대 5칸의 거리 20개가 된다. 20^100,000 ... 브루트 포스로는 절대 돌아가지 않는다. 100 * 100 격자에 모든 문자가 'B' 이며 'BB' 를 만드는 경우의 수를 생각해보면 굉장히 많다. 그리디한 방법도 없고, 이럴 때는 DP 를 이용해 푸는 것이 좋겠다. 사실 이런 격자 문제를 풀때 DP를 사용하면 나는 항상 DP[X][Y][?] 이런 식으로 놓고 생각해본다. 무엇을 어떻게 메모이제이션 할 것인..