나의개발일지

https://www.acmicpc.net/problem/1932 아래층으로 내려갈 땐 지금 당장 값이 작아도 끝까지 도착했을 때의 값이 더 클 수 있다.그럼 반대로 생각해보면 된다!위층으로 올라갈 때 직전 값 중 큰 값을 누적해가면 dp[0][0]이 최댓값이 된다.for(int i=n-1; i>=0; i--){ for(int j=0; j package BOJ.DP;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class BOJ_1932_정수삼각형 { public static void main(S..

https://www.acmicpc.net/problem/2170 처음엔 pq를 사용했는데 시간초과가 떠서 방법을 변경했다.정렬 후에는 이후 값이 무조건 직전값에 영향을 받을 수 밖에 없기에 그때그때 확장하는 방법이 가능해진다. 1. x값 오름차순 정렬 x값이 같다면, y값 오름차순 정렬2. 만약 다음 값이 이전 값에 걸친다면 끝 좌표만 확장2. 만약 걸치지 않는다면 이전 선의 길이를 계산해 저장한 후, 현재 x, y를 새로운 시작과 끝 값으로 정의3. 마지막 선 길이까지 더한 후 결과 출력 package BOJ.Greedy;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java..

https://www.acmicpc.net/problem/11054 결국은 가장 긴 오름차순 수열과 가장 긴 내림차순 수열.근데 이제 오름차순의 끝나는 수와 내림차순의 시작하는 수가 동일할 때의 최대 길이를 구하는 문제이다.1. 가장 긴 증가하는 부분 수열을 찾아 dpUp배열에 저장한다.2. 가장 긴 감소하는 부분 수열을 찾아 dpDown배열에 저장한다. (이때 배열의 끝부터 역으로 오름차순 탐색했다.)3. 각 위치에서 dpUp + dpDown - 1 (현재 위치 수 중복) 을 계산하며 최댓값을 갱신한다. package Study.Week05;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;i..

https://www.acmicpc.net/source/86922116 알고리즘의 난이도가 올라가면 더 이상 알고리즘 난이도의 문제가 아닌 아이디어의 문제임을 알려주는 대표적인 유형의 문제. 별의별 생각을 다 해보며 규칙을 찾아봤는데 결국은 하나였다. 오름차순으로 만들어야 한다는 것.오름차순으로 만들기 위해 옮겨지는 아이의 최소 수는? 이미 오름차순인 번호를 제외하고, 나머지 번호를 옮겨주면 된다.즉, (총 학생 수 - 가장 긴 증가하는 부분 수열) 인 것이다~!가장 긴 증가하는 부분 수열은 이전에 넘 많이 글을 올렸어서 링크로 첨부하겠당.https://dev-zsunny.tistory.com/65 99클럽 코테 스터디 30일차 TIL DP(상자넣기)https://www.acmicpc.net/proble..

https://www.acmicpc.net/problem/12852 우선 N의 범위가 최대 백만이기에, 각 3가지 경우를 모두 메모이제이션 하는 것은 불가능했다.그렇다면 최대 1차원 배열을 사용해야 한다는 것인데, 규칙이 뭘까? 하고 dp 배열을 그려봤다.예제 2를 대입해서 배열의 값으로는 연산 횟수를 저장하고자 할 때,이전 값에서 * 3, * 2, + 1 을 해서 현재 값이 되는 수의 배열 값 + 1(1회 연산) 을 한 것들 중 최솟값을 저장 하면 되겠다 싶었다.그래서 처음에 아래와 같이 작성하여 제출했다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { ..

https://www.acmicpc.net/problem/1965문제 읽으면서 든 생각. 어라..? 이거 그냥 가장 긴 증가하는 부분수열 아닝가..?https://www.acmicpc.net/problem/11053 (백준 11053 가장 긴 증가하는 부분 수열) 크기가 더 큰 상자에 크기가 더 작은 상자를 넣을 수 있고, 이렇게 넣을 수 있는 최대 상자의 개수를 구하는 문제.결국은 오름차순을 가지는 수열의 개수를 구하면 되는 문제이다.예제를 살펴보면 1 6 2 5 7 3 5 6 -> 1, 2, 3, 5, 6 으로 총 5개가 답이 된다.순차적으로 배열을 탐색하며 현재 값보다 인덱스가 작은(이전에 위치한) 값들을 보며 현재 값보다 작으면 해당 인덱스 dp에 + 1 씩 하며 최댓값을 갱신해준다.  packa..

