이것도 알아야 하네?

순서가 정해져 있는 여러 일들을 순서에 맞게 나열할 떄 사용할 수 있는 알고리즘이다. 즉, 선후 관계가 정의된 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..