알고리즘 (22) 썸네일형 리스트형 힙 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 쌍을 저장 마지막 .. Priority Queue 우선순위 큐 개념과 이를 이용한 정렬 및 응용 문제 파이썬 구현 1. 우선순위 큐 ADT 각 데이터 항목을 (키, 원소) 쌍으로 저장 ex) (학번, 점수), (주소, 우편물) unordered : 삽입시 데이터 키를 고려하지 않기 때문에 빠르지만 삭제는 키의 순서로 고려해야 해서 느리다. ordered: 삽입시 느리지만 삭제를 빠르다. 삽입 삭제의 빈도에 따라 구현 방식을 결정한다. 삽입시 키에 따라 정렬, 삭제시 키에 따라 정렬 키를 저장하기 위한 자료구조로 우선순위 큐를 활용한다. ADT 메소드 i) 주요 메소드 insertItem(k,e) : 키 k인 원소 e를 큐에 삽입 element removeMin() : 큐에서 최소 키를 가진 원소를 삭제하여 반환 ii) 일반 메소드 int size () : 큐의 항목 수 반환 bool isEmpty() : 큐가 비어있.. [프로그래머스 코딩 테스트 연습] BFS/DFS 4. 여행경로 BFS/DFS 4. 여행경로 문제 설명 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다. 나는 stack을 이용해서 푸는 코드를 참고 했다. 그래서 항상 stack은 stack = ["ICN"] 으로 초기화 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 모든 공항은 알파벳 대문자 3글자로 이루어집니다. 주어진 공항 수는 3개 이상 10,000개 이하입니다. tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다. 주어진 항공권은 모두 사용해야 합니다. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가.. 위상 정렬 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 .. 이전 1 2 3 다음
