돌고 돌아 기본

프로그래머스 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...

기본 구현 class Dijkstra { public static final int INF = 987654321; public static class Pair implements Comparable { private final int x; private final int y; public Pair(int x, int y) { this.x = x; this.y = y; } public int getX() { return x; } public int getY() { return y; } @Override public int compareTo(Pair o) { if (this.x == o.x) { return this.y - o.y; } return this.x - o.x; } } private Dijkstr..

최대 공약수(gcd) - 반복 public int gcd(int a, int b) { while (b != 0) { int r = a % b; a = b; b = r; } return a; } 최대 공약수(gcd) - BigInteger.gcd public int gcd(int a, int b) { return BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).intValue(); } 최소 공배수(lcm) public int lcm(int a, int b) { return (a * (b / gcd(a,b))); }