https://www.acmicpc.net/problem/9461 처음에 이해가 잘 안돼서 P(N)을 쭉 써보다가 규칙을 찾았다. P(1) = 1,P(2) = 1,P(3) = 2,P(4) = 2,P(5) = 2,P(6) = P(3) + P(5) = 3,P(7) = P(2) + P(6) = 4,P(8) = P(1) + P(7) = 5,P(9) = P(4) + P(8) = 7,P(10) = P(5) + P(9) = 9,P(11) = P(6) + P(10) = 12,P(12) = P(7) + P(11) = 16 작성하다보니 슬슬 규칙이 보이기 시작했다.혹시 몰라서 문제의 그림을 보며 머릿속으로 그려봤는데 한바퀴를 돌 때까지 규칙이 일정하다는 것을 확인했다.P(1) ~ P(8) 이후부터는 P(N) = P(N-5..

https://www.acmicpc.net/problem/11055 어제와 비슷한 유형의 문제이다.문제에서 구해야 하는 값을 dp배열에 저장하는 값으로 설정하고, 그 규칙을 하나씩 찾아봤다.dp[0] 은 무조건 배열의 값일것이고, 그 뒤는 현재 값의 앞에 있는 값들을 탐색하면서 현재 값보다 작은 값이 있으면 그 값에 현재 값을 더한다.그리고 이런 값들을 Math.max를 통해 최댓값으로 갱신하며 구하면 끝!(자세한 건 아래 주석 참고)** 참 저 ans 때문에 98%에서 또 틀렸는데, ans를 자꾸 습관적으로 0으로 초기화해서 1 1을 넣었을 때 0이 나왔다(반목문 안돌아서)ans 초기화도 생각을 잘 해서 초기화하자.. 여기선 dp[0]으로.. package Study.Week04;/*1 : dp[0] ..

https://www.acmicpc.net/problem/11722 1시간 동안 고민했는데 도오저히 아이디어가 안 떠올라서 힌트를 봤다 >.순서대로 탐색하면서 현재 값보다 이전 값의 크기를 비교하며 수열의 길이를 메모이제이션 하면 된다.현재 값보다 이전 값이 클 때 그 이전 값에 + 1을 수열의 크기로 저장하면서 갱신해주면 된다.자세히 분석해보면 아래와 같다.10 30 10 20 20 1010 : dp[0] = 110, 30 => 10 or 30 : dp[1] = 110, 30, 10 => 30, 10 : dp[2] = dp[1] + 110, 30, 10, 20 => 30, 20 : dp[3] = dp[1] + 110, 30, 10, 20, 20 => 30, 20 : dp[4] = dp[1] + 110,..

https://www.acmicpc.net/problem/9655 DP문제 였는데 딱히 메모이제이션을 사용하진 않았다. 규칙을 도출하는 자체가 상향식 접근법이라고는 할 수 있겠지만..?무튼 코드에 주석으로 정리해놓고 풀긴했지만 한번 더 정리해보면!N을 1인 경우에서 부터 상근과 창영이 돌을 가져갈 수 있는 경우를 모두 정리해보았을 때결국은 홀수면 상근이 이기고, 짝수면 창영이 이기는 방법밖에 없다.따라서 N을 홀짝인 경우로 나누어 승자를 출력해주었다. 다만 여기서! 입력받는 값이 작아 Scanner를 사용했는데, 채점시간이 어어엄청 오래 걸리는 걸 확인했다.그래서 BufferedReader로 바꾸어서 한번 더 해봤는데, 확실히 좀 더 빨라졌고 이 기회에 Scanner와 BufferedReader에 대해 ..