🗒️ dynamic programming (3)

1. 2022.06.29 [Python] 동적 계획법(DP: Dynamic Programming)

   동적 계획법(DP: Dynamic Programming) 동적 계획법(DP: Dynamic Programming) 불필요한 연산을 줄이고, 최적의 답안을 구하는 알고리즘 동적 계획법의 등장 배경 ① 배낭 문제(Knapsack Problem) 무게와 가격이 다른 여러 물건 중에서, 가장 효율적으로 배낭에 채우기 위한 문제 예) 배낭에 넣을 수 있는 무게는 한정 되어 있고, 배낭에 넣을 수 있는 보석의 무게와 가치가 각각 다를 때 어떻게 해야 가방에 가장 큰 이익이 담길 수 있도록 보석을 채울 수 있을까? ② 브루트 포스 검색(Brute Force Search) 모든 경우의 수를 나열한 후, 그중에서 최선의 해결책을 찾는 방법 '짐승(Brute)처럼 무식한 힘(Force)으로 전체 경우의 수를 검색한다.'는..
2. 2021.07.22 부분집합의 합 문제(Subset Sum Problem)

   부분집합의 합 문제(Subset Sum Problem) 부분집합의 합 문제를 한 문장으로 표현하면 다음과 같음. 음수가 아닌 정수로 이루어진 집합 S와 임의의 정수 x가 주어질 때, S의 부분집합 중에서 그 원소의 합이 x와 같은 부분집합이 존재하는가? 부분집합의 합 문제의 예 S = { 13, 79, 45, 29 } x = 42 → True (13 + 29) x = 25 → False 집합 S가 S = { 13, 79, 45, 29 } 형태로 주어질 경우, S로부터 다음과 같은 16개의 부분집합을 추출할 수 있음. { } { 13 } { 79 } { 45 } { 29 } { 13, 79 } { 13, 45 } { 13, 29 } { 79, 45 } { 79, 29 } { 45, 29 } { 13, 79..
3. 2021.07.22 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)

   플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) 모든 쌍 최단 경로(All-Pairs Shortest Path)를 구하는 알고리즘 O(V³)의 시간 복잡도와 O(V²)의 메모리 사용량으로 동작하는 상향식 알고리즘 벨만-포드 알고리즘 그래프의 두 정점 사이의 최단 경로가 출발 정점에서 시작하는 다른 최단 경로와 최종 목표 정점으로 연결된 에지의 조합으로 구성됨. 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) 은 이러한 개념에 좀 더 광범위한 일반화를 적용함으로써 큰 효과를 얻음. 정점 A와 정점 B 사이의 최단 거리가 AB이고, 정점 B와 정점 C 사이의 최단 거리가 BC이면, 정점 A와 정점 C 사이의 최단 거리는 AB + BC 임. 이 논리는 그 자체로 획기..