Post-IT

1. 문제 분석 오름차순이 되는 부분 수열중에 가장 긴 수열의 길이를 구하면 된다. A의 크기가 1000이라 가장 긴 수열을 직접 구해도 될거같은데, 근데 알고리즘이 DP로 분류되어 있어 DP로 풀었다. 시간복잡도 : O(N^2) 알고리즘 : DP2. 문제 풀이수열을 부분적으로 잘라서 부분수열들에서 한 항씩 추가해 가면서 최대 길이를 구한다.arr[j] > arr[i] : 더 큰 값을 발견dp[i] = Math.max(dp[i], dp[j]+1)더 큰값이 아닐때j++이렇게 부분수열로 쪼개 작은 수열부터 최고 길이를 구해가면 된다.3. 코드 구현import java.io.InputStreamReader;import java.util.Scanner;public class BOJ_11053 { publi..

1. 문제 분석 보자마자 점화식이 떠올랐다... 너무 쉬운거 같은데 왜 정답률이 저렇게 낮지.. 시간복잡도 : O(N) 알고리즘 : DP2. 문제 풀이보자마자 떠올랐다. 두가지 케이스 밖에 없다.2개 적은 경우의 수에서 가로로 두개 붙이기1개 적은 경우의 수에서 세로로 한개 붙이기dp[i] = dp[i-2] + dp[i-1] 라고 생각하고 풀었는데... 자꾸 답이 틀렸다고 나온다. 제한 시간도 메모리도 아닌데,, 왜 dp[N]%10007이 아닌지 아무리 생각해도 몰랐는데, n이 1000으로 충분히 작다고 생각했었다. 질문 게시판을 둘러보니 생각보다 dp값이 크게 변할 수 있다는걸 알게되었고 모듈러 성질이라는 것을 알았다.(A+B)%M = {(A%M) + (B%M)}%M이 성질을 이용해서 dp를 계산할 때..

1. 문제 분석매우 쉬운 DP 문제이다. 피보나치 문제와 유사하다. 시간복잡도 : O(TxNxK) 알고리즘 : DP2. 문제 풀이k층 n호의 인원수를 구하면된다. k-1층 n호까지의 인원의 합을 구하면된다.dp[k][n] = dp[k-1][1] + dp[k-1][2] + dp[k-1][3] .. + dp[k-1][n]dp[k][n-1] = dp[k-1][1] + dp[k-1][2] + dp[k-1][3] .. + dp[k-1][n-1]아주 쉽다. 즉 같은 층 이전 호수 + 아래층 현재 호수를 더하면 된다.dp[k][n] = dp[k][n-1] + dp[k-1][n] 3. 코드 구현import java.util.Scanner;public class BOJ_2775 { public static void..

1. 문제 분석 이전에 비슷한 배낭문제를 푼 적이 있어 1-0 배낭 문제처럼 풀었다. 그런데 여러 자료구조를 써봤는데도 계속 메모리 초과가 나서 찾아보니 기존의 방법대로 하면 K가 클 경우 계산이 매우 길어지게 된다는 것을 알게 되었다. 새로 찾아낸 방법이 바로 이진 분할이라는 것이였다.M개의 물건을 1부터 2의 거듭제곱 형태로 묶어 새로운 그룹을 만드는 것이였다.  시간복잡도 : O(N log M) 알고리즘 : DP(+ 이진 분할)2. 문제 풀이이 문제의 풀이는 사실 기존의 배낭문제와 다를게 없다. 다만, 중복된 물건을 최대한 간소화 시키는것이 핵심이다.간소화 방법은 다음과 같다.M개의 동일한 물건을 1, 2, 4, ...로 분할 시켜 저장한다. 가치 값도 개수에 맞게 계산하여 서로다른 X개의 물건으로..

1. 문제 분석이번 문제도 DP를 활용하면 풀 수 있는 문제이다. 우리가 DP를 배운다면 많이 들어봤을 배낭 문제이다. 시간복잡도 : O(NxK) 알고리즘 : DP2. 문제 풀이기본적으로 많이 배우는 배낭문제랑 다를게 없다.배낭 무게가 불가한 경우 : 이전 차수(i)의 가치값을 그대로 가져온다.dp[i][w]=dp[i−1][w]배낭에 추가가 가능한 경우 : 현재 물건의 가치 + 남은 무게 만큼의 가치 값dp[i][w]=max(dp[i−1][w],dp[i−1][w−weight[i]]+value[i]) 3. 코드 구현import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.S..

1. 문제 분석 이번 문제도 DP를 활용하면 풀 수 있는 문제이다. DP는 매번 느끼지만 코드는 간단한데 점화식 찾는게 제일 어려운 것 같다. 시간복잡도 : O(N) 알고리즘 : DP2. 문제 풀이이번 문제에는 조금 까다로운 조건이 붙는다. 계단을 연속해서 등반할 수 없다. N번째 계단에 무조건 도달해야 되기 때문에 N-1, N-2 를 모두 밟는다면 도착점에 도달할 수 없게 된다. 우선 X번째 계단에 올 수 있는 경우는 두가지이다. 이전에 연속 계단을 밟았고 한칸 넘어 오는경우, 이전에 연속해서 밟지 않았기에 바로 전 블록에서 오는 경우.한칸 넘어 올때 : dp[i] = stair[i] + dp[i-2]바로 전 블록에서 오는경우 dp[i] = stair[i] + dp[i-3] + stair[i-1]두번째..

1. 문제 분석 이 문제는 바로 전날 풀었던 1149번 RGB거리와 매우 유사하다. 정수 X를 1로 만드는 최소 횟수를 구하면 된다. 작은 문제에서 큰 문제로 해결해가는 Bottom-Up 방식으로 풀면 될거 같았다. 시간복잡도 : O(N) 알고리즘 : DP2. 문제 풀이2~X까지 각 숫자가 1이 되는 최솟값을 구하면 된다. 작은 값부터 배열에 저장해가면서 최종 값을 계산한다.dp[i] = dp[i-1] + 1 dp[i] = dp[i/2] + 1 (단 i가 2로 나누어질 때)dp[i] = dp[i/3] + 1 (단 i가 3로 나누어질 때)3. 코드 구현import java.util.Scanner;public class BOJ_1463 { public static void main(String[] ar..