이것도 알아야 하네?

순서가 정해져 있는 여러 일들을 순서에 맞게 나열할 떄 사용할 수 있는 알고리즘이다. 즉, 선후 관계가 정의된 Graph에서 선후 관계에 따라 정렬 하기위해 위상 정렬을 이용한다. 이 때, Graph는 반드시 비순환 방향 그래프여야 한다. 선수 과목이 대표적인 예시다. 특정 수강과목에 먼저 수강해야하는 과목이 있다면 해당 과목부터 수강해야 한다. 이 경우, 위상 정렬을 통해 올바른 수강 순서 중 하나를 찾아낼 수 있다. 위상 정렬 동작 진입 간선 수는 Node에 들어오는 간선 수로, 해당 Node 전에 방문해야하는 다른 Node의 수를 의미한다. 진입 간선 수가 0인 Node와 이와 연결된 모든 (진입, 진출)간선 삭제 남아있는 그래프의 진입 간선 수를 갱신 그래프에 모든 Node가 없어질 때까지 1,2..

처음에 문제를 봤을 때, 선수과목 문제처럼 일의 순서가 존재할 때 순서에 맞게 정렬하는 문제해결법인 '위상정렬'이 가장 먼저 떠올랐다. 때문에 그래프를 생성하고 순서에 대한 정보를 같이 저장해주면서 해당 node 보다 먼저 방문해야하는 수를 indegree에 저장해주었다. 실제로 문제상 indegree는 1이상의 값을 가질 수 없지만, 일반적으로 다 적용할 수 있게 하고 싶어서 나머지 부분도 맞춰서 코딩해주었다. 처음 시작점인 0을 queue에 넣어주고 graph에 저장된 값을 이용하여 연결되어 갈 수 있는 node를 찾아 queue에 다시 집어넣는다. queue에 들어갈 수 있는 node는 우선 방문 조건이 없는 node로 즉, 해당 node의 indegree값이 0이면 queue에 넣는다. queue..

처음에는 최적화로 DP를 활용하는 문제인가 고민해봤지만, DP를 이용하여 구간을 구하는 쉬운 방법이 떠오르지 않아 노선을 변경했다. 한 번 훑으면서 조건에 맞는 구간을 출력한다. 우선 코드 상으로 left는 구간의 시작점을 right는 구간의 끝점을 나타낸다. while()을 통해 right는 한 번 훑으면서 새로운 보석을 발견했을 때, contains라는 dict에 값을 저장한다. contain이 기존에 구한 unique 보석의 개수를 모두 충족했을 때부터 left를 변경한다. 만약 이미 한 개 이상 보석이 존재할 때 해당 구간은 여벌의 보석을 소유한 것이므로 오른쪽으로 이동하며 구간에서 제외한다. def solution(gems): left = 0; right = 0 targets = set(gems..

다익스트라 알고리즘 개념 다익스트라 알고리즘 또는 데이크스트라 알고리즘은 그래프에서 노드(Node) 간의 최단 경로를 찾는 알고리즘 중 하나로, 시작 노드(Node)가 주어졌을 때 해당 시작점으로부터 다른 모든 노드(Node)까지의 최단 경로 찾습니다. 해당 알고리즘은 도로 교통망 및 라우팅 프로토콜 등에서 많이 활용되고 있습니다. 예를 들어, 그래프의 꼭짓점들이 각각 도시를 나타내고, 변들이 도시 사이를 연결하는 도로의 길이를 나타낸다면, 다익스트라 알고리즘을 통하여 두 도시 사이의 최단 경로를 찾을 수 있습니다. 다익스트라 동작 소스(Source)는 시작 노드(Node)이며, dist[]를 시작 노드(Node)와 시작 노드(Node)를 포함한 모든 노드까지의 거리로 정의합니다. dist[]에서는 시작..

최근 알고리즘 두뇌(?)가 멍청해지는 것을 느끼고, DP 관련 도서를 e-book으로 구매해서 기억을 찬찬히 다시 돌리고 있습니다. 그 중 구매한 "다이내믹 프로그래밍 완전 정복"이라는 책을 가장 먼저 읽었고, 책을 구매할 시에는 리뷰를 한 블로그를 발견하지 못하여 이 후에 구매하고자 하는 사람에고 도움이 되고자 이 글을 작성합니다. 처음에는 나동빈님의 코딩 저서처럼 한국산? 인 줄 알았지만, 그냥 번역본이었습니다... (표지만 봐도 지은이가 외국인인데.. 그냥 난 멍청...했...) 원제는 "Dynamic Programming for Coding Interviews"로 코딩 인터뷰에서 사용할 수 있는 동적 계산법을 소개한 책이며, 해당 책은 구글에 pdf..읍읍 책 리뷰 ★★☆☆☆ 장점 DP 관련 모든..

(시도 1) 코드 처음에는 단순히 graph를 변경하여 "Back Tracking" 방식으로 풀면 될 것 같아, 아래와 같이 코드를 짰다. #include #include #include #include using namespace std; void transpose_graph (int n, vector &graph, int k) { vector temp = graph[k]; vector col; for (int i = 0; i < n; i++) { col.push_back(graph[i][k]); graph[i][k] = temp[i]; } graph[k] = col; } void DFS(int n, vector graph, vector traps, int cur, int target, int shor..