Dev_Diary

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 이 문제는 냅색 알고리즘이라고 불리는 알고리즘의 전형적인 문제입니다 간단하게 설명하자면 무게와 물체 두 축을 가진 2차원 memoization 이라고 할 수 있습니다. # 배낭문제 (냅색 알고리즘) def solution(N, K, objects): # 정렬 objects = sorted(objects, key=lambda x: (..

https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 기본 아이디어는 '무작위로 뽑아서 계산하지 말고 테이블 둘째 줄에 적혀있는 수로 이동하면 적어도 하나의 수는 첫째줄 집합에 포함된다' 입니다. 이런 아이디어를 갖고 어떻게 구현할지 생각해보니 단순히 DFS, 즉 스택을 이용하면 될 것 같다는 생각이 들었습니다. def solution(N, table): # 스택 리스트 stack_list = [] # 자신의 값을 가지면 미리 넣어두기 ..