algorithm

개요 MST (Minimum Spanning Tree)를 구하는 알고리즘 what's MST? 모든 노드(Vertex)를 최소 비용으로 최소 간선(Edge)을 사용해 연결한 트리 (no cycle) * MST의 Edge수는 Number Of Vertex - 1 이다. Where to use MST? Network Design Approximation algorithms (ex. traveling salesperson problem) When to use Kruskal Get MST of undirected graph by Greedy algorithm Algorithm (1) Sort all edges in ordering by weight (ascending) => 최소 비용 간선 오름차순 (2) Pi..

🔒 문제 💭 생각의 흐름 문제를 푸는 입장에서 유형을 보지 않을 수가 없는데 조건: 'directed graph' + can connect itself ∴ Union-Find 알고리즘을 사용하기 어렵다. 총 2가지 방식으로 풀이할 수 있겠다. Topological Sort using BFS (Kahn's Algorithm) 풀이 DFS 변형 풀이 여기선 2번 방법을 선택해서 풀이해보겠다. DFS 변형 풀이법의 핵심은 다음과 같다. 전형적인 DFS 코드를 쓰되, 부모 노드 Set(지나온 부모 노드 방문여부)을 Keep 한다! DFS 를 재귀적으로 호출하면서 이전 스택으로 되돌아 가기 직전에 방문처리 되지 않은 상태로 되돌리기 위해 (부모 노드 Set 업데이트) 부모 노드 방문을 취소한다. bool dfsD..

🔒 문제 Detect cycle in an undirected graph | Practice | GeeksforGeeks practice.geeksforgeeks.org 💭 생각의 흐름 일단 문제 자체에서 DFS를 사용하여 사이클을 탐색하라고 했다. 정석적인 DFS recursive function을 작성하고 사이클 생기는 시점에 true만 리턴하면 된다고 생각했다. Q. 사이클이 생기는 시점이 언제인가? A. BackEdge (부모노드 이외의 노드에 연결되는 선이 발견되는 시점) 따라서 visited (방문 기록) 배열을 두고 visited 상에 방문된 상태로 기록되있으면서 parent 노드가 아닌 노드로 연결되있을 경우 바로 true (사이클이 존재)를 리턴하도록 한다. ⚠️ 실수 아래 그림 처럼 그..

개요 모든 경우의 수를 탐색하는 Brute Force 알고리즘으로 조건이 존재할 때 사용한다. State-Space Tree 라고도 한다. 기본적으로 DFS 를 사용하며 조건에 부합하지 않는 branch에 대해 Pruning (가지치기)를 하여 불필요한 경우의 수를 따지지 않는다. Branch and Bound BFS 베이스로 (depth == level) 기준으로 자리를 구분한다. 관련 문제 www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/ Write a program to print all permutations of a given string - GeeksforGeeks A Computer Scie..

🔒 문제 💭 생각의 흐름 1. 맨 첫글자로 group을 나누어 9..0 역순으로 훑는다. 2. 각 라운드를 돌며 중복 없이 가장 큰수가 하나 나올때 마다 이어붙인다. roundArray = [3, 34, 3411, 3434, 3413, 345] 1라운드 : 3 3 3 3 3 3 3 2라운드 : 3 4 4 4 4 4 3라운드 : 3 3 1 3 1 5 4라운드 : 3 4 1 4 3 ... 😵‍💫 실수 1. 위 방법에서 중복이 있을 경우 해당 숫자만 후보로 남기고 라운드를 또 따로돌려야한다. -> 재귀를 써야함. 2. 모든 숫자가 0이 올 경우 출력은 0이다. ex) [0, 0, 0, 0] -> 0 (※ 결과를 string으로 반환할 뿐 어쨌든 가장 큰 정수 변환하여 출력해야한다.) 🔐 잘못된 풀이 (Kotl..

🔒 문제 💡 생각의 흐름 (1) 아, 유클리드 호제법 GCD (최대공약수) 함수 작성해서 최소공배수 바로 구해보리기 하면 되겠군. 최대공약수 공식 알고리즘은 요기서 최대공약수 알고리즘 Greatest Common Divisor Problem 임의의 자연수 n, m (단, n > m) 에 대한 최대공약수? Input 자연수 n, m Output Largest D s.t n % D and m % D == 0 s.t: Search That의 약자. [1] n-gcd 가장 생각하기 쉬운.. m-falcon.tistory.com (2) 오름 정렬해서 쪼꼬만 애들끼리 만든 최소공배수로 뒷놈들 다 검사해보는 식으로 해야겠군 🔑풀이 (Kotlin) class Solution { fun gcd (a: Int, b: In..