사진: Unsplash의Antoine Dautry 우리가 알고리즘 문제를 해결하다가 보면 특정 구간에 대한 변화를 줘야할 때가 있습니다. 이번 게시글에서는 부분합에 개념에 대해 알아보고 누적합을 사용해서 특정 구간에 대한 변화를 주는 방법을 알아보도록 하겠습니다. 누적합 누적합의 개념은 사실 단순합니다. 배열의 처음부터 각각의 원소를 모두 더한 값을 새로운 배열에 넣으면 됩니다. [1, 2, 3, 4, 5] 의 배열이 있다면 이에 대한 누적합 배열은 [0, 1, 3, 6, 10 ,15] 입니다. 이러한 개념을 이용하면 특정 구간에 대한 합도 쉽게 구할 수 있습니다. 만약 3부터 5를 더한 값을 구하려고 한다고 생각해 보겠습니다. 그럼 이 값은 1부터 5까지의 값에 1부터 2까지 더한 값을 뺀 값이랑 동일..

위상 정렬이란? 위상 정렬이란 방향이 있는 비순환 그래프(DAG, Directed Acyclic Graph)에서 모든 노드를 방향성에 따라 순서대로 정렬하는 알고리즘이다. 즉, 모든 노드들을 자신을 가리키는 화살표가 있는 다른 노드보다 앞에 오도록 배열하는 것이다. 이 알고리즘은 그래프 내부의 우선순위가 있는 작업들을 수행하는 순서를 결정하기 위해 사용된다. 위상 정렬 알고리즘의 핵심은 진입 차수(in-degree)를 이용하는 것이다. 진입 차수는 어떤 노드로 들어오는 화살표의 수를 의미한다. 위상 정렬은 진입 차수가 0인 노드부터 처리하면서, 해당 노드에서 출발하는 모든 화살표를 제거하고, 그 화살표를 제거한 노드의 진입차수를 감소시킨다. 이러한 과정을 반복하여 모든 노드를 처리하는 순서를 구한다. 위..

유클리드 호제법이란? 유클리드 알고리즘은 2개의 자연수의 최대 공약수를 구하는 알고리즘이다. 호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 예시 1071과 1029의 최대공약수를 구하면, 1071은 1029로 나누어 떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42 1029는 42로 나누어 떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21 42는 21로 나누어 떨어진다. 따라서, 최대공약수는 21이다. 78696과 19332의 최대공약수를 구하면, 78696 ＝ 19332×4 ＋ 1368 19332 ＝ 1368×14 ＋ 180 1368 ＝ 180×7 ＋ 108 180 ＝ 108×1 ＋ 72 108 ＝ 72..

배낭 문제란? 배낭 문제는 조합 최적화 문제의 일종이다. 간략하게 말하자면, 담을 수 있는 최대 무게가 정해진 배낭과 함께 각각의 무게와 가치가 주어진 아이템의 집합이 주어졌을 때, 배낭에 담은 아이템들의 가치의 합이 최대가 되도록 하는 아이템들의 부분집합을 찾는 문제이다. 우리가 흔히 쓰는 배낭 문제는 Fraction Knapsack Problem 0-1 Knapsack Problem 이 2가지가 존재한다. Fraction Knapsack Problem (분할 가능한 배낭 문제) with Greedy Algorithm 내가 배낭 문제를 처음 접했을때 든 생각은 "어 이거 그리디 알고리즘 아닌가?" 였다. 그리디 알고리즘에서 가장 유명한 문제인 동전 거스름돈 문제는 일단 거스름돈으로 사용할 500원, 1..

백트래킹이란? 백트래킹이란 원하는 값을 찾는 도중 현재 대상이 원하는 값이 아닐때, 더 이상 그 대상을 탐색하지 않고 전 단계로 돌아가서 원하는 값을 푸는 방식이다. 우리가 가장 많이 사용하는 방식인 DFS, BFS가 바로 백트래킹에 속한다고 한다. DFS, BFS가 바로 백트래킹에 속한다고 한다. 사실 이 말은 매우 불친절한 말이다. 백트래킹이 무엇인가에 대해 의문점이 생겨서 많은 게시글들을 참고하고 여기저기를 뒤져본 결과 나름 내가 내려본 결론은 백트래킹은 DFS 나 BFS에서 조건문을 통해 우리가 찾고자 하는 값이 절대 아닌 것들은 탐색하지 않고 우리가 찾고자 하는 값이 있는 것들만을 탐색하여 우리가 원하는 값을 찾는 방식이라고 생각한다. 이해를 돕기위한 예로 유명한 백트래킹 문제를 가져와 보겠다...

플로이드 워셜 알고리즘이란? 플로이드 워셜 알고리즘은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다. 이전에 배웠던 다익스트라 알고리즘은 한 노드에서 가능한 모든 노드 쌍에 대해 최단 거리를 구했기 때문에 이 점이 2가지의 알고리즘에 차이라고 할 수 있다. 플로이드 워셜 알고리즘의 시간 복잡도는 O(N³)으로 3중 for문으로 보통 모든 경우의 수를 비교한다. 플로이드 워셜 알고리즘의 핵심은 거쳐가는 정점을 기준으로 최단 거리를 구하는 것이다. 그래서 k를 두어서 모든 노드에 대해서 최단 거리를 구할 수 있도록 하였다. fun floydWarshall() { val d = Array(4) { IntArray(4) } for (i in 0 until 4) { for (j in 0 ..

다익스트라 알고리즘이란? 다익스트라 알고리즘은 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는알고리즘이다. 가능한 적은 비용으로 가장 빠르게 해답에 도달하는 경로를 찾아내는 대부분의 문제에 응용된다. 처음 고안되었을때의 다익스트라 알고리즘은 O(N²)의 시간복잡도를 가진다. 이후에 PriorityQueue 를 이용해서 O(NlogN) 까지 시간복잡도를 줄이는 방식이 고안되었다. 다익스트라 알고리즘은 다음과 같다. (P[A][B]는 A와 B 사이의 거리라고 가정한다. 출발점으로부터의 최단거리를 저장할 배열 d[v]를 만들고, 출발 노드에는 0을, 출발점을 제외한 다른 노드들에는 매우 큰 값 INF를 채워 넣는다. (정말 무한이 아닌, 무한으로 간주될 수 있는 값을 의미한다.) 보통은 최단거리 ..

브루트 포스(Brute Force) 알고리즘이란? 우리가 완전탐색이라고도 부르는 브루트 포스 알고리즘은 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법이다. 엄청난 시간이 걸리는 데다 자원이 엄청나게 들어 무식한 방법이라고 할 수 있지만 100%로 완전 탐색할 수 있다는 장점이 있다. 이론적으로 가능한 모든 경우의 수를 다 검색하보는 것이라 암호학에서는 가장 확실한 방법으로 통용되고 있다. 브루트 포스는 크게 선형 구조와 비선형 구조로 나눌 수 있다. 선형 구조: 순차 탐색 비선형 구조: 백트래킹, DFS, BFS 우리는 이런 구조를 가지고 많은 알고리즘 문제를 해결해야 한다. 그러므로 우리는 이런 구조에 대한 이해를 확실하게 해서 해당하는 알고리즘 문제에 가장 알맞은 구조를..