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 ..

https://www.acmicpc.net/problem/2294 🔒 골드5 - #2294 동전 2 📌 테스트케이스 추가 힌트 2 15 3 5 = 3 2 15 2 1 = 8 ✍️ 풀이법 대표적인 DP 문제이고, 이 전 포스트인 동전 1 문제와 비슷하게 생각할 수 있다. DP 문제를 풀 때, 가장 먼저 고려해야 할 것은 캐싱을 통한 점화식 도출이다. 캐싱을 위해 DP 테이블을 그려보면, 가로축에 K원이 되기 위한 가치를 나열할 수 있다. 그리고 세로축에 동전을 하나씩 추가하며 문제를 해결해 보자. 먼저, 1원짜리 동전을 추가해 준다. 첫 동전 만으로는 점화식을 도출하기 어려우므로, 다음 동전으로 넘어간다. 5원짜리 동전을 추가해 주게 되면, 4원까지는 캐시에 영향을 미치지 않는다. 이후, 5원을 만들 때부..