olrlobt

분할 정복 알고리즘 (Divide and Conquer Algorithm) 분할정복 알고리즘은 간단히 말해, 문제를 작게 분할한 후 각각을 정복하는 알고리즘이다. 큰 문제를 작은 문제로 분할하여 각각을 해결하고, 그 결과를 이용해 전체 문제를 해결한다. 이때 분할된 작은 문제는 원래 문제와 같은 형태를 가지며, 작은 문제는 원래 문제의 일부분이 된다. 분할된 작은 문제를 재귀적으로 해결하고, 이를 결합하여 원래 문제를 해결한다. 분할정복 알고리즘은 재귀적인 방법을 통해 문제를 해결하며, 대표적인 예시로는 이진 탐색(Binary Search), 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort) 등이 있다. 분할 정복 알고리즘과 동적계획법(DP) 분할정복 알고리즘과 동적 계획법은 모두 대규모 ..

유클리드 호제법 (Euclidean Algorithm) 유클리드 호제법이라고도 불리는 유클리드 알고리즘은 둘 이상의 정수의 최대공약수(GCD)를 구하는 알고리즘이다. 유클리드 호제법은 큰 수(num1)와 작은 수(num2) 사이의 최대 공약수는 큰 수를 작은 수로 나눈 나머지(R)와 작은 수(num2) 사이의 최대 공약수와 같다는 점을 반복하여 문제를 해결한다. 기본적인 방법은 다음과 같다. 큰 수(num1)에서 작은 수(num2)를 나눈다. 나머지가 0이 아니라면, 나머지와 작은 수(num2)로 1번부터 다시 시작한다. 1~ 2 과정을 반복해 나머지가 0이라면, 그 수가 최대 공약수이다. 예를 들어, 21과 49 가 있다. mod 연산을 진행하면, 49 mod 21 = 7 나머지가 0이 아니므로, 나머..

플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) Floyd-Warshall 알고리즘은 음수 순환 사이클이 없는 그래프에서, 모든 점에서 모든 점까지의 최단거리를 구하는 알고리즘이다. 한 점에서 이웃 노드를 탐색하며 최단 거리를 구하는 다익스트라 알고리즘과는 다르게, 거쳐가는 중간 노드를 기준으로 최단 거리를 구한다. 또한, 다익스트라 알고리즘과 다르게, 음의 가중치를 갖는 간선이 있어도 된다. 하지만, 합이 음수 가중치를 갖는 사이클이 있어서는 안 된다. 위 그림은 1에서 4로 가는 최단 경로를 구하려 한다. 양쪽 그림 모두 2 > 3 > 2로 가는 사이클이 존재하지만, 좌측은 합이 +1, 우측은 합이 -1이다. 위 문제를 해결하기 위해서 좌측 그림은 1 > 2 > 4의 경로로 해..

다익스트라 알고리즘 (Dijkstra Algorithm) 다익스트라 알고리즘 (또는 데이크스트라 알고리즘)은 그래프에서 두 노드 사이의 최단 경로를 찾는 알고리즘이며, BFS와 DP를 사용하여 구현된다. 다익스트라 알고리즘은 일반적으로 두 노드 사이의 가장 짧은 경로를 찾는 문제에 사용되지만, 최단 경로 트리를 만드는 문제에도 많이 사용된다. BFS와 DP에 대한 이해가 부족하다면, 아래의 포스팅을 통하여 이해를 하면 좋을 것 같다. BFS : https://olrlobt.tistory.com/41 [알고리즘] BFS (Breadth-First Search) : 너비 우선 탐색 알고리즘이란? 너비 우선 탐색 BFS(Breadth-First Search) 트리나 그래프를 탐색하는 기법 중 하나로, 시작 노..

너비 우선 탐색 BFS(Breadth-First Search) 트리나 그래프를 탐색하는 기법 중 하나로, 시작 노드로부터 자식 노드들을 순서대로 탐색하면서 너비를 우선으로 탐색하는 알고리즘이다. BFS는 완전탐색 알고리즘에 속하며, 가중치가 없는 그래프에서 같은 거리에 있는 모든 노드를 탐색한 후, 다음 거리의 노드를 탐색하기 시작하는 방식으로 진행된다. 따라서, 가중치 없는 그래프에서 최단거리를 구하는 문제에 활용될 수 있다. BFS는 Queue를 활용해 다음 방문할 노드를 추적하며, While 반복문을 통하여 문제를 해결한다. BFS 탐색 과정 BFS 알고리즘의 기본 단계는 다음과 같이 요약할 수 있다. 시작 노드에서 시작하고 대기열(Queue)에 넣는다. 대기열에서 노드를 제거하고 검사한다.(pol..

깊이 우선 탐색(DFS, Depth-First Search) 트리나 그래프를 탐색하는 기법 중 하나로, 시작 노드에서 자식의 노드들을 순서대로 탐색하면서 깊이를 우선으로 탐색하는 알고리즘이다. 깊이를 우선시하여 모든 경우의 수를 탐색하기 때문에, 완전탐색 알고리즘에 속하기는 하지만, 항상 완전탐색으로 사용되지는 않는다. DFS는 주로 반복문을 활용하거나, 재귀문을 통하여 구현된다. DFS의 탐색 과정 DFS의 기본 탐색 과정은 특정 정점에서 시작하여 역추적(backtracking) 하기 전에 각 분기를 따라 가능한 한 멀리 탐색하는 것이다. 탐색하는 과정은 다음과 같다. 현재 노드를 방문한 것으로 표시한다. 방문한 표시가 되어 있지 않은 각각의 인접한 정점을 탐색한다. 더 이상 방문하지 않은 정점이 없으..

완전탐색 : 브루트포스 알고리즘 Brute Force Algorithm Brute : 무식한 Force : 힘 직역하면, 무식한 힘을 갖는 알고리즘이란 뜻으로, 완전 탐색 알고리즘의 한 종류이지만 완전 탐색의 또 다른 이름으로 쓰이기도 한다. 브루트 포스 알고리즘은 완전탐색으로 답을 도출하는 알고리즘이며, 대부분은 반복문과 조건문을 통하여 답을 도출한다. 모든 경우의 수를 전부 탐색하기 때문에, 100%의 정확성을 보장하지만, 모든 경우의 수를 전부 탐색하기 때문에, 높은 시간 복잡도를 갖는다. 완전 탐색과 브루트포스 알고리즘의 차이 브루트 포스와 완전탐색은 의미차이가 거의 없기 때문에, 같은 의미로 쓰이기도 한다. 영어로도 완전탐색은 Exhaustive Search 라고도 하고, Brute Force ..

동적계획법 : 다이나믹 프로그래밍 DP (Dynamic programming) DP는 하나의 큰 문제를 작은 문제로 나눈 뒤, 기억하여 푸는 알고리즘 기법이다. DP에서 동적계획법, 동적프로그래밍이라는 단어는, DP 창시자가 그냥 멋있는 단어를 붙인 것이라고 한다. 따라서 크게 의미를 부여하거나 찾아볼 필요는 없다. 하나의 문제를 작은 문제로 나누어 해결하는 방식은 분할정복 알고리즘과 비슷하다고 생각할 수 있다. 분할정복 알고리즘의 경우는 단순히 큰 문제를 작게 나누어 해결하는 방식에 불과하지만, DP의 경우는 작은 문제를 풀고 값을 저장하여, 중복된 계산 자체를 없애버린다. 예를 들어 피보나치 수열을 보자. 피보나치 수열은 재귀함수로, f(n) = f(n-1) + f(n-2) 의 형태를 띈다. 이때 계..