화요밍의 개발로그

동적 프로그래밍(동적 계획법, Dynamic Programming)은 하나의 문제를 풀기 위해서 해당 문제를 여러 개의 Subproblem으로 나누어 푸는 방식이고, Subproblem은 반복되며 답은 항상 같은 특성을 이용하여 Memoization을 통해 최종적으로 문제를 해결하는 것을 말한다. 설명 간략하게 정리된 위의 문장을 쪼개서 설명하면 다음과 같다. 1. 하나의 문제를 풀기 위해서 해당 문제를 여러 개의 Subproblem으로 나누어 푸는 방식이다. 하나의 문제를 풀기 위해서는 그보다 더 작은 Subproblem으로, 그리고 해당 subproblem에서 그보다 더 작은 Subproblem을 더이상 나눌 수 없을 때까지 나누어 작은 Subproblem의 결과 값으로 부터 최종 답을 구할 수 있는..

Summary BFS와 DFS는 그래프의 모든 정점을 탐색하는(그래프의 순회) 완전 탐색 알고리즘이다. BFS는 Breadth-First Search로 너비 우선 탐색을 의미하고 자료구조는 Queue를 사용한다. DFS는 Depth-First Search로 깊이 우선 탐색을 의미하고 자료구조는 Stack을 사용한다. 설명 쉽게 설명하기 위해서 아래와 같은 그래프가 있다고 가정해보자. (만약, Queue와 Stack에 대해 잘 모른다면 먼저 아래 참고를 통해 공부하고 돌아오자!) 그래프의 모든 노드를 BFS와 DFS 방법으로 탐색하여 탐색 순서가 어떻게 되는지 살펴보며 공부해보자. - BFS (Breadth-First Search, 너비 우선 탐색) BFS는 방문 노드와 가장 가깝게 인접한 노드들을 먼저 ..