dp 39

BOJ#1509 팰린드롬 분할

BOJ#1509 팰린드롬 분할 * 문제https://www.acmicpc.net/problem/1509 * 풀이- Manacher 알고리즘을 통해 임의의 범위의 문자열이 팰린드롬인지 구한다. - dp[i] : 0 ~ i 범위의 문자열을 팰린드롬 분할할 때 최소 분할 수 j ~ i 범위 문자열이 팰린드롬일 때, dp[i] = min(dp[i], dp[j-1] + 1)(여기서 j는 0 부터 i 까지) dp[0] = 1이고 -> dp[1] -> dp[2] -> ... -> dp[N-1]을 차례대로 구한다 * 나의 코드https://github.com/stack07142/BOJ/blob/d4b527b666ba54f7f53c1128f5a1523cb261d2b9/BOJ%231509/src/Main.java impo..

Algorithm/DP 2017.10.27

BOJ#2631 줄세우기

BOJ#2631 줄세우기 * 문제https://www.acmicpc.net/problem/2631 * 풀이일단 [4, 1, 2, 3, 5]인 경우의 문제를 손으로 풀어봅시다.거의 대부분 4를 3뒤로 옮겨서 한번만에 문제를 푸셨을 것입니다. 위 과정을 조금 더 상세하게 써보면 1. 수열에서 증가하는 가장 긴 부분 수열을 구하고 (이것들은 움직이지 않음)[4, 1, 2, 3, 5] 나머지 숫자를 적절한 자리로 이동시키면 옮겨지는 아이의 수를 최소로 하면서 줄을 세울 수 있습니다.[4, 1, 2, 3, 5] -> [1, 2, 3, 4, 5] 여기서 우리는 횟수만 구하면 되므로전체 길이 - LIS(Longest Increasing Subsequence) 길이 = 아이의 최소 이동 횟수 = 원하는 답 저는 LIS..

Algorithm/DP 2017.09.28

BOJ#10164 격자상의 경로

BOJ#10164 격자상의 경로 * 문제https://www.acmicpc.net/problem/10164 * 풀이카카오 블라인드 채용 - 1차 테스트의 모의 테스트에 나온 문제와 유사합니다. 점화식은 간단하게 dp[row][col] = dp[row-1][col] + dp[row][col-1] 임을 알 수 있습니다. 단, K가 0이 아닌 경우 경유지가 1개 있는 것이므로이 경우 시작점->경유지, 경유지->도착점의 경우의 수를 각각 구한 뒤 곱해주면 원하는 답을 얻을 수 있습니다. * 나의 코드 https://github.com/stack07142/BOJ/blob/4cccafbf34e20c197249ac96c20b33f15e644bb1/BOJ%2310164/src/Main.java import java.i..

Algorithm/DP 2017.09.26

BOJ#1915 가장 큰 정사각형

BOJ#1915 가장 큰 정사각형 * 문제https://www.acmicpc.net/problem/1915 * 풀이카카오 모의 테스트에서 나온 문제와 동일합니다. 풀이 아이디어는 다음과 같습니다.검사 위치에서 인접한 3방향(위쪽, 왼쪽, 왼쪽위 대각선 )의 값을 검사하여검사 위치의 값을 최소값 + 1으로 갱신해줍니다. * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%231915/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class M..

Algorithm/DP 2017.09.22

BOJ#1309 동물원

BOJ#1309 동물원 * 문제https://www.acmicpc.net/problem/1309 * 풀이N이 1일 때부터 3일때까지 그림을 직접 그려보면 규칙을 찾으실 수 있을겁니다. 점화식dp[row][0] = (dp[row - 1][0] + dp[row - 1][1] + dp[row - 1][2]) % MOD; dp[row][1] = (dp[row - 1][0] + dp[row - 1][2]) % MOD; dp[row][2] = (dp[row - 1][0] + dp[row - 1][1]) % MOD; * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%231309/src/Main.java import java.io.BufferedReader; impo..

Algorithm/DP 2017.09.15

BOJ#2096 내려가기

BOJ#2096 내려가기 * 문제https://www.acmicpc.net/problem/2096 * 풀이메모리 제한이 4MB 입니다. 저는 처음에 재귀 형식으로 풀었다가 바텀업 방식으로 다시 풀었습니다. 또한, [100001][3] 사이즈의 dp배열과 map 배열을 모두 제거하였습니다. 두가지 형태의 코드 모두 아래에 붙여놓았으니 참고하시면 좋겠습니다. * 나의 코드 https://github.com/stack07142/BOJ/blob/458582301c132e9a61af00c77068edac24669619/BOJ%232096/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStream..

Algorithm/DP 2017.09.12

BOJ#2294 동전 2

BOJ#2294 동전 2 * 문제https://www.acmicpc.net/problem/2294 * 풀이dp 기본 문제입니다.solve 함수는 크게 3부분으로 구성되어 있습니다. dp 정의dp[coinSum] : 현재 동전의 합이 coinSum일 때, k가 되기 위해 추가해야 하는 동전의 최소 개수solve(coinSum) 함수 : dp[coinSum]을 반환하는 함수. 1. 기저 사례동전의 합이 k에 딱 맞는 경우, return 0동전의 합이 k에 맞지 않는 경우, return 매우 큰 수 if (coinSum == k) return 0; if (coinSum > k) return INF; 2. 메모이제이션 dp 배열의 값을 -1로 초기화 했습니다. 즉, dp[coinSum]이 -1인 경우 메모이제이..

Algorithm/DP 2017.09.12

BOJ#1890 점프

BOJ#1890 점프 * 문제https://www.acmicpc.net/problem/1890 * 풀이dp + dfs로 풀었습니다.정답 비율에 비해 문제가 굉장히 쉽습니다. N 범위와 경로의 개수 범위(long)만 주의하면 될 것 같습니다. * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%231890/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static final int[] dRow = {0, 1}; stat..

BOJ#2167 2차원 배열의 합

BOJ#2167 2차원 배열의 합 * 문제https://www.acmicpc.net/problem/2167 * 풀이단순하게 for loop 2개로 (i, j) ~ (x, y) 원소들을 더해도 되지만계산량을 줄이기 위해서 아래와 같이 구현해보았습니다. 1. 입력을 받으면서 dp[row][col]를 계산해 놓는다.dp[row][col] : (row, 1) 부터 (row, col)까지의 합 2. K개의 쿼리를 입력 받는다. (i, j), (x, y) 3. 행 단위로 합을 구하고 sum 변수에 합산한다. for ( row = i ... x) { sum += dp[row][y] - dp[row][j - 1];} * 나의 코드https://github.com/stack07142/BOJ/blob/6ac31273349..

Algorithm/DP 2017.05.10