Problem Solving/BOJ

목차1. 문제 설명2. 정답     1. 문제 설명https://www.acmicpc.net/problem/12865   정말 말그대로 평범한 배낭 알고리즘 문제로, 점화식을 도출하는 방법을 정리해보려고 한다.배낭 알고리즘은 전형적인 dp문제다. 결국에 배낭에 물건을 담냐, 담지 않느냐로 쪼갤 수 있기 때문이다.     먼저 dp 배열을 정의해보자. dp[i][w]i번째까지의 물건을 고려했을 때무게 w를 버틸 수 있는 배낭의 최대 가치 물건을 선택할 때에는 두 가지 선택지가 있다. 1. 현재 물건의 무게가 배낭에 담을 수 있는 최대 무게를 초과 첫 번째 물건의 무게는 8kg로 배낭에 최대로 담을 수 있는 무게인 7kg를 초과한다.이 경우, 배낭에 물건을 담을 수 없다.따라서 이전 상태의 값을 그대로 가져..

목차1. 문제 설명2. 정답     1. 문제 설명https://www.acmicpc.net/problem/2146 지도가 주어질 때 가장 짧은 다리를 하나 놓아 두 대륙을 연결하는 방법을 찾는 문제다.  바다 = 0육지 = 1위의 그림과 같이 지도가 주어지면 회색 영역의 섬을 dfs로 구한다.바다와 육지가 각각 0, 1의 값을 사용하기 때문에 각각의 섬에 2부터 번호를 부여한다. 즉 dfs로 모든 영역을 순회했을 때 각각의 섬은 오른쪽 사진과 같은 번호를 부여받는다.  두 대륙을 연결하는 가장 짧은 다리는 (해안선과 근접한 육지) - (해안선과 근접한 육지)간의 최단 거리와 같다. Q. 최단 거리를 구해야한다면?A. bfs를 써야 한다는 뜻이다!   그렇다 이 문제는 dfs + bfs 짬뽕인 것이다....