매일 조금씩

문제 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://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 풀이 분할정복으로 푼다. 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 사분면 순으로 재귀함수를 호출하면서 모든 숫자가 1이면 1 출력, 0이면 0 출력. 이외의 케이스는 좌표와 크기를 갱신하여 다시 재귀를 돌려주면 된다. 2021.11.16 - [Problem Solving/BOJ] - [BOJ 2630] 색종이 만들기 (Java) [BOJ 2630] 색종이 만들기 (Java..

문제 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://programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 풀이 기본적으로 BFS와 DP방식으로 문제를 접근했다. BFS로 영역을 확장해 나..