돌고 돌아 기본

프로그래머스 42861번 - 섬 연결하기 요구사항 1. 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 반환하라. 2. A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다. 요구사항 분석 및 풀이과정 1. 이 문제는 전형적인 최소 스패닝 트리 문제입니다. 최소 스패닝 트리 문제는 크루스칼 알고리즘 또는 프림 알고리즘으로 해결 가능합니다. 2. 저는 서로소 집합(Union-Find)을 이용한 크루스칼 알고리즘을 사용할 할 것입니다. 크루스칼 알고리즘에 대해서는 따로 설명하지 않겠습니다. 3. 섬 사이에 다리를 건설하는 비용을 기준으로 내림차순 정렬하여, 비용이 적은 다리부터 사이클이 형성되지 않도록 N - 1 개의 ..

프로그래머스 42577번 - 전화번호 목록 요구사항 1. 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있으면 false, 그렇지 않으면 true를 반환하라. 요구사항 분석 및 풀이과정 1. 보는 관점을 바꾸면 풀이가 쉬워진다. 한 번호가 다른 번호의 접두어인 경우가 있는가 한 번호의 접두어가 될 수 있는 문자열 중 전화번호부에 있는 번호가 있는가 2. 전화번호부에 특정 번호가 있는지 빠르게 확인하기 위하여 전화번호부를 Set(HashSet)을 이용하여 만들어줍니다. 3. 전화번호부에 등록된 번호를 순회하면서 해당 번호의 모든 접두어에 대하여 전화번호부에 있는 번호인지를 검사합니다. 그림으로 살펴보면 다음과 같습니다. 전화번호부는 ["12", "123", "1235"]라고 해보겠..

프로그래머스 49189번 - 가장 먼 노드 요구사항 1. 주어진 그래프에서 1번 노드에서 가장 멀리 떨어진 노드의 개수를 반환하라. 요구사항 분석 및 풀이과정 1. 여기서 중요하게 봐야 할 점은 "최단 경로"의 정의이며, 그 이유는 최단 경로가 간선의 "개수"의 최솟값으로 정의된다는 점입니다. i번 노드에서 j번 노드까지의 최단 경로 = i번 노드에서 j번 노드로 이동할 때 지나가는 간선의 개수가 작은 경로 2. i번 노드에서 j번 노드로 이동할 때, 다른 노드를 경유하여 올 경우 직접적으로 이동했을 때보다 최소한 하나의 간선을 더 지나치게 되며, 최단경로가 아니게 됩니다. 3. 1번 노드부터 BFS 알고리즘을 적용하여 j번 노드를 방문할 때, 이미 방문했다면 해당 노드를 처음 방문했을 때의 경로가 최단..

프로그래머스 43162번 - 네트워크 요구사항 1. 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 2. 1번을 만족할 경우 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 말할 수 있습니다. 3. 주어진 연결 정보를 바탕으로 네트워크가 구성되어있을 때, 네트워크의 개수를 반환하라. 요구사항 분석 및 풀이과정 1. 문제가 어려워 보이지만 결과적으로 주어진 컴퓨터들이 몇 개의 그룹으로 묶이는지를 묻는 문제입니다. 2. 전형적인 서로소 집합(Disjoint-Set, Union-Find) 문제라고 볼 수 있습니다. 서로소 집합을 이용하여 풀어보겠습니다. 서로소 집합 자료구조에..

기본 구현 class Trie { public static class Node { private boolean isEnd; private final Node[] next; public Node(int size) { this.isEnd = false; this.next = new Node[size]; } public Node next(int v) { return this.next[v]; } public boolean isEnd() { return isEnd; } } private final char start; private final int size; private final Node root; public Trie(char start, char end) { this.start = start; this...