백준 썸네일형 리스트형 [python] 백준 1182번 부분수열의 합 https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 💻 코드 import sys from itertools import combinations input = sys.stdin.readline n, s = map(int, input().split()) number = list(map(int, input().split())) count = 0 for i in range(1, n + 1): result = list(c.. 더보기 [python] 백준 14501번 퇴사 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 💻 코드 import sys input = sys.stdin.readline n = int(input()) t_list = [] p_list = [] dp = [0] * (n + 1) for _ in range(n): t, p = map(int, input().split()) t_list.append(t) p_list.append(p) for i in range(n - 1, - 1, -1): if t_list[i] + i > n: dp[i] = dp[i + 1] else: dp[i] = max(p_list[i] + dp[i + t_l.. 더보기 [python] 백준 2309번 일곱 난쟁이 https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 💻 코드 import sys input = sys.stdin.readline dwarf = [int(input()) for _ in range(9)] temp1, temp2 = 0, 0 for i in range(9): for j in range(i + 1, 9): if sum(dwarf) - (dwarf[i] + dwarf[j]) == 100: temp1 = dwarf[i] temp2 = dwarf[j].. 더보기 [python] 백준 17087번 숨바꼭질 6 https://www.acmicpc.net/problem/17087 17087번: 숨바꼭질 6 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이 www.acmicpc.net 💻 코드 import sys import math input = sys.stdin.readline a = [] result = [] n, s = map(int, input().split()) a = list(map(int, input().split())) for i in range(n): result.append(abs(s - a[i])) print(math.gcd.. 더보기 [python] 백준 9095번 1, 2, 3 더하기 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 💻 코드 import sys input = sys.stdin.readline T = int(input()) d = [0] * 100 d[1] = 1 d[2] = 2 d[3] = 4 for _ in range(T): n = int(input()) for i in range(4, n + 1): d[i] = d[i - 1] + d[i - 2] + d[i - 3] print(d[n]) 📝 풀이 저번에 풀었던 2 X n 타일링 문제와 거의 같다. 푸는 방법은 똑같았고 점화식만 아주 살짝 바꿔주면 된다. .. 더보기 다이나믹 프로그래밍 Dynamic Programming 다이나믹 프로그래밍이란? 메모리를 적절히 사용하여 수행 시간 호율성을 비약적으로 향상시키는 방법 이미 계산된 결과를 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 다이나믹 프로그래밍의 조건 1. 최적 부분 구조 (Optimal Substructure) : 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 구조 2. 중복되는 부분 문제 (Overlapping Subproblem) : 동일한 작은 문제를 반복적으로 해결할 수 있는 문제 다이나믹 프로그래밍 구현 방식 TopDown(탑다운) & BottomUp(보텀업) TopDown(탑다운, 하향식) 큰 문제를 해결하기 위해서 작은 문제들을 재귀적으로 호출하여 작은 문제가 모두 해결되었을 때 큰 문제의 답까.. 더보기 [python] 백준 2609번 최대공약수와 최소공배수 문제 풀이 https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 문제 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000 이하의 자연수이며 사이에 한 칸의 공백이 주어진다. 출력 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. 💻 코드 방법 1) 단순 수식 num1, num2 = map(int, input().split()) def GCD(x, y): for .. 더보기 [python] 백준 9012번 괄호 문제 풀이 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 문제 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’와 ‘)’ 만으로 구성되어 있는 문자열이다. 그중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로.. 더보기 이전 1 2 다음
