컴퓨터 공학/알고리즘 (14) 썸네일형 리스트형 힙 Heap 개념,우선순위 큐를 이용한 구현 (python)과 성능 비교, 힙 정렬, 상향식 힙 생성, 응용 문제 1. 힙 Heap 내부 노드에 키를 저장하며 다음 두가지 속성을 만족하는 이진트리 힙순서 (heap-order) : 루트를 제외한 모든 내부 노드 v key(v) >= key(parent(v)) 모든 노드의 경우, 부모노드의 키 값이 자식 노드의 키 값보다 작거나 같아야 한다. 완전이진트리 (complete binary tree) : 힙의 높이 h i = 0, ..., h-1에 대하여 깊이 i인 노드가 $2^i$개 존재 깊이 h-1에서 내부노드들은 외부노드의 왼쪽에 존재 즉, 진행순서 : Root - L - R ⇒ 힙의 마지막 노드는 깊이 h-1의 가장 오른쪽 내부 노드 n개의 키를 저장한 힙의 높이 = O(logn) 2. 힙을 이용한 우선순위 큐 구현 각 내부노드에 key-value 쌍을 저장 마지막 .. 위상 정렬 Topology Sort 위상 정렬 Topology Sort 태스크 수행 순서를 찾는 알고리즘 방향 그래프에 존재하는 각 정점의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것 Directed Acyclic Graph에만 적용 가능 (사이클이 발생하지 않는 방향 그래프) 하나의 그래프에서 여러 개의 위상정렬이 도출될 수 있다. 위상정렬의 시작점이 있어야 한다. 그래프에 남아 있는 정점 중 진입차수가 0 인 정점(해당 정점으로 들어오는 간선이 없는 경우)이 없다면 위상정렬 알고리즘 종료 example 진입 차수가 0 인 정점 (들어오는 간선의 수가 0, 위상 정렬의 시작점이 될 수 있는 정점)을 선택 → 여러 개인 경우 아무거나 선택 → 초기에 진입 간선의 수가 0 인 모든 정점을 큐에 삽입 : (0) (1) 선택된 정점과.. 네트워크 플로우 Network Flow, 에드몬드-카프 Edmonds-Karp, 포드 풀커슨 Ford-Fulkerson 알고리즘 네트워크 플로우 Network Flow 특정 지점에서 다른 지점으로 데이터가 얼마나 많이 흐르고 있는지 측정하는 알고리즘 ⇒ 최대 유량 max flow 문제 해결에 사용되는 알고리즘 example A→D의 최대 유량은 6, 6 이상을 보내면 정체 현상이 발생하기 때문이다. 각 경로의 용량 중 가장 작은 것이 최대 유량 Terminologies flow: 두 정점 사이에서 현재 흐르는 양 capacity: 두 정점 사이에서 최대로 흐를 수 있는 양 source: 유량이 시작되는 정점 sink: 유량이 도착하는 정점 augumenting path: 소스에서 싱크로 유량을 보내는 경로 residual capacity: 용량 - 유량 Properties 용량 < 유량 (capacity < flow) flow(m.. 최단 경로 찾기 Shortest path, 변 경감 edge relaxation, 벨만-포드 Bellam-Ford's, 다익스트리 Dijikstra's 알고리즘 최단 경로 찾기 Shortest Path 두 노드를 잇는 가장 짧은 경로 찾기 weighted graph에서 엣지 가중치의 합이 최소가 되는 경로 찾기 problems single source 단일 노드에서 출발하여 그래프 내의 모든 다른 노드에 도착하는 가장 짧은 경로 찾는 문제 single destination 모든 노드에서 출발하여 그래프 내의 한 단일 노드로 도착하는 가장 짧은 경로를 찾는 문제 single pair 주어진 꼭지점u, v 사이의 최단 경로 찾는 문제 all pair 그래프 내의 모든 노드 쌍 사이의 최단 경로 찾는 문제 Floyd-Warshall algorithm all-pair 최단 경로 문제 알고리즘 optimal substructure 활용 optimal substructur.. 최소 신장 트리 Minimum Spanning Tree, 크루스칼 Kruskal's, 프림 Prim's 알고리즘 Greedy Algorithm 각 단계에서의 최선책을 선택하여 다음 단계로 진행하는 알고리즘 현재 선택에 의해 다음 단계의 조건이 변하는 경우 부적합 최소 신장 트리 MST 모든 노드를 포함하는 그래프, 모든 노드가 연결된 그래프, 트리 속성을 만족하는 그래프 그래프 상에서 각 간선에 가중치가 부여됨 한 정점을 기준으로 가능한 가장 작은 가중치의 간선들을 사용하여 모든 정점을 연결하는 트리(MST) MST를 구하는 문제를 푸는 알고리즘 크루스칼 가장 작은 값의 간선을 선택한다. → 그 다음 작은 값의 간선을 선택한다. → 그 다음으로 작은 값의 간선을 선택하되 사이클이 생기지 않게 선택한다. → 모든 정점을 선택할 때까지 위 선택 과정을 반복한다. 프림 알고리즘 기준 정점에서 출발하는 가장 작은 값은 간.. 다이나믹 프로그래밍 Dynamic Programming 다이나믹 프로그래밍 Dynamic Programming Dynamic Programming의 개념 큰 문제를 작은 문제로 나누어 문제를 푸는 기법 divide and conquer 기법과 달리 작은 문제의 중복이 발생하지 않는다. 분할된 모든 작은 문제들은 한번만 풀어야 하기 때문에 작은 문제의 정답은 구한 뒤 메모해 둔다. 그리고 큰 문제를 풀다가 동일한 작은 문제가 나타나면 앞에 메모한 작은 문제의 결과값을 이용한다. Dynamic Programming의 조건 작은 문제가 반복적으로 일어나는 경우 같은 문제를 구할 때마다 결과값이 같은 경우 메모이제이션 Memoization 한번 계산한 작은 문제의 결과값을 저장해두는 것 Bottom-up 구현 def fibonacci_bottom_up(n): if .. 분할정복 Divide & Conquer 알고리즘, 합병정렬 Merge Sort 이해하기 이번 글에서는 분할 정복 알고리즘에 대해 이해하기 위해 merge sort 복잡도를 분석해보겠습니다. Divide & Conquer Algorithm 분할 정복 알고리즘은 n개의 요소를 가진 문제를 n개의 부분 문제로 divide 하고 부분 문제들을 conquer하여 문제를 해결하는 방식입니다. n개로 분할된 문제들을 해결하는 과정을 n번 반복해야 하므로 재귀적으로 해결할 수 있고, 이 과정에서 점화식을 활용할 수 있습니다. 점화식이란 더 작은 입력에 대해 자신의 값으로 함수를 나타내는 방정식으로, 분할 정복 알고리즘에서 수행시간을 표현하는데 사용됩니다. 예시 1) T(n) = T(n-1) + Θ(1) T(n) = 각 재귀 호출에 걸리는 시간은 상수시간 Θ(1) + 새로운 재귀 호출에 필요한 시간 T(n.. Big-O notation Big-O notation 점근적 상한 Aysmpototic Upper Bound n ≥ N 인 모든 정수 n 에 대하여 $g(n)$ ≤ $cf(n)$이 성립하는 실수 c>0과 음이 아닌 정수 N이 존재한다. $g(n) ∈ O(f(n))$ $g(n)$ 은 $f(n)$의 big O이다. $g(n)$ : 내가 구한 알고리즘/함수 $f(n)$ : 해당 함수의 시간 복잡도를 나타내는 함수 g(n) ∈ O(f(n)) n ≥ N 인 모든 정수 n에 대하여 g(n) ≤c x f(n)이 성립하는 실수 c > 0 과 음이 아닌 정수 N이 존재한다. 기울기가 양수 cf(n)과 g(n)의 교차점 N이 양의 정수로 반드시 존재한다. N 이후로 cf(n)은 g(n)보다 항상 큰 값을 나타낸다. 즉, N이후에 g(n)은 아무리 .. 이전 1 2 다음
