recursion
-
LCS(최장 공통 부분 수열 - longest common subsequence) 재귀적 방법 & 중복제거의 메모이제이션Algorithm with C/DFS 2020. 9. 27. 23:47
발췌 문헌 ko.wikipedia.org/wiki/%EC%B5%9C%EC%9E%A5_%EA%B3%B5%ED%86%B5_%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4 최장 공통 부분 수열 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 최장 공통 부분수열 문제는 LCS라고도 불린다. 이는 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제다.(종종 단 두 개중 하� ko.wikipedia.org LCS 문제는 최적의 부분구조를 가진다. 이 문제는 더 작은, "부분문제"로 쪼개질 수 있고, 이것은 반복해서 자명한 부분문제가 될 때까지 더 간단한 부분문제로 쪼개질 수 있다. LCS는 또한 겹치는 부분문제를 가진다. 더 높은 부분문제에 ..
-
Graph DFS with RecursionC 자료구조/Graph 2020. 7. 8. 00:39
내용 구현은 앞에서 만든 내용을 가지고 오자. 1. 개념 깊이 우선 탐색( DFS )은 미로를 탐색할 때, 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다. 깊이 우선 탐색은 그래프의 시작 정점에서 출발하여 먼저, 시작 정점StartVertex를 방문하고 방문하였다고 표시를 한다. StartVertex에 인접한 정점들 중에서 아직 방문 하지 않은 정점u가 있다면 u를 시작 정점으로 하여 깊이 우선 탐색을 다시 시작한다. 이 탐색이 끝나게 되면, 다시 StartVertex에 인접한 정점들 중에서 아직 방문이 안된 정점을 찾는다. 만약 없으면 종료하고, 있다면 다시 그 정점을 시작 정점..