다이나믹 프로그래밍
-
백준 2096 내려가기Algorithm/BOJ 2021. 4. 20. 09:54
출처: www.acmicpc.net/problem/2096 분류: DP 접근방식 간단한 DP 문제였습니다. 1, 2, 3 각 열에서 가장 최선인 경우를 계속 선택해나가면 됩니다. 행마다 갱신하고 나면 그 이전은 생각할 필요가 없으므로 디피는 각 열을 저장할 행 하나만 있으면 됩니다 :) 저는 맨 밑에서부터 올라왔는데 위에서부터 내려가도 상관은 없을듯 하네요! 해결방법 let n = Int(readLine()!)! var num = [[Int]]() for _ in 0..
-
백준 1520 내리막 길Algorithm/BOJ 2021. 3. 30. 14:00
출처: www.acmicpc.net/problem/1520 분류: DP, DFS 접근방식 DFS 방식으로 원하는 칸에 도달하는 경로를 찾아나갈 수 있습니다. 대신 모든 경우를 탐색하면 시간제한에 걸리게 되므로 DP를 활용해야 합니다. 현재 칸에서 가능한 경우의 수는 이미 모두 탐색을 했기 때문에 방문한 칸을 다시 방문할 필요는 없고 저장된 방문 횟수만 가져옵니다. 구체적으로는 처음에 DP 배열에 -1을 넣어두고 방문하면 0으로 초기화하고 값을 더해줍니다. DP가 -1일 경우에만 탐색하고 아니면 DP의 값만 리턴합니다. 해결방법 typealias Point = (r: Int, c: Int) let rc = readLine()!.split(separator: " ").map { Int(String($0))!..
-
백준 12865 평범한 배낭Algorithm/BOJ 2021. 3. 30. 13:09
출처: www.acmicpc.net/problem/12865 분류: DP 접근방식 디피로 해결할 수 있는 문제였습니다. 디피는 상황에 따른 최대 값을 기록해놓고 더 최적인 경우를 비교하면서 업데이트 해나가는 메모제이션 방식입니다. 이 문제에서는 특정 무게에 최대 가치가 얼마인지 기록해놓으면 되겠네요. 테이블에는 현재까지 찾은 최적의 가치가 들어있다고 할 때, 현재 무게 4짜리의 물품으로 테이블의 무게 7 칸을 채우려고 한다면 최적은 테이블의 무게 3짜리 칸 가치 + 현재 물품의 가치 (무게 4) vs 테이블의 무게 7짜리 칸의 가치 로 생각해볼 수 있습니다. 이런식으로 물품들을 입력받을 때마다 테이블을 업데이트 해나가면됩니다. 물품마다 현재 무게부터 테이블의 끝까지를 업데이트를 해나가야 하는데 테이블을 ..