므네모시아

2021 KAKAO BLIND RECRUITMENT 합승 택시 요금 Level 2 문제 두 사람이 시작지점 S 로 부터 각자의 목적지 A, B에 도착할 때까지 택시 비용을 최소로 하려고 함 각 간선의 표시는 해당 도로를 사용하는데 드는 비용이며, 두 사람이 특정 위치까지 합승하여 비용을 절감할 수 있음 지점은 1에서 n개. n은 3이상 200이하 지점 s, a, b 는 1이상 n이하 자연수이며, 서로 다른 값 fares 는 [c, d, f] 로 이루어진 배열이며, c와 d 사이 요금이 f 라는 뜻 동일한 구간에 대한 요금 정보는 1번만 주어짐 f 는 1이상 100,000이하 Idea 시작 지점에서 모든 지점까지 최단 거리 구하기 모든 지점에서 A 까지, 모든 지점에서 B까지의 최단 거리 구하기 즉, S ..

연습문제 가장 먼 노드 Level 3 문제 n개의 노드가 있는 그래프 1번 노드에서 가장 멀리 떨어진 노드의 개수 구하기 가장 멀리 떨어진 노드란 최단 경로로 이동했을 때, 간선의 개수가 가장 많은 노드들을 의미 n은 2이상 20,000이하 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있음 간선 정보는 [a, b] 배열로 제공되는데, 이는 a번 노드와 b번 노드 사이에 간선이 있다는 의미 Idea Dijkstra 연결된 간선의 개수에 따라 최단 경로가 결정되므로 모든 가중치는 1로 가정하여 각 노드의 비용을 구하면 됨 Code Swift 다익스트라 알고리즘으로 구현 ► 다익스트라 알고리즘 with Swift 다익스트라 알고리즘 with Swift 알고리즘 문제를 풀다가 최단 경로에 관한 ..

Summer/Winter Coding(~2018) 배달 Level 2 문제 N 개의 마을로 이루어짐 각 마을은 양방향 통행 가능한 도로로 연결되어 있고 각 도로 별로 걸리는 시간이 다름 1번 마을에서 배달 하려고 하는데 K 시간 이하로 배달이 가능한 마을만 주문을 받음 N은 1이상 50이하 road 길이(도로 정보 개수)는 1이상 2,000이하 road 는 길이가 3인 배열 (a, b, c) a, b (1이상 N이하, a != b) : 마을 번호, c (1이상 10,000이하 자연수) : 걸리는 시간 a, b를 연결하는 도로는 여러 개가 있을 수 있음 K 는 음식 배달이 가능한 시간. 1이상 500,000이하 1번 마을에 있는 음식점이 K 이하의 시간에 배달이 가능한 마을의 개수를 반환 Idea 주어진 ..

알고리즘 문제를 풀다가 최단 경로에 관한 문제를 풀게 되었는데, 알고리즘에 대한 정확한 개념을 공부한 지 너무 오래된 것 같아 다시 공부해보았다! 최단 경로에 대한 알고리즘은 여러 가지가 있지만 이번엔 '다익스트라' 알고리즘에 대해 정리해보고자 한다. 다익스트라 알고리즘에 대해 설명하기 전 최단 경로에 대한 설명을 간단히 해보자면, 최단경로 란? - 유향 가중치 그래프를 가정 - 경로란, 한 정점에서 다른 정점까지의 길을 의미 - 경로의 길이란, 경로를 구성하는 간선들의 가중치 합을 의미 - 최단 경로란, 시작정점 → 도착정점의 경로들 중 길이가 가장 작은 경로를 의미 이때, 최단 경로에 대한 것은 또 다음과 같이 구분할 수 있다. - 단일 시작점 최단 경로 : 시작점 1개 → 모든 도착지 1. 가중치 ..