Algorithm/Memo

재귀함수로 만드는 합

#include using namespace std; int sum(int i); int main() { cout 2 + 1 -> 3 + 3 -> 4 + 6 -> 5 + 10 -> 6 + 15 ..... 결국 10 + 45를 만나면서 최종 수를 반환한다. 출력 55 팩토리얼을 구하는 재귀함수 int factorial(int x) { if (x == 0) { return 1; } return x * factorial(x - 1); } return쪽의 factorial함수내로 진입한다. 0에 도달하면 하나씩 리턴하며 돌아온다. 0 : 1 1 : 1 * 1 2 : 2 * 1 3 : 3 * 2 4 : 4 * 3 ........ 이런식으로 돌아오게된다.

다익스트라 알고리즘

1. 시작한 곳을 dist를 0으로 잡고 시작. 거리비용들의초기값은 INF로 한다. 2. 우선순위 큐를 사용하여 거리비용이 낮은 순으로 탐색 3. 조건은 현재노드에 있는 다음 노드들, 즉 붙어 있는 노드들을 탐색 4. 그 노드들에 대해서 dist보다 현재 노드와 붙어 있는 노드로 가는 거리비용을 합한 값이 작을 경우 값을 적는다. 5. 다음 우선순위 큐가 없을 때까지 반복하면 모든 곳을 최소비용으로 순회하게 된다. 6. 시작지점부터 도착지점까지 최소 비용을 구하는 문제에 사용. 도움 사이트 : yabmoons.tistory.com/364 [ 다익스트라 알고리즘 ] 개념과 구현방법 (C++) 그래프 알고리즘에서 '최소 비용'을 구해야 하는 경우 사용할 수 있는 대표적인 알고리즘으로는 '다익스트라 알고리즘'..

너비 우선 탐색 BFS

bool BFS(int cost) { queue q; q.push(start); visited[start] = true; while (!q.empty()) { int currNode = q.front();//현재 너비에 있는 것을 순차적으로 검색 q.pop();//검색한 곳은 삭제 if (currNode == finish) return true; for (int i = 0; i 4 2 -> 3, 2 -> 5 3 -> 6, 5 -> 6 ..

깊이 우선 탐색_DFS

#include #include #include #include using namespace std; const int N = 6; vector number[N]; bool visited[N]{false}; void DFS(int curr); int main() { ios::sync_with_stdio(false); //무방향 리스트 number[1].push_back(2); number[1].push_back(4); number[2].push_back(1); number[2].push_back(3); number[2].push_back(5); number[3].push_back(2); number[3].push_back(5); number[4].push_back(1); number[5].push_bac..

힙

Heap이란 완전이진트리의 일종으로 부모 노드와 자식 노드간에 항상 대소관계가 성립하는 자료구조. - 완전이진트리를 배열로 구성하면 현재노드 current에서 부모 노드를 알고 싶을때 current/2를 하면 알수있다. 1 2 3 4 5 6 7 4/2 = 2 5/2 = 2 6/2 = 3 7/2 = 3 도움글 더보기 https://twpower.github.io/137-heap-implementation-in-cpp