조준장 개발자 생존기

문제 11720번: 숫자의 합 첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다. www.acmicpc.net 알고리즘 - 정수형을 리스트로 받는다. - 받은 리스트의 합을 출력한다. 코드 import sys n = int(sys.stdin.readline()) m = list(map(int, sys.stdin.readline().strip())) # 정수형을 리스트로 받는다. print(sum(m)) github GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법 내가 푼 코딩 테스트 문제와 해결법. Contribute to junjange/CodingTest development by creating an a..

문제 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 알고리즘 - 리스트를 거꾸로 변환해 가장 큰 증가하는 부분 수열의 길이를 구하는 방법으로 바꾸어 문제를 수행한다. - 반복문을 통해 수열이 증가하는지 확인하고 i번의 수와 이전수를 비교한다. - 두 수를 비교하고 현재 수가 더 크다면 증가하는 부분 수열의 길이를 구한다. - 현재 증가한 부분수열보다 비교하고 있는 길이가 크다면 현재 증가한 부분 수열을 비교하고 있는 길이로 초기화한다...

문제 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 알고리즘 - 반복문을 통해 각 인덱스 위치에 가장 큰 증가 부분 수열의 합을 구한다. - 반복문과 조건문을 통해 현재 인덱스 값과 이전 인덱스 값을 비교한다. - 현재 인덱스 값이 이전 인덱스 값보다 크다면 현재 인덱스 위치에 가장 큰 부분 수열의 합과 이전 인덱스 위치에 가장 큰 부분 수열의 합 + 현재 수를 비교한다. - 이전 인덱스 값이 더 크다면 현재 인덱스 위치에 가장 큰 부분 수열의 합과 ..

문제 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 알고리즘 - 반복문을 통해 코인을 확인한다. - 반복문을 통해 코인으로 1원부터 k원까지 만들 수 있는 경우의 수를 확인한다. - k원을 만드는 과정으로는 현재 코인 - 현재 확인 중인 수(j)의 값을 dp[j]에 더하는 방식이다. ex) 현재 코인: 1, 2, 5일 때 index 현재 코인 : 1 현재 코인 : 2 현재 코인 : 5 1 1 0 0 2 11 dp[0] + dp[2] 0 3 111 dp[1] + dp[3] 0 4 1111 dp[2] + dp[4..

문제 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 알고리즘 - 각 자연수를 만드는 제곱수에 최대 항의 개수를 dp에 저장한다. - 이중 반복문을 통해 각 자연수를 만드는 제곱수에 항의 개수를 구한다. - 각 자연수가 제곱수보다 작다면 제곱수로 항의 개수를 만들지 못하므로 반복을 멈춘다. - 각 자연수를 만다는 제곱수에 최소 항의 개수를 구한다. 코드 pypy3 해결 # pypy3 (통과) # python3 (시간초과) import sys n = int(sys.stdi..

문제 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 알고리즘 - 문제를 읽어보면 결국 돌을 1개를 계속해서 가져가든 3개를 계속해서 가져가든 두 개를 혼합하여 가져 가든 승자는 한 명인 것을 알 수 있다. - 상근이가 먼저 시작한 후 남은 돌의 개수가 짝수이면 창영이에 승이고 홀수이면 상근이에 승이다. 코드 import sys n = int(sys.stdin.readline()) # 상근이가 먼저 시작한 후 # 남은 돌의 개수가 짝수면 창영 승, 홀수면 상근 승 if (n - 1) % 2: print("CY") else: print("SK") github GitHub - junjange/CodingTest: 내가 푼 코딩 테스트..

문제 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net 알고리즘 - 반복문을 통해 점화식을 수행한다. - A의 개수는 이전 화면에 B의 개수 - B의 개수는 이전 화면에 A의 개수와 B의 개수 index 화면 A의 개수 B의 개수 1 B 0 1 2 BA 1 1 3 BAB 1 2 4 BABBA 2 3 5 BABBABAB 3 5 6 BABBABABBABBA 5 8 7 BABBABABBABBABABBABAB 8 13 코드 import sys k = int(sys.stdin.readline()) dp = [[0 for _..

문제 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 알고리즘 - 중복 조합을 통해 문제를 수행한다. - nHr = n+r-1 C r 코드 import sys r = int(sys.stdin.readline()) # 중복 조합을 통해 문제를 수행한다. nHr = n+r-1 C r n = 10 + r - 1 a = n # n+r-1 b = r # r # aCb 구현 for i in range(1, r): a *= n - i # n x (n - i) .. x (n - r + 1)..

문제 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 알고리즘 - 반복문을 통해 각 스티커 인덱스의 최댓값을 구한다. - 카드의 크기가 2일 때인 즉, 인덱스가 1일 때 최댓값은 이전 대각선의 스티커 점수의 합이다. - 인덱스가 1보다 클 경우에는 두칸 전에 스티커 값과 이전 스티커 값 중에서 큰 값과 현재 스티커의 값을 더한 값이 최댓값이 된다. - 표를 통해 확인하면 더 쉽게 이해할 수 있다. 예제 입력 1) index 0 1 2 3 4 0 50 10 + 30 = 40 max(100, 30) +..

문제 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 알고리즘 - dp를 통해 타일이 n개일 때의 규칙을 찾아 점화식을 도출해 낸다. - 점화식 : f(n) = f(n - 1) + f(n - 2) - 반복문을 통해 점화식을 표현한다. 코드 import sys n = int(sys.stdin.readline()) dp = [0] * 1000001 dp[1] = 1 # 1 dp[2] = 2 # 00, 11 dp[3] = 3 # 100, 001, 111, # dp[4] = 5 # 0011, 1100, 1001, 0000..