파게로그

문제 링크: 11049번 행렬 곱셈 순서 https://www.acmicpc.net/problem/11049 아이디어는 다음의 두 지점에서 얻었다. 2차원 배열을 통해 부분 문제의 해를 저장해둘 수 있다. (원래 알고 있던 접근법) 행렬의 계산 순서는 바꿀 수 없다. (문제에서 제시된 조건) 계산 순서를 바꿀 수 없다는 조건은 대수롭지 않은 것으로 넘길 수 있지만, 굉장히 많은 경우의 수를 줄여주는 중요한 조건이다. 이는 바로 뒤 문제인 파일 합치기(문제 링크, 포스트 링크)에서도 마찬가지다. 여러가지 방법으로 저장할 수 있겠지만, 나는 dp[i][j]에서 i는 부분행렬의 마지막 행렬을, j는 부분행렬의 길이를 나타낼 때, dp[i][j]는 matrix[i-j+1:i+1]까지의 최소 연산 횟수를 나타내는..

문제 링크: 12865번 평범한 배낭 https://www.acmicpc.net/problem/12865 DP 알고리즘 중에서도 Knapsack 알고리즘을 대표하는 문제이다. 며칠을 고민하다가 전 과정 풀이를 참고했다. 풀이를 본 이상 점화식을 이해하는 것은 생각보다 어렵지 않았다. n개의 물품 중 고려하는 물품 번호가 1

문제 링크: 1912번 연속합 https://www.acmicpc.net/problem/1912 partialSum이 직전까지의 부분합보다 큰 경우에는 dp[i]는 partialSum이 될 것이고, 그렇지 않으면 dp[i]는 dp[i-1]과 같아야 한다. 하지만 partialSum이 음수인 경우에는 지금까지의 부분합을 버리고 0으로 초기화하는 과정이 선행되어야 한다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { public static void main(String[] args) throws IOException { /* input */ Buffer..

문제 링크: 2565번 제목 https://www.acmicpc.net/problem/2565 먼저 입력을 받은 후 A의 위치에 따라 정렬한다. 정렬된 상황에서 B 전깃줄은 증가하는 수열이어야 하기에 LIS의 최대 길이를 구하고, 이를 전체 전깃줄의 개수에서 빼준다. import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; public class Main { public static void main(String[] args) { /* input */ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); if (n==1) { System.out.println(0); S..

문제 링크: 11053번 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053 당분간 LIS 문제를 자주 접할 듯한데 정말 쉽지만은 않다고 생각된다. 이 문제의 경우 가장 긴 증가하는 부분 수열의 길이만을 알면 되므로, arr[i]보다 작은 arr[j] 중 최대인 dp[j]에 1을 더해주면 arr[i]를 포함하는 LIS의 길이가 나온다. 다만 arr[i]가 포함되지 않은 수열이 LIS일 수 있기에 dp를 모두 저장한 후 최종 출력 시 다시 한 번 최댓값을 찾아야 한다. 이는 O(n^2)의 알고리즘인데 보다 효율적인 알고리즘은 스스로의 힘으로는 힘들 것 같아 찾아서 익히고 구현해보도록 해야겠다. import java.io.BufferedReader; import ..

문제 링크: 2156번 제목 https://www.acmicpc.net/problem/2156 "연속으로 놓여 있는 3잔을 모두 마실 수는 없다"라는 조건에서 헤맸다. 내가 생각했던 것은, dp 배열이 이전의 정보를 담고 있는다는 것이었다. 즉 현재의 잔을 마셨을 때, 1번째 전 잔을 마셨을 때, 2번째 전 잔을 마셨을 때를 모두 나누어 생각해보고자 했다. 하지만 이러한 방법은 배열의 중간중간이 비게 되어 바람직하지 못하다. 어떤 잔을 마셨건 이를 저장할 필요없이 이러한 각각의 경우를 36라인과 같이 특정 시점까지의 잔 수를 dp[i-n]으로 살펴본 후 2번째 전 잔까지를 arr[i]로 별도로 더해주면 된다. package baekjoon.problem11053; import java.util.Scann..

문제 링크: 프로그래머스 Lv.2 기능개발 https://programmers.co.kr/learn/courses/30/lessons/42586 먼저 progresses를 배포까지 걸리는 날짜를 담고 있는 리스트로 바꾸어준다. 아직 배포되지 않은 기능들 중 가장 긴 기간을 long이라 하면, long이 progresses[i]보다 크거나 같으면 후자는 전자의 개발이 완료될 때까지 기다려야 한다. 반면 long이 progresses[i]보다 작으면 지금까지의 배포는 모두 완료되어야 한다. def solution(progresses, speeds): # 배포까지 남은 날짜로 변환 for i in range(len(progresses)): remainProg = 100 - progresses[i] remain..

문제 링크: 10844번 쉬운 계단 수 https://www.acmicpc.net/problem/10844 가장 마지막 자리인 mem[1]부터 시작해서 가장 첫 자리인 mem[n]까지 숫자를 붙여나가면서, mem[i]에는 가능한 경우의 수를 저장한다. n=1일 때를 제외하고는 mem[1][digit]에는, 아직 아무것도 정해지지 않은 상태이므로 반드시 1이 들어가야 한다. import java.util.Arrays; import java.util.Scanner; public class Main { static long[][] mem; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt..