[LV3] 섬 연결하기
문제 풀이항목이 '탐욕법'으로 되어 있어서, 처음에는 dfs를 통해 모든 경로를 다 탐색한 후 그 중 최소 거리를 찾으려 했다.하지만 개같이 실패에 시간초과까지,..,.,,결국 다른 방법을 사용해 보기로 했다. 내가 찾아본 방법은 '크루스칼 알고리즘'으로, 모든 정점을 연결 할 때, 최소의 비용을 찾는 알고리즘이라고 한다.정확히 이 문제를 풀기에 적합한 알고리즘으로, 각 정점과 가중치가 주어졌을 때, 현재 정점이 연결 되어 있는지 아닌지를 파악하여 연결 되어있다면 패스, 안되어 있다면 가중치를 더하는 방식을 사용한다. 위와 같은 그래프의 각 정점을 모두 이었을 때, 최소 가중치를 구하는 방법을 알아보자먼저 가중치의 오름차순으로 정렬해 준다. 그 다음, 각 연결별로 순회하며 노드의 부모 노드들을 비교해 ..
[C3] 5430 - AC
문제세상에 할 일이 없어서 새로운 언어를 만드는 사람이 어딨나,,,,,,, 풀이사실, 처음 봤을 때는 R은 뒤집기, D는 삭제라 하니...당연히 reverse()와 shift()를 쓰면 되는거 아닌가? 라고 생각했지만그렇게 당연하게 풀리는 문제가 골드5일리가 없다..!!!!의심하고 또 의심하며 처음부터 다른 풀이 방법을 사용해 보기로 했다. 우선, 테스트케이스가 최대 100개, 주어지는 함수의 개수가 최대 10만개, 배열의 요소가 최대 10만개이다.reverse()의 시간 복잡도는 O(n)이므로, 최악의 경우 복잡도는 O(n^2).그러므로 최대한 메서드를 쓰지 않고, 1차원 for문 안에서 해결하는 것을 목표로 했다. 내가 생각했던 방법은 투포인터?와 비슷한 방법으로, 시작 인덱스와 끝 인덱스를 정해놓고..
[C3] 1260 - DFS와 BFS
문제풀이DFS는 재귀로, BFS는 큐를 이용해서 풀었다.먼저 노드 정보를 이용해 그래프를 만들어준다.그래프는 객체로 만들어도 되고, 이차원 배열로 만들어도 되는데 나는 일단 이차원 배열을 사용하고 있다.노드가 n개, 간선이 m개이므로 그래프는 n개의 요소를 가진 이차원 배열이고, n번 노드와 연결된 노드들을 n-1번 배열에 넣어주면 된다.편의를 위해 n이 아니라 n+1개의 배열을 만들어주고, 0번 배열은 비워 1번부터 시작하도록 해주면 좋다노드연결된 노드0-12, 321, 431, 441,2,3 const graph = Array.from({ length: n + 1 }, () => []); input.forEach((el) => { const [s, e] = el; graph[s].push..
