Floyd Warshall이란? 대표적인 최단거리 찾기 알고리즘 중 하나 - 다익스트라, 벨만포드, 플로이드 와샬 * 다익스트라 : 모든 쌍의 최단 경로(음의 가중치 X) * 벨만포드 : 모든 정점에 대한 최단경로(음의 가중치 O) * 플로이드 와샬(음의 가중치 O + 음의 사이클이 없어야한다) 모든 정점끼리의 최단거리를 한번에 계산할 때 사용 + 동적 계획법을 사용 ex) 전체 정점에서 다른 정점들까지의 최단거리를 한번에 계산 -> 다익스트라의 경우 어떤 정점 A에서 다른 정점들까지의 최단 거리를 계산 Pseudo Code for(k=1;k> M; vector dis(N+1,vector(N+1,5000)); for (int i = 1; i > from >> to >> c; dis[from][to] = ..

이진탐색(Binary Search)란? 오름차순으로 정렬된 리스트에서 특정값을 찾는 알고리즘 오름차순으로 정렬된 리스트에서 중간 값(mid)을 선택하고 찾고자 하는 값(target)과 비교를 반복 때문에 정렬이 필수적 선형탐색보다 훨씬 빠르게 검색 가능(탐색 범위를 절반씩 줄여나감) 시간 복잡도 O(log N) 구현방법 1~100까지 오른차순으로 정렬된 카드 더미가 있다고 가정하자. 목표는 29를 찾는 것이다. i번째 카드는 c[i]로 나타내고, 목표 값(target)은 val로 표현하자. 결정 문제(Decision Problem, 답이 이분적일 경우)를 "c[i] >= val ?"로 설정하고 답은 i를 증가시키며 탐색을 시작한다. 그리고 v[i] >= val이 되는 지점이 나타나면 탐색을 완료합니다. ..