Dot Dot Line Dot

title: Programmers - 부대복귀 date: 2022-10-25 tags: Algorithm Graph Dijkstra https://school.programmers.co.kr/learn/courses/30/lessons/132266 문제 요약 그래프가 주어지며, 출발 지점의 리스트와 하나의 도착 지점이 주어진다. 각 출발 지점에서 도착 지점까지 가는 경로의 최소 길이를 vector에 넣어 return한다. 경로가 없다면 -1을 넣는다. 문제 풀이 Node의 개수는 최대 100K이며, O(n^2) 이상이라면 TLE가 발생할 것이다. 출발 지점이 모두 달라 Bellman Ford Algorithm을 사용할 수 없다. 하지만 도착 지점이 하나이기에, 이를 역으로 생각하면 도착 지점에서 각 지점..

title: Programmers - 순위 date: 2022-10-08 tags: Algorithm Graph https://school.programmers.co.kr/learn/courses/30/lessons/49191 문제 요약 실력 차이에 따라 승패가 확실한 경기들이 주어진다. 경기 결과들을 통해 정확한 순위를 도출할 수 있는 인원의 수를 return한다. 문제 풀이 처음에는 Literally Top-down 방식을 생각하였다. 각 노드에서 자식 노드(해당 노드에게 진 노드)로 진행하며 개수를 count하는 방식으로, 이 방식은 부모 노드가 여러개일 때 처리가 복잡해진다. 결국 각 노드를 기준으로 부모 노드와 자식 노드의 개수를 구하여 문제를 해결하였다. 처리가 귀찮으니 메모리를 더 쓰더라도 ..

title: Programmers - 섬 연결하기 date: 2022-08-12 tags: Algorithm Graph Kruskal https://school.programmers.co.kr/learn/courses/30/lessons/42861 문제 요약 n개의 섬이 존재하며, 섬을 잇는 다리와 다리의 비용이 주어진다. 모든 섬이 연결되도록 하는 최소의 다리 비용을 return한다. 문제 풀이 Graph 문제로, Kruskal 알고리즘을 알고 있는지 확인하는 문제이다. Kruskal 알고리즘은 가장 적은 비용의 edge부터 확인하며 두 vertex의 가장 높은 parent가 같지 않을 경우 해당 edge를 추가한다. 같은 parent를 가진다면 이미 서로 연결되어 있는 상태로, 더 연결할 필요가 없다..

title: Programmers - 가장 먼 노드 date: 2022-07-23 tags: Algorithm Graph https://school.programmers.co.kr/learn/courses/30/lessons/49189 문제 요약 Graph가 주어진다. 1번 노드에서 가장 멀리 떨어진 노드의 개수를 count 한다. 문제 풀이 Graph를 순회하며 1번 노드에서 얼마나 떨어져있는지 확인하는 문제이다. BFS 방식으로 각 노드를 확인하며, Priority Queue를 이용하여 거리를 기준으로 짧은 거리에 존재하는 노드부터 갱신한다. 여러 노드가 하나의 노드에 대한 emplace 작업을 할 경우, 이미 방문한 노드가 추후 Priority Queue에서 나올 수 있다. erase 혹은 remo..

title: Programmers - 합승 택시 요금 date: 2022-07-22 tags: Algorithm Graph Floyd-Warshall https://school.programmers.co.kr/learn/courses/30/lessons/72413 문제 요약 동일한 위치에서 출발하여 각자 A,B로 택시를 타고 간다. 처음부터 따로 갈 수 있고, 중간까지만 합승하였다가 이후 각자 택시를 타고 가도 된다. 최저 택시 요금을 계산하여 return한다. 문제 풀이 Floyd-Warshall 알고리즘을 사용하면 매우 간단한 문제이나, 잘못 접근하여 긴 시간동안 삽질을 했다. Dijkstra 알고리즘을 사용하여 시작 노드 S에서 모든 노드로 가는 비용과 경로를 확인한 후, 해당 경로들만 이용하였을 ..

title: Programmers - 배달 date: 2022-06-21 tags: Algorithm Graph Dijkstra https://programmers.co.kr/learn/courses/30/lessons/12978 문제 요약 주어진 그래프에서 root 노드로부터 K 가중치 내로 이동 가능한 노드의 수를 구하여 return한다. 문제 풀이 전형적인 Dijkstra Graph 문제이다. 주어진 그래프를 인접행렬로 변환한 후, N-1번 거리를 갱신하여 root로부터 모든 노드로 가는 거리가 K 이하인 노드의 개수를 구한다. 갱신이 이루어지지 않을 때 갱신을 중단하여도 되지만, 최대 갱신 횟수는 N-1번이다. 중단 조건 구현이 귀찮아서 N-1번 갱신하였다. 가중치에 -가 존재한다면 Floyd-W..