매일 조금씩

문제 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://programmers.co.kr/learn/courses/30/lessons/12979 코딩테스트 연습 - 기지국 설치 N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5 programmers.co.kr 풀이 N: 200,000,000 이하의 자연수 stations의 크기: 10,000 이하의 자연수 stations는 오름차순으로 정렬되어 있고, 배열에 담긴 수는 N보다 같거나 작은 자연수입니다. W: 10,000 이하의 자연수 시간 초과에 유의해서 풀어야 한다. N이 2억개이므로, N으로 순회를 한다면 시간초과가 발생한다. statio..

문제 https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 풀이 bfs로 1번 노드부터 탐색하면서 각 노드 별로 depth를 저장하면 풀 수 있다. depth 저장 배열을 정렬시킨 후 max값을 count 한다. 소스코드 import java.util.*; class Solution { int[] depth; boolean[] visited; ArrayList[] nodes; public int solution(int n, int[][] edge) { // 자료 구조 생성 depth ..

문제 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로 영역을 확장해 나..

LIS 알고리즘이란? LIS 알고리즘 (Longest Increasing Subsequence Algorithm) 은 최장증가수열 알고리즘으로 증가하는 원소들의 가장 긴 부분집합을 찾는 알고리즘이다. 풀이 1. DP로 풀기 시간 복잡도 O(N^2) 이기 때문에 원소의 개수가 작은 경우에는, 해당 방법으로 문제를 풀 수 있다. {10 20 10 30 20 50} 수열 1 2 3 4 5 6 10 20 10 30 20 50 DP[i] = i번째 원소를 포함하는 증가 수열의 최대 원소 개수 N=1 1 2 3 4 5 6 1 N=2 1 2 3 4 5 6 1 2 현재 index의 원소 값과, 그 미만의 index의 원소 값을 비교 현재 원소보다 작은 원소가 있다면 해당 index의 dp값 중 최대값에 + 1을 한 것..

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