5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net ** 문제 유형 그리디 ** 풀이 거스름 돈의 최소 개수 계산 가장 기초적인 탐욕 알고리즘 문제 유형으로, 단순히 '큰 화폐 단위' 순서대로 잔돈을 거슬러 주면 최적의 해를 구할 수 있음 changes = 1000 - int(input()) cnt = 0 for i in [500, 100, 50, 10, 5, 1]: cnt += changes // i changes %= i print(cnt)

11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net ** 문제 유형 동적 프로그래밍, LIS ** 풀이 가장 긴 증가하는 부분 수열(LIS) 문제는 전형적인 동적 프로그래밍 문제 수열의 크기가 N일 때, 기본적인 동적 프로그래밍 알고리즘으로 O(N^2)에 해결 가능 D[i] = array[i]를 마지막 원소로 가지는 부분 수열의 최대 길이 N = 6일 때, n = int(input()) array = list(map(int, input(..

12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net ** 문제 유형 동적 프로그래밍 ** 풀이 배낭 문제(Knapsack Problem)으로 알려져 있는, 전형적인 동적 프로그래밍 문제 물품의 수 = N, 배낭에 담을 수 있는 무게 = K 동적 프로그래밍을 이용하여 시간 복잡도 O(NK)로 문제 해결 가능 +) 핵심 아이디어 모든 무게에 대하여 최대 가치를 저장하기 D[i][j] = 배낭에 넣은 물품의 무게 합이 j일 때 얻을 수 있는 최대 가치 각..

1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net ** 문제 유형 동적 프로그래밍 ** 풀이 사용할 수 있는 타일의 종류는 2개: (1), (00) 두 가지 종류의 타일을 이용하여, N 길이의 수열을 만드는 모든 경우의 수를 계산 가장 전형적인 동적 프로그래밍 문제 N이 최대 1,000,000 이므로 시간 복잡도 O(N)으로 해결해야 함 +) 과정 N = 2일 때, 경우의 수는 2가지 -> (11), (00) N = 3일 때, 경우의 수는 3가지 N = 4일 때, 경우의 수는 5가지 동적 프로그래밍 문제를 풀기 위해..

max_value: result = [i] max_value = c elif c == max_value: result.append(i) max_value = c for e in result: print(e, end=" ")

1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net ** 문제 유형 DFS, BFS ** 풀이 연결 요소의 개수를 세는 문제 모든 정점에 대하여 DFS or BFS를 수행하고, 한번 방문한 정점은 다시 확인하지 않음 전체적으로 DFS or BFS를 수행한 총 횟수를 계산 DFS or BFS 응용 문제 중에서 출제 비중이 매우 높은 유형 중 하나임 DFS로 문제를 푸는 경우, sys 라이브러리의 setrecursionlimit() 함수 설정 필요 # 방법 1 import sys sys.setrecursionlimit(10000..