조준장 개발자 생존기

문제 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 알고리즘 - 이중 반복문을 통해 n번의 수까지 증가하는 길이를 구한다. - 길이를 구할 때 i번의 수와 그전에 수들을 비교한다. - n의 최대 값이 1000보다 작거나 같기 때문에 시간 복잡도는 O(N^2)으로 수행할 수 있다. 코드 import sys n = int(sys.stdin.readline()) a = list(map(int, sys.stdin.readline().spl..

문제 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 알고리즘 - 점화식을 통해 0과 1의 호출 횟수를 구한다. - 테스트 케이스만큰 반복하여 답을 구한다. 코드 import sys t = int(sys.stdin.readline()) dp = [1] * 42 dp[0] = 0 # 피보나치 수 0일때, 0 dp[1] = 1 # 피보나치 수 1일때, 1 # 점화식을 통해 0과 1의 호출 횟수를 구한다. for i in range(2, 41): dp[i] = dp[i - 2] + dp[i - 1] # 테스트 케이스만큼 반복하여 답을 구한다. for _ in range(t): n = int(sys.stdin.r..

문제 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 알고리즘 - dp를 통해 계단의 점수를 리스트로 표현한다. - 연속으로 세 개의 계단을 밟는 경우와 두 계단을 한 번에 오르는 경우를 비교하여 dp 리스트의 계단의 점수를 넣는다. 코드 import sys n = int(sys.stdin.readline()) m = [0] * 301 for k in range(n): m[k] = int(sys.stdin.readline()) dp = [0] * 301 # 계단 dp[0] = m[0] # 첫 번째 계단 dp[1] = m[..

문제 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 알고리즘 - 점화식을 통해 코드를 도출해 낸다. 코드 import sys n = int(sys.stdin.readline()) dp = [0] * (n + 1) dp[0] = 0 # 0번째 피보나치 수 : 0 dp[1] = 1 # 1번째 피보나치 수 : 1 # 반복문을 통해 n번째 피보나치 수를 구한다. for i in range(2, n + 1): dp[i] = dp[i - 2] + dp[i - 1] print(dp[n..

문제 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 알고리즘 - 점화식을 구해보면 n = 1일 때, 1이고 n = 2일 때, 2이고 n = 3일 때, 3이고 n = 4일 때, 5이고 n = 5일 때, 8인 것을 확인할 수 있다. (dp[n] = dp[n - 1] + dp[n - 2]) - n이 3보다 작거나 같을 때 직사격형을 채우는 방법의 수가 n개 이므로 n을 출력한다. - 그 외인 경우에는 점화식을 통해서 문제를 수행한다. 코드 import sys sys.setrecursionlimit(10 ** 6) # 점화식 : n = ..

문제 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 알고리즘 - 1, 2, 3을 통해 만들 수 있는 경우의 수를 찾는 것이기 때문에 1, 2, 3의 경우의 수를 구하고 그것을 재귀 함수를 통해 입력받은 수를 만들 수 있는 경우의 수를 찾는다. - 피보나치 수 0번째는 0이기 때문에 0을 리턴 - 피보나치 수 1번째는 1이기 때문에 1을 리턴 - 그 외 2보다 크거나 같은 피보나치 수는 앞 피보나치 수의 합이므로 재귀 호출을 통해 구해서 합을 구한다. 코드 import s..

문제 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 알고리즘 - 1, 2, 3을 통해 만들 수 있는 경우의 수를 찾는 것이기 때문에 1, 2, 3의 경우의 수를 구하고 그것을 재귀 함수를 통해 입력받은 수를 만들 수 있는 경우의 수를 찾는다. 코드 import sys # 점화식 : (n > 3), f(n) = f(n - 1) + f(n - 2) + f(n - 3) def dp(v): # 1을 만들 수 있는 경우의 수 : 1 if v == 1: return 1 # 2을 만들 수 있는 경우의 수 : 2 elif v == 2: return 2 # 3을 만들 수 있는 경우의 수 : 4 elif v == 3: re..

문제 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 알고리즘 - dp를 통해 문제를 수행한다. - 1부터 n까지 반복하여 각 수의 최소 연산 횟수를 구한다. - 반복문에서 2 부터 n + 1까지 반복한 이유는 1이 되기 위한 연산 횟수는 필요없기 때문이다. - 1을 빼주는 연산은 현재 연산 횟수를 이전까지에 연산 횟수에서 + 1 해준 연산 횟수로 초기화 해줘 확인한다. - 현재 3으로 나눠진다면 현재 수를 구하기 위한 연산 횟수와 3으로 나눈 값의 연산 횟수에서 + 1해준 값과 비교하여 작은 값을 현재 연산 횟수로 초기화한다. - 현재 수가 2로 나눠진다면 현재 수를 구하기 위한 연산 횟수와 2로 나눈 값의 연산 횟수에서..

문제 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 알고리즘 - 물건의 수에 따라 가방에 물건을 얼마나 담을 수 있는지 확인한다. - 반복문을 통해 각 물건의 무게와 가치를 확인하고 가방에 담을 수 있는 물건의 최대 가치를 각각 구한다. - 현재 비교하고 있는 가방의 최대 무게가 현재 물건의 무게보다 작다면 이전에 비교했던 가방의 무게에 담겨져 있는 가치가 최대 가치가 된다. - 현재 비교하고 있는 가방의 최대 무게가 비교하고 있는 물건의 무게..

문제 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 알고리즘 - bfs 탐색을 통해 문제를 수행한다. - 모든 칸에 가중치를 -1로 초기화한다. - 시작 칸에 가중치를 0으로 초기화한 후 모든 구역을 탐색할 때 벽을 만나게 되면 가중치에 +1을 해준다. - 빈 곳을 이동할 때는 현재 가중치를 이전에 가중치로 초기화한다. - 큐에 다음 탐색할 좌표를 추가할 때는 벽을 부시지 않고 이동한 좌표부터 먼저 탐색할 수 있게 한다. 코드 import sys from collections impor..