이것도 알아야 하네?

https://programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 징검다리는 숫자가 적혀있는 디딤돌로 구성되어있고, 사람이 디딤돌을 지나가면 적힌 숫자가 줄어든다고 할 때 징검다리를 건널 수 있는 최대 인원을 구하는 문제이다. 사람이 건널 때 징검다리에 있는 디딤돌을 딛고 건너야하되, 숫자가 0이 된 디딤돌이 있으면 점프를 해서 가야한다. 점프로 넘을 수 있는 디딤돌 개수 또한 주어진다. 풀이 (시도 1) 효율성을 보는 문제라서 안될 것은 알았지만 누구나 생각할 수 있는 naive한 접근 방식을 도전해보았다. 징검다리 길이 x 징검다리에 있..

풀이 이번 문제에서 고려했어야했던 포인트는 두 가지로, 첫 번째는 후보 조합을 구하는 것과 두 번째는 조합 중 중복을 제외해야하는 것이다. 이렇게 복잡하게 풀 문제는 아니었는데, 깔끔한 알고리즘을 떠오르지 않았다. 후보 조합을 찾는 것은 2 step으로 구성되어있다. '*'로 치환되어있는 banned_id 들이 될 수 있는 후보를 먼저 dict형식으로 찾아놓은 후, DFS를 통해서 생성할 수 있는 모든 조합을 찾는다. 첫 번째 step에서 중요한 점은 banned_id의 후보를 dict 형식으로 저장할 때 id를 저장하는 것이 아닌 user_id의 위치를 저장한다. 이는 이후 중복체크할 때 사용된다. 조합을 찾을 때는 이미 선택한 id는 중복되서 들어갈 수 없으니 이미 앞에서 다를 banned_id로 선..

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