Koo's.Co

python에서 제공하는 itertools를 사용하면 효율적으로 순열과 조합을 구할 수 있습니다. 1. 조합(combinations) 첫번째 파라미터로 iterable 객체를 받고, 두번째 파라미터는 선택할 원소의 개수를 입력받습니다. from itertools import combinations A = [2, 1, 3] for i in combinations(A, 2): print(i) for i in combinations(A, 3): print(i) 2. combinations_with_replacement 중복을 허용하여 입력받은 iterable 객체 내 원소로 만들 수 있는 모든 조합을 구할 수 있습니다. from itertools import combinations_with_replacemen..

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

전에 파이썬의 bisect 라이브러리의 bisect_left와 bisect_right을 다룬 적이 있었습니다. 그 때는 기본적인 함수의 동작방식과 사용방법에 대해서만 공부해봤는데 최근에 LIS 문제를 다시 풀어보면서 lower bound를 다시 공부할 기회가 생겼었습니다. 오늘은 직접 bisect_left, bisect_right를 구현해보려 합니다. 오늘 게시물을 보기 전에 아래 게시물에서 lower bound와 upper bound에 대해 읽어보고 오시길 추천드립니다. 간단하게 lower bound: target "이상(target 포함o)"이 처음 나오는 위치 upper bound: target"보다 큰(target 포함x)" 값이 처음 나오는 위 [Python] bisect 라이브러리 (lower..

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