Koo's.Co

2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 풀이 위상 정렬과 dp를 이용해 풀 수 있는 문제입니다. ACM Craft 문제와 거의 동일한 문제인 것 같습니다. 먼저 위상 정렬을 이용해 각 값들의 진입 차수를 구해준 후 bfs를 사용했습니다. 작업을 하기 위해서는 선행 작업들을 모두 수행해야 하기 때문에 dp리스트를 만들어 이전 작업들 중 가장 시간이 오래 걸린 값들만 저장해줍니다. -> max를 이용해 노드에 한 번 도착할 때마다 값을 갱신! 모든 작업이 완료된 시간을 구해야하기 때문에 max를..

1. 1, 2, 3 더하기 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 새로 오는 수는 그 전의 숫자들에 각각 1, 2, 3을 더해 만들 수 있다. 4의 경우 이전 3개의 숫자에 1, 2, 3을 더해 만들 수 있다. 그러므로 구하고자 하는 점화식은 위와 같다. import sys read = sys.stdin.readline dp = [0, 1, 2, 4] + [0] * 7 for i in range(4, 11): dp[i] = dp[i-1] + dp[i-2] + dp[i-3] for _ in range(int(read())): print(dp[int(read())]) 2. 1, 2, 3 더하기 2..

12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 저번에 푼 11053 - 가장 긴 증가하는 부분 수열 문제는 O(N^2)의 시간복잡도로도 풀이가 가능했습니다. 오늘 풀 문제는 수열 A의 크기가 최대 1,000에서 1,000,000으로 1,000배 증가했지만 시간 제한은 동일하기 때문에 O(N^2)의 알고리즘으로 풀면 시간 초과가 됩니다. 풀이 import sys from typing import List read = sys.stdin.readline def lower_bound(nums: List[int], t..

11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 가장 긴 증가하는 부분 수열 문제는 DP로 풀 수 있는 대표적인 문제로, LIS(Longest Increasing Subsequence)라 불리는 문제입니다. 입력받은 리스트 A와 동일한 크기의 dp 리스트를 생성합니다. dp 리스트는 각각의 원소가 가지는 최대 부분 수열의 길이를 저장합니다. 각각의 원소는 최소 1이상의 값을 가지므로 dp = [1] * N으로 초기화하려 합니다...

1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 1. 별도의 dp 리스트를 생성하지 않는 방법 별도의 dp 리스트를 생성하지 않고, rgb라는 2차원 배열을 이용해 각 집을 칠하는 비용을 저장하려 합니다. (리스트를 2개를 생성하면 그만큼의 공간복잡도가 증가하여 dp리스트를 생성하지 않고 풀었습니다) 0을 빨강, 1을 초록, 2를 파랑으로 칠할 때의 인덱스라 할 때, i번째 집의 색칠 비용은 각각 빨강: rgb[i][0], 파랑: rgb[i][1], 초록: rgb[i][2] 으로 나..

9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 기초적인 dp문제로 타뷸레이션과 메모제이션, 두 가지 방식으로 풀어보려 합니다. 값에 따른 방법의 수를 나타내면 다음과 같습니다. index 0 1 2 3 4 5 방법의 수 0 1 2 4 7 13 index와 n번째 값을 일치시키기 위해 0번 인덱스를 추가로 사용하였습니다. 점화식은 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]으로 i번째 값 이전의 3개의 값을 더하여 구할 수 있습니다. 1. 타뷸레이션 dp = [0, 1, 2, 4] + [None] * 7 ns = [] for _ in range(int(input())): ns.app..

1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 풀이 dp의 타뷸레이션 방식으로 문제를 풀어보려 합니다. N을 입력받은 후 N+1 크기의 배열(dp)을 만들어 i번째 인덱스에 i번째 숫자의 최소 연산 수를 저장하려 합니다. index 0 1 2 3 4 5 6 7 8 연산수 0 0 1 1 2 3 2 3 3 배열의 index와 i번째 수를 동일하게 하기 위해 0번 index를 추가하였습니다. ① 1, 2번 연산은 모든 수에서 적용하지 못하지만 3번 연산은 모든 수에 적용할 수 있기 때문에 우선적으로 3번 연산을 적용합니다. - dp[n+1] = dp[n] + 1 ② n이 3의 약수라면 n+1번째 수에 저장된 연산수와 n/..

1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 N번째 피보나치 수를 구하는 함수는 다음과 같다 int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); } } 피보나치 함수를 호출했을 때, 0과 1이 몇 번 출력되는지 구하는 프로그램을 작성해야 한다. 입력 - 첫째 줄에 테스트 케이스의 개수 T - 각 테스트 케이스는 한 줄로 입력 - N은 0 또는 40보다 작은 자연수 출력 각 테스트..