오늘도 더 나은 코드를 작성하였습니까?

정의 - DAG(-Directed Acyclic Graph 순환하지 않는 유향 그래프)를 방향성에 거스르지 않도록 순서대로 배열하는 방법. 예를 들어 대학을 졸업하고, 이후에 일어나는 일들을 그래프로 표현한다 가정해보자. 부분적인 순서 관계만 있는 상황에서, 필수조건을 만족하면서 치킨집을 운영한다. kahn 알고리즘 (진입차수를 이용한) 방법 * 진입차수 - 특정 노드로 들어오는 간선의 수 진출차수 - 특정 노드에서 나가는 간선의 수 - 여러가지 순서가 나올 수 있다. - 위상정렬의 가능 여부, 가능하다면 어떤 순으로? - 시간복잡도 O(V+E), 모든 정점에 연결된 간선의 갯수 만큼 반복 Queue를 이용하여 구현. 1. 진입차수 degree 0 인 정점을 Queue에 삽입한다. - 진입차수 Array..

컴퓨터 과학에서 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 변의 가중치가 음이거나 양인 (음수 사이클은 없는) 가중 그래프에서 최단 경로들을 찾는 알고리즘이다 "모든 노드"에서 다른 "모든 노드"까지 최단경로 모두 계산 모든 정점 하나하나 마다 거쳐갈때 상황을 가정하여, 최단거리를 완화해서 나간다는 점에서 dp 유형에 해당하는 알고리즘이다. 노드 k를 경유해 가는 경우를 확인 (A --> B) 와 (A --> K --> B) 뭐가 더 짧은지 확인한다. 예시) k = 1 일때, 4번 --> 2번 이동 불가능(INF) 했지만, 1을 경유하면, 4 --> 1 --> 2 값 5로 갱신 4번 --> 5번 이동 불가능(INF) 했지만, 1을 경우하면, 4 --> 1 --> 5 값 -2로..

다익스트라(dijkstra) 알고리즘은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘이다. "특정" 노드에서 다른 "모든"노드로 가는 최단경로를 계산한다. 양의 가중치에서 사용한다. 매 상황(현재 노드에서 다른 노드로 이동)때 가장 비용이 적은 노드를 선택한다(그리디) 현재 최소거리 Distance Table을 갱신하면서, dp 유형에도 해당하는 알고리즘이다. 예시) 아래와 같은 무방향 그래프가 주어졌다고 가정하자. 출발점 A로 시작한다 가정하면, 갈수 있는곳은 B, D 두 군데이며,테이블을 갱신 후, 시작점(A)에서 가까운 B로 간다. B로 이동후, 갈수 있는곳은 E, D 두 군데이며, 테이블을 갱신 후, 시작점(A)에서 가까운 D로 간다. D로 이동후, 갈..

이진탐색의 응용으로 자주 나오지는 않지만, 알아두면 유용하고 반대로 모르면 구현자체가 쉽지 않을 수도 있다. *이진탐색의 응용으로 반드시 오름차순 정렬은 기본적으로 되어있는 배열 및 리스트를 이용한다. 상한선 (upper_bound) - key 보다 "큰 값"이 가장 처음 나오는 index val arr = arrayOf(1, 2, 2, 3, 3, 3, 4, 5, 5, 6, 7, 7) 위 와같은 배열이 있다면 key = 6이라면 상한선은 무엇일까? 첫번째 7인 index 10일 것이다. key = 7 또는 그 이상의 값이라면 상한선은 배열의 마지막 Index + 1, 반대로 배열의 최소값이 들어온다면 무조건 index 0이다. 여기 핵심적으로 봐야할것 1. 조건을 만족하는 key값을 찾기 위해 left는..