Algorithm5 0-1 knapsack problem 가방에 최대 무게가 있고 그 무게 안에 물건을 넣는데 물건의 가치가 최대로 넣는 경우를 구하는 문제. Brute force로 문제를 풀면 모든 가능한 부분집합의 경우를 비교해보면 되므로 2의 n번을 비교해보게 된다. 예를 들어 보석1, 2, 3, 4 가 있고 각각의 무게와 가치가 있을 때 0부터 최대 가방무게 n까지 열의 속성으로 두고 0부터 최대 보석 가지수를 4개까지 행이 속성으로 두어서 보석 가지 수⑊가방 무게 0 1 2 .. n 0 0 0 0 0 1 0 2 0 3 0 4 0 이런 식으로 테이블이 만들어진다 생각하고 이해해보면 쉽다. 처음에 이 문제를 이해하려고 했을 때 많이 애를 먹었던 부분이 왜 보석을 여러개를 안넣고 1개만 넣는거지??였다. 예를들어 보석1의 무게가 1이면 가방 무게가 2이므로.. 2021. 6. 9. 다익스트라 알고리즘 Dijkstra's algorithm 일정 시간 복잡도 다익스트라 알고리즘은 시작 정점이 정해져있다. 정점을 선택해가며 진행하고 각 정점까지 총 가중치를 합한 값을 저장하고 비교해 나간다. 앞서 살펴본 프림 알고리즘의 일정 시간 복잡도와 유사하다. T(n) = 2(n-1)(n-1)로 모든 정점을 방문하기 위해서는 시작 정점을 제외하고 n-1개의 정점을 방문해야한다. 그러므로 repeat n-1번을 해준다 (가장 바깥쪽 반복문) 이 repeat내부에서는 각 정점까지 현재 진행상태에서의 최단거리를 비교하고 (n-1번) 이동할 정점을 고른 후에는 다시 각 정점까지의 거리를 업데이트한다 (n-1번) 그렇기 때문에 (n-1 + n-1)(n-1) = 2(n-1)(n-1)이 되는 것이다. 의사 코드를 보면 다음과 같다. void dijkstra(int n, const n.. 2021. 6. 9. 프림 알고리즘 Prim's Algorithm 일정 시간 복잡도 MST(minimum spanning tree)구하는 알고리즘 정점 선택 기반으로 가중치 제일 낮은 방향으로 이전 단계의 신장트리를 확장해나간다. 트리가 N-1개의 간선을 가질 때까지 반복한다. 의사 코드를 보면 다음과 같다. void prim(int n, const numberW[][], set_of_edges& F) //정점 개수, 간선 정보, 방문 간선 { index i, vnear; number min; edge e; index nearest[2..n]; //해당 인덱스의 정점에서 가장 가까운 정점 정보 number distance[2..n]; //현재 방문한 정점에서 해당 인덱스의 정점까지 거리(최단) F = ∅; for(i = 2; i 2021. 6. 8. [알고리즘] 퀵 정렬 | Quick Sort | C++코드 해석 병합정렬(Merge Sort)과 함께 기본 정렬알고리즘인 퀵정렬. 병합정렬이 수열을 반으로 쪼개가며 정렬했다면, 퀵정렬은 기준을 두고 기준보다 작은값들, 기준보다 큰값들로 쪼개가며 정렬한다. 병합정렬은 따로 정렬해둔 값을 저장해둘 메모리공간이 필요했다면 퀵정렬은 따로 메모리공간이 필요하지 않다. 하지만 병합정렬은 언제나 시간복잡도가 일정한 반면 퀵정렬은 잡히는 기준에 따라 시간복잡도가 O(n^2)까지 올라갈수있다고한다. 코드는 이러하다. pivot이 기준 값이 되고 i가 pivot의 자리를 찾아준 다고 생각하면된다. 이해하기 쉽게 예시를들어 그림으로 설명해보자면 이런식이다. 2020. 2. 20. [알고리즘] 병합정렬 알고리즘 | Merge Sort | C++코드 해석 분할정복(Divide and Conquer) 알고리즘을 공부하고있습니다. 병합정렬을 이해해보겠습니다, 우선은 코드는 이렇게 생겼습니다 코드를 이해하기 쉽도록 병합정렬의 개념과 예시그림을 설명하겠습니다! 병합정렬은 분할과 정렬로 나눌수있습니다. 먼저 처음과 끝의 중간에서 두 개로 분할합니다. 이후 분할된 블록들을 계속해서 최소단위까지 분할해줍니다. 8개의 수열을 분할하는 과정을 예로 들면, 이런 식이 됩니다. 코드를 보면 이에 재귀함수를 이용하였는데요, 빨간색 숫자는 재귀함수에 따라 분할이 되는 순서입니다. 재귀함수가 머리아프신분들은 저 순서를 보시면 직관적으로 바로 이해가 되실 거에요! 분할이 끝났으면 5번에서 정렬&병합 한번, 8번에서 한번, 8번 병합이끝나고 6번에 돌아와서 한번, 6번에서 끝나고 2.. 2020. 2. 20. 이전 1 다음
