Computer Science/알고리즘(백준+프로그래머스)
플로이드-와샬 알고리즘
1. Transitive Closure : Digraph G가 주어졌을때, u-v사이에 path가 존재하면 u-v사이의 directed edge를 추가한게 G*, transitive closure이다. EX) G에서 B->D->E 를 연결하는 path가 있으면 B->E directed edge를 추가한다. -> 이는 diagraph에서 reachability information을 제공할 수 있다. 2. Transitive Closure는 어떻게 알 수 있는가? 1) 모든 정점에 대해서 DFS를 수행한다. O(n(n+m)) -> 정점에서 reachable한 vertex를 찾는 DFS를 모든 정점에 대해서 수행해야 한다. : 만약 Graph가 Dense하다면 최악의 경우엔 O(n^3), Sparse하다면 ..
Greedy Algorithm(프림/크루스칼/다익스트라)
1. Optimization Problems : 최적해 문제 -> 최적해 문제란, 총 비용을 최소화하거나, 총 이익을 최대화 하는 등의 특정한 목적을 갖고 있다. - 가능한 모든 값을 분석해 가장 좋은 것을 고르거나, 매번 선택을 할때 가장 최적의 결과를 낳는 일련의 선택을 하게 된다. 2. Greedy Algorithm : 탐욕 알고리즘은 최적해 문제를 해결하는 여러가지 방법 중 하나로, 선택 당시에 가장 좋아보이는 방법을 고른다. "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 갖고 있다. -> 따라서, 이를 결정하는 일정한 기준이 존재해야 한다. : 어떤 것을 고를지는 오랜 시간이 걸려서는 안되며, 이를 계산하는데 너무 많은 비용이 들어서도 안된다. EX)..
그래프와 관련 알고리즘(DFS,BFS)
1. Graph란? : 일련의 노드(Vertex) 집합 V와 간선(Edge) 집합 E로 구성된 자료구조의 일종이다. 일반적으로 Vertex에는 데이터가, Edge에는 Vertex와 Vertex 사이의 관계 정보가 포함되어 있다. 2. Graph가 사용되는 예시 -> 문제를 풀기 위해 이를 자료구조로 만들어 컴퓨터가 이해할 수 있도록 해야 한다. 1) Airline Routes -> 이 graph의 각 vertex는 공항 이름이고, 간선이 존재하면 항공 노선이 존재한다는 것이다. Q) 가장 비행기를 덜 갈아탈수 있는 노선은? - 최단 거리 노선을 탐색하면 된다. (중간 경유지를 최소화함) : 이는 BFS를 이용해 해결할 수 있다. 2) FlowChart : 순서도 자체가 그래프라고 할 수 있다. -> 방향..