Koo's.Co

1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이 주어진 시간동안 최대한 많은 회의를 하려 합니다. 처음에 회의시간의 길이를 이용하려 했는데 굳이 회의시간의 길이를 확인하는 방법보다 회의가 끝나는 시간을 기준으로 회의들을 정렬한 후, 끝나는 시간에 맞춰 다음 회의 일정을 잡으면 최대한 많은 회의를 선택할 수 있었습니다. import sys read = sys.stdin.readline n = int(read()) res = 1 ts = [list(map(int, read().split())) for _ in range(n)] ts.sort(key=lambda x: (x[1], x[0])) prev = ts[0][1] fo..

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보다 작은 자연수 출력 각 테스트..

15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안 되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 풀이 - 결과를 ..