Category: Algorithms

All 44 Algorithms 26 Data Structures 10 Security 6 GitHub 1 Backend / Java 1

Per page5 10 20

KMP (Knuth–Morris–Pratt)

KMP 알고리즘은 문자열 탐색 알고리즘입니다. KMP는 Knuth–Morris–Pratt의 줄임말로 KMP 알고리즘을 제안한 Donald Knuth, Vaughan Pratt 그리고 James H. Morris의 이름을 따서 이름…

2024-05-314분

#알고리즘 #문자열

알고리즘

Floyd-Warshall (플로이드-워샬 알고리즘)

플로이드-워샬 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 정점 사이의 최단 거리를 구하는 알고리즘으로 O(V^3)의 시간 복잡도를 가집니다. 하나의 정점으로부터 다른 모든 정점사이의 최단 거리를 구하는…

2024-05-302분

#알고리즘 #그래프

알고리즘

벨만-포드 알고리즘

벨만 포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 어느 한 정점에서 나머지 정점까지 거리를 구하는 알고리즘입니다. 하지만 다익스트라와는 다르게 음수 가중치를 갖는 그래프에서도 동작을 하며, 음수 사이클을 찾아내는 기능도 가지고…

2024-05-293분

#알고리즘 #그래프

알고리즘

다익스트라(Dijkstra) 알고리즘

다익스트라 알고리즘은 그래프의 한 노드에서 연결된 다른 노드들로 가는 최단 거리를 구하는 알고리즘입니다. 만약 모든 노드 쌍간의 최단 거리를 구하고 싶다면 N개의 각 정점에 대해 해당 정점을 출발점으로 하는 다익스트라 알고리즘을…

2024-05-284분

#알고리즘 #그래프

알고리즘

최소 신장 트리(Minimum Spanning Tree)

최소 신장트리란 최소 신장 트리(Minimum Spanning Tree)는 가중치가 있는 무방향 그래프의 모든 노드를 포함하면서 사이클이 없고 가중치의 합이 최소가 되는 트리입니다. 연결그래프가 주어질 때, MST를 구하는…

2024-05-214분

#알고리즘 #그래프

알고리즘

Dynamic Programming (동적 계획법)

목차 동적 계획법이란 Top-Down와 Bottom-Up Coin Change Problem Knapsack Longest Common Subsequence Longest Increasing Subsequence Edit…

2024-05-1920분

#알고리즘

알고리즘

위상 정렬 (Topological Sort)

위상 정렬이란 유향 그래프에서 정해진 순서를 위배하지 않도록 나열하는 것입니다. 예를 들면 전략 게임에서의 빌드 오더나 선수강과목을 예로 들 수 있습니다. 전략 게임의 빌드 오더에서 A를 짓지 않으면 B를 지을 수 없고, B를 짓지…

2024-05-173분

#알고리즘 #그래프

알고리즘

퀵 정렬 (Quick Sort)

퀵 정렬(Quick Sort)은 배열에 있는 수 중 사용자가 지정한 규칙대로 임의의 pivot을 잡고, 해당 pivot을 기준으로 작거나 같은 수를 왼쪽 파티션, 큰 수를 오른쪽 파티션으로 보내고 다시 왼쪽 파티션 구간에 한하여…

2024-05-163분

#알고리즘 #정렬

알고리즘

분할 정복 (Divide & Conquer)

분할정복(Divide and Conquer)은 말 그대로 문제를 분할한 다음, 분할한 문제들 (sub-problems)을 해결하고, 그 결과를 합쳐서 원래의 문제를 해결하는 것입니다. 분할정복의 대표적인 예로는 합병 정렬, 고속…

2024-05-143분

#알고리즘

알고리즘

BFS (Breadth-First Search, 너비 우선 탐색)

너비 우선 탐색은 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 중 하나입니다. 현재 정점과 인접한 간선들을 검사하다가 방문하지 않은 정점들을 발견하면 그 간선을 통해 방문하지 않은 정점들을 자료구조 큐에 넣습니다.…

2024-05-133분

#알고리즘 #그래프