매일 조금씩

문제 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 풀이 전체 전깃줄 개수 - 전깃줄의 최장증가 수열 개수 = 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수 A 값의 순서로 B 값을 수열로 만들어보면 {8, 2, 9, 1, 4, 6, 7, 10} 이다. 이 수열의 최장증가수열의 개수를 구해서, 전체 전깃줄 개수에서 빼면 답을 구할 수 있다.입력이 정렬되어 들어오지 않기 때문에 A값 기준으로 정렬한 후, 이분 탐색 이용하..

LCS 문제란? 최장 공통 부분수열 문제는 LCS라고도 불린다. 이는 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제다 https://ko.wikipedia.org/wiki/%EC%B5%9C%EC%9E%A5_%EA%B3%B5%ED%86%B5_%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4 최장 공통 부분 수열 - 위키백과, 우리 모두의 백과사전 최장 공통 부분수열 문제는 LCS라고도 불린다. 이는 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제다.(종종 단 두 개중 하나가 되기도 한다.) 컴퓨터 과학에 ko.wikipedia.org 문제 https://www.acmicpc.net/problem/9251 9251번:..

문제 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 풀이 arr[i]= i번째 잔의 포도주양 dp[i] = i번째 잔까지 있을 때 마실 수 있는 최대 포도주 양 세 가지 경우로 나누어 볼 수있다. 1. i번째 잔을 마시지 않았을 경우 dp[i] = 이전 잔까지 있을 때의 마실 수 있는 최대 포도주 양 dp[i] = dp[i-1] 2. i번째 잔을 한 번 연속으로 마실 경우 i-1번째 잔을 건너 뛰어야 한다. dp[i] = dp[i-2] + ar..

문제 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 풀이 7 7 3 10 8 15 8 18 1 16 0 15 2 20 7 25 4 20 4 19 4 24 5 30 2 27 6 26 5 24 2차 배열에 최대값을 저장하면서 더해나간다. 첫번째 값 dp[i][j] = num + dp[i-1][j]; 마지막 값 dp[i][j] = num + dp[i-1][j-1]; 나머지 값 dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]); 마지막 행의 최대값을 구한다. N이 1일 경우 for문 내에서..

문제 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 dp[i]의 최대값을 찾으면 됨 dp[i]? i번째 수를 포함하는 연속합의 최대값 dp[i] = dp[i-1] + i번째 수 단 dp[i-1]이 음수일 경우에는 더하지 않는다. 10 -4 3 1 5 6 -35 12 21 -1 10 6 9 10 15 21 -14 12 33 32 소스코드 package dp; import java.io...

문제 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 풀이 규칙을 찾아서 점화식을 세운다. n=5 까지 작은 문제들의 답을 넣고, n=6 부터는 dp[n] = dp[n-1] + dp[n-5] 로 구할 수 있다. 결과를 담을 배열의 자료형이 long형이어야 한다. 소스코드 package dp; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamR..

문제 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 풀이 타일을 0과1로 표현했을 뿐이지 아래와 동일한 문제이다. dp[1] = 1 dp[2] = 2 dp[3]부터는 아래 점화식을 따른다. dp[i] = dp[i-1]+ dp[i-2] 2021.10.29 - [Problem Solving/Programmers] - [프로그래머스] 2 x n 타일링 (Java) [프로그래머스] 2 x n 타일링 (Java) 문제 https://programmers.c..

문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 DP문제로, Index를 차례대로 증가시키면서 해당 Index 왼편에 올 수 있는 바이토닉 부분 수열의 최대 개수를 구한다. 이때 기준 Index에서 작은 Index를 체크하면서, 기준보다 작은 수의 바이토닉 수열 최대 개수 중에 최대 값을 구한 후 +1을 해주면 된다. 아래 문제의 왼쪽 편만 구한 것이다. ..

문제 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 기준 숫자에서 왼쪽과 오른쪽을 나눈다. left[i] = i번째 수의 왼편에 올 수 있는 오름차순 부분 수열의 최대 개수 right[i] = i번째 수의 오른편에 올 수 있는 내림차순 부분 수열의 최대 개수 left[i] + right[i] 의 최대값에 1을 더한 것이 답이 된다. (1을 더하는 이유는 left, right에 기준 숫자가 빠져있기 때문) 차례대로 index를 증가 또는 감소 시키면서 채워나..

문제 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 DP문제가 제일 어렵다. DP문제는 사고의 전환이 필요하다. 나한테 너무 어려운 부분... 어쨌든 해당 문제는 구글링을 통해 힌트를 조금 얻어서 풀었다. dp[i][j] = i자리수에서 j로 끝나는 계단수의 개수 N(자리수)가 1일 때 1, 2, 3, 4, 5, 6, 7, 8, 9 dp[1][0] = 0 dp[1][1] = 1, dp[1][2] = 1 ... dp[1][8] =1 dp[1][9] = 1 N이 2일 때 10 / dp[2][0] = 1 21 / dp[2][1] = 1 12, 32, / d..