Algorithm (6) 썸네일형 리스트형 [알고리즘] 프림(Prim) 알고리즘 💡프림(Prim) 알고리즘이란?프림(Prim) 알고리즘 특최소 신장 트리 알고리즘노드를 중심으로 간선 탐색배열로 구현할 경우 시간 복잡도 $O(n^2)$, 우선 순위 큐로 구현할 경우 시간 복잡도 $O(ElogN)$그리디 알고리즘알고리즘 과정임의의 노드를 선택해당 노드와 연결되어 있는 간선 중 가중치가 최소인 것을 MST에 추가MST에 포함된 모든 정점과 연결된 간선 중 가중치가 최소이고, 사이클을 형성하지 않는 것을 MST에 추가V-1개의 간선이 선택될 때까지 간선 선택을 반복과정 예시초기 상태2. 노드 1 선택노드 1과 연결된 세 개의 간선 우선 순위 큐 추가 우선 순위 큐 157 3. 큐에 포함된 간선 중 가장 작은 간선 선택 후 MST에 연결 노드 3 추가MST에 포함된 .. [알고리즘] 최소 신장 트리(Minimum Spanning Tree) 💡최소 신장 트리란?신장 트리(Spanning Tree)그래프의 모든 정점을 포함하는 최소 연결 부분 그래프트리의 특징정점의 개수 n 개인 신장 트리의 간선 개수는 n-1 개모든 정점이 연결사이클 없음임의의 두 정점을 선택했을 때, 그 사이 경로는 유일함예시위 그래프에 대한 아래 신장 트리 예시들최소 신장 트리(MST, Minimum Spanning Tree)신장 트리 중 간선 가중치 합이 최소인 신장 트리예시위 그래프에 대해 최소 신장 트리💡최소 신장 트리 알고리즘1. 크루스칼(Kruskal) 알고리즘그리디를 이용하여 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 방법간선을 중심으로 하는 알고리즘greedy하게 간선을 선택하는 방법과정간선 가중치를 기준으로 오름차순 정렬간선 리스트 중 작은.. [Algorithm] 최단 거리 알고리즘 - 다익스트라(dijkstra) 알고리즘 🔎 다익스트라(dijkstra) 알고리즘이란?다익스트라그래프의 한 정점에서 다른 모든 정점까지 최단 거리를 구하는 알고리즘이다.DP 문제: 최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문에 작은 문제가 큰 문제의 부분 집합이다.한계: 음의 간선을 포함할 수 없다. (음의 간선을 포함하는 최단 경로 탐색 알고리즘으로 ‘벨만-포드’ 가 있다.)알고리즘 구현 방식아직 방문하지 않은 정점 중 출발지에서 가장 가까운 정점 방문 → by PriorityQueue해당 정점을 거쳐 갈 수 있는 정점의 거리가 이전 기록 값 보다 작으면 갱신1. 초기 상태ABCDEFINFINFINFINFINFINF visit 배열ABCDEFfalsefalsefalsefalsefalsefalse 2. A 방문 후 주변 노드.. [알고리즘] 완전 탐색 문제 / 순열 / 구현 - 반복문, 재귀 완전 탐색 문제 말 그대로, 완전히 탐색 한다는 뜻. 모든 수를 다 고려해서 해를 찾는다. ( 예시 ) Baby-gin Game 설명 - 0~9 사이의 숫자 카드에서 임의의 카드 6장 뽑는다 - 연속 3장의 카드는 : run, 3장의 카드가 동일한 것은 : triplet 이라 한다 - 6장의 카드가 모두 run과 triplet으로 구성될 경우를 baby-gin 이라 한다. 예시 - 1 1 1 1 2 3 일 경우 1개의 triplet 과 1개의 run으로 구성되었으므로, baby-gin ( triplet : (1 1 1), run : (1 2 3) ) - 1 2 3 1 2 3 일 경우 2개의 run으로 구성되었으므로, baby-gin( run : (1 2 3) ) - 1 5 6 4 2 2 일 경우 1개의 .. [알고리즘] 재귀함수 반복과 재귀 - 반복과 재귀는 유사한 작업을 수행할 수 있음 - 반복은 일정 작업이 끝날 때 까지 수행 VS 재귀는 주어진 문제의 해를 구하기 위해 동일한 구조의 더 작은 문제로 쪼개가는 과정 재귀 함수 - 하나의 큰 문제를 더 작은 문제로 쪼개고 결과들을 결합 -> 함수로 구현 - 함수 내부에서 직, 간접적으로 자기 자신을 호출 - basis part 와 inductive part로 구성 basis part - 가장 작은 단위로, 일반적으로 마지막 값을 리턴함으로 재귀를 종결하는 역할로 이용 - ex) if(n==1) return; inductive part - 재귀를 이용하는 부분으로, 일반적으로 지금 수행하고 있는 나보다 더 작은 단위의 같은 구조 함수를 호출 - ex) else return n*f.. [알고리즘] chapter3. Growth of Function Asymptotic notation algorithm의 정확한 러닝타임을 결정할 때가 있지만, 대부분은 가치 없음 input의 사이즈에 따라 running time 얼마나 될 지를 in the limit의 관점에서 결정 low-order term 와 constant factors를 대강 생각해서 중요한 것에 초점을 두는 방식 Notations Theta f(n) = θ(g(n)) f(n) ≈ c g(n) BigOh f(n) = O(g(n)) f(n) ≤ c g(n) Omega f(n) = Ω(g(n)) f(n) ≥ c g(n) Little Oh f(n) = o(g(n)) f(n) c g(n) g(n)은 주로 n, n², log n.. 이전 1 다음
