조준장 개발자 생존기

문제 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 알고리즘 - 반복문을 통해 입력받은 리스트에 각 인덱스의 최댓값을 구한다. - 구하는 방법으로는 이전 수들의 합이랑 현재 인덱스의 수를 더한 값과 현재 인덱스의 수 중 큰 값을 현재 인덱스의 수에 추가하는 방식으로 수행한다. 코드 import sys n = int(sys.stdin.readline()) m = list(map(int, sys.stdin.readline().split())) dp = [m[0]] # 0번째 인덱스의 수를 미리 리스트 안에 넣는다. # 반..

문제 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 알고리즘 - 반복문을 통해 각 층의 수에 가중치를 더해준다. - 각 층의 왼쪽 줄이라면 이전 층의 왼쪽 줄에 가중치를 더한다. - 각 층의 오른쪽 줄이라면 이전 층의 오른쪽 줄에 가중치를 더한다. - 각 층의 중간 줄이라면 이전 층의 왼쪽 줄에 가중치와 오른쪽 줄의 가중치 중 큰 값을 더한다. - 반복이 끝난 후 마지막 층에 최대 가중치 값을 출력한다. 코드 import sys n = int(sys.stdin.readline()) m = [list(map(int, sys.stdin.readline().split())) for _..

문제 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로 나눈 값의 연산 횟수에서..