목록Computer Science (228)
DHistory
문제 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 import sys n = int(sys.stdin.readline().rstrip()) numbers = [0] + list(map(int, sys.stdin.readline().rstrip().split()))[:n] def solution(a): d = [1] * (len(a)) for i in range(2, len(numbers)): for j in range(1, ..
문제 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 풀이 """ 00 타일 1 타일 N인 모든 2진 수열을 만들 수 없다. N = 1 => 1 N = 2 => 00, 11 N = 3 => 100, 001, 111 N = 4 => 0011, 0000, 1001, 1100, 1111 2xn 타일과 동일 0 => 2x1 1 => 1x2 """ n = int(input()) MOD = 15746 def solution(n): if n == 1: return 1 a = 1 b = 2 for i in range(3, n +..
문제 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 풀이 """ 이친수 1. 0으로 시작하지 않는다. 2. 이친수에서 1이 "두번 연속"으로 나타나지 않는다. N자일 때, 이친수의 개수는? d[n]: n자리일 때, 0으로 끝나는 이친수의 개수 => 0과 1로 2개씩 생김 a[n]: n자리일 때, 1로 끝나는 이친수의 개수 => 다음은 0으로 끝남 """ n = int(input()) def solution(n): d = [0] * (n + 1) a = [0] * (n + 1) a[1] = 1 fo..
문제 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 풀이 """ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12 5 = 4 0 6 = 5 1 7 = 6 2 8 = 7 3 9 = 8 4 10 = 9 5 11 = 10 6 12 = 11 7 """ import sys t = int(sys.stdin.readline().rstrip()) def solution(n): if n
문제 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 """ 1. 계단을 한 계단 씩 또는 두 계단씩 오를 수 있다. 2. 연속된 세 개의 계단을 모두 밟아서는 안된다. 3. 마지막 도착 계단은 반드시 밟아야한다. d[n]: n번째 계단을 밟았을 때 최대 점수 OX | O OXO | O 1. 직전 계단을 밟지 않은 경우 d[i - 2] + a[i]이다. 2. 직전 계단을 밟은 경우 d[i - 1]이 아닌 d[i - 3]인 이유는 d[i - 1]에서 직전 계단을 밟았을 때, 최대 점수일 수 있기 때문이다. d[i - ..
문제 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 풀이 """ d[n] = 가로의 길이가 n일 때 타일을 채울 수 있는 방법의 수 타일의 크기는 1x2 / 2x1이 있다. d[1] = 1 d[2] = 2 # 2 x 1로 만들 수 있는 방법의 수 + 1 x 2로 만들 수 있는 방법의 수 d[i] = d[i - 1] + d[i - 2] """ n = int(input()) def solution(n): d = [0] * (n + 1) d[0] = 1 d[1] = 1 for i in range(2, n + 1): d[i] = (d[i..
문제 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 풀이 """ 0 1 1 2 3 5 8 f(0) = f(0) f(1) = f(1) = 1f(1) + 0f(0) f(2) = f(1) + f(0) = 1f(1) + 1f(0) f(3) = f(2) + f(1) = 2(f1) + 1f(0) f(4) = f(3) + f(2) = 3f(1) + 2f(0) f(5) = f(4) + f(3) = 5f(1) + 3f(0) f(6) = f(5) + f(4) = 8f(1) + 5f(0) => 0과 1의 개수가 피보나치 수열을 이룬다. """ import sys t = int(sys.stdin.readline().rstri..
문제 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 """ 1. X가 3으로 나누어 떨어지면, 3으로 나눈다. 2. X가 2로 나누어 떨어지면, 2로 나눈다. 3. 1을 뺀다. 연산을 사용하는 횟수의 최솟값을 출력 d[n]: n을 만들기 위한 연산의 최솟값 """ n = int(input()) def solution(n): d = [10 ** 6 + 1] * (n + 1) d[0] = d[1] = 0 for i in range(1, n + 1): if not i % 2: d[i] = min(d[i], d[i // 2] + 1) if not i % 3: d[i] = min(d[i], d[i // 3] + 1) d[i]..
문제 15624번: 피보나치 수 7 첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 """ 0번째 0 1번째 1 2번째부터는 바로 앞 두 피보나치 수의 합 """ import sys n = int(sys.stdin.readline().rstrip()) def solution(n): a, b = 0, 1 for i in range(2, n + 1): if not i % 2: # 미리 나누어서 저장해야한다. # 큰 숫자가 되면 비트를 많이 사용하기 때문에 연산 속도가 오래걸린다. a = (a + b) % 1000000007 else: b = (a + b) % 1000000007 return a if not n % 2 else b prin..
문제 2491번: 수열 0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾 www.acmicpc.net 풀이 """ d[n]: n일 때, 가장 긴 구간이 되는 길이 """ import sys n = int(sys.stdin.readline().rstrip()) numbers = list(map(int, sys.stdin.readline().rstrip().split()))[:n] def solution(numbers): # 가장 긴 구간이 되는 길이의 최솟값은 1이다. d1 = [1] * len(numbers) d2 = [1] * len(numbers) for ..