문제 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 풀이 이전에 다루었던 11053 가장 긴 증가하는 부분 수열의 풀이에서 각 원소들만 추가해주면 된다. 이는 메모이제이션을 통해 수열의 값의 크기에 따라 앞의 수 중 작은수가 얼만큼 있는지 확인할 수 있기 때문이다. 코드 from sys import stdin if __name__ == '__main__': n = int(stdin.readline()) nums = list..
도커에 대해 알아보기 전에 기존의 LXC(Linux Container)와 달리 많은 사람들이 도커를 사용하게 되고, 지금도 컨테이너 기반의 시스템 구축에 애용되는지 알아보기 위해 배경지식을 알아보고자 한다. Container 컨테이너는 운영체제 수준의 가상화(Operating System level virtualization)을 통해 각 컨테이너 별로 독립적으로 실행될 수 있는 환경을 제공한다. 도커가 등장하기 전에는 LXC(Linux Container)가 유명하였다. 초기에 도커는 LXC를 런타임으로 사용하는 방식을 채택하였다. 시간이 지남에 따라, 업그레이드 하면서 LXC 없이도 동작할 수 있는 버전을 제공하였다. VM Ware와 Virtual Box는 컨테이너와 달리 Hypervisor를 통해 Ge..
문제 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 풀이 예시의 수열 10 20 10 30 20 50은 다음과 같이 가장 긴 증가하는 부분 수열을 찾을 수 있다. 앞의 수열에서 작은 수가 있는지 카운트하여, 각 값에 따라 증가하는 부분수열의 길이를 찾을 수 있다. 20 보다 작은 수가 있는가? 수열 10 20 10 30 20 50 카운트 1 2 1 1 1 1 10은 20 보다 작으므로 10의 카운트 값에서 + 1한 값을 20의..
문제 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제 풀이 자리 수의 증가에 따라 다음과 같은 경우의 수를 확인할 수 있다. 자리 수 1 2 3 4 5 1 10 101 1000 10000 100 1001 10001 1010 10010 10100 10101 즉, N에 따라 만족하는 이친수의 경우는 f(n) = f(n - 1) + f(n - 2)라는 것을 알 수 있다. 이를 코드로 구현하면 간단히 문제를 해결 할 수 있다. 코드 if __name__ == '__main__': n = int(inp..
문제 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 수의 길이가 1인 경우에는 1 - 9 까지의 계단수가 있으므로 경우의 수는 9개이다. 수의 길이가 2인 경우에는 다음과 같은 경우의 수들이 있다. 시작 수 1 2 3 4 5 6 7 8 9 10 21 32 43 54 65 76 87 98 23 34 45 56 67 78 89 표를 보면 시작하는 수가 1과 9를 제외하고는 시작 수가 가질 수는 경우의 수는 다음과 같이 코드로 나타낼 수 있다. cur = [ cur[1], cur[0] + cur[2], cur[1] + cur[3], cur[2] + cur[4], cur[3] + cur[5], cur[4] + cur[6..
문제 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제 풀이 카드 구매하기에서는 구매하고자 하는 카드를 최대값으로 구매하는 문제였다. 이와 달리 카드 구매하기 2는 가장 최소 값으로 카드를 구매할 경우에 발생하는 금액을 반환하는 문제이다. 카드 구매하기와 동일한 방법으로 풀며, 약간의 코드를 수정하면 이 문제도 쉽게 풀 수 있다. 코드 if __name__ == '__main__': N = int(input()) card = [0] + list(map(int, input().split())) memo = [0]..
문제 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제 풀이 이 문제를 효율적으로 풀기 위해서는 메모이제이션(Memoization)을 활용하여야 한다. 문제의 예제와 같이 1 5 6 7이 입력되는 경우 카드 3개 까지 구매할 수 있는 경우의 수는 다음과 같다. 카드 1개 구매 : 1개 들어있는 카드 팩 카드 2개 구매 : (1개 들어있는 카드 팩) * 2, 2개 들어있는 카드 팩 카드 3개 구매 : (1개 들어있는 카드 팩) * 3, 2개 들어 있는 카드 팩 + 1개 들어 있는 카드백, 3개 들어 있는 카드팩 즉 ..
1, 2, 3 더하기 시리즈 1, 2, 3 더하기 1, 2, 3 더하기 2 1, 2, 3 더하기 3 1, 2, 3 더하기 4 1, 2, 3 더하기 5 1, 2, 3 더하기 6 1, 2, 3 더하기 7 1, 2, 3 더하기 8 1, 2, 3 더하기 9 문제 9095번: 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 www.acmicpc.net 문제 풀이 이전에 풀었던, 11726 2xn 타일링, 11727 2xn 타일링 2과 같이 어떠한 경우의 수가 있는지 파악하는 것이 중요하다..
