매일 조금씩

문제 https://programmers.co.kr/learn/courses/30/lessons/12902# 코딩테스트 연습 - 3 x n 타일링 programmers.co.kr 풀이 전형적인 dp문제로 규칙을 찾아서 점화식을 세워서 풀 수 있다. 아래 문제는 조금 더 쉬운 버전이다. 2021.10.29 - [Problem Solving/Programmers] - [프로그래머스] 2 x n 타일링 (Java) [프로그래머스] 2 x n 타일링 (Java) 문제 https://programmers.co.kr/learn/courses/30/lessons/12900 코딩테스트 연습 - 2 x n 타일링 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 ..

문제 https://programmers.co.kr/learn/courses/30/lessons/12913 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟 programmers.co.kr 풀이 정수 삼각형과 유사한 문제이다. land와 동일 사이즈의 배열을 생성하여 행과 열을 순회하면서, 해당 index에서 가질 수 있는 최대 점수를 저장해나간다. 마지막 행의 최대 값이 답이 된다. 2021.11.08 - [Problem Solving/BOJ] - [BOJ 1932] 정수 삼각형 (Java) [BOJ 1932] 정수 삼각..

문제 https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 풀이 dp 문제로 각 위치마다 최대값을 저장해나간다. 마지막 행에서 가장 큰 값이 답이된다. 2021.11.08 - [Problem Solving/BOJ] - [BOJ 1932] 정수 삼각형 (Java) [BOJ 1932] 정수 삼각형 (Java) 문제 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄..

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://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 풀이 집에서 학교 까지의 최단 경로의 수를 구하는 문제이다. 아래, 우측 방향으로만 이동할 수 있고 물웅덩이는 지나갈 수 없다. 행렬 크기 값이 보통 문제와 달리 반대로 주어지니, 헷갈리지 않도록 유의해야 한다. 처음에 dfs, bfs 로 시도했지만 정답은 맞지만 효율성에서 통과가 안된다. 해당 문제는 동적 계획법 카테고리에 있는 문제로, DP로..

문제 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..