Algorithm/Algorithm
[Algorithm] 외판원 순회 문제(Traveling Salesman Problem)
[Algorithm] 외판원 순회 문제(Traveling Salesman Problem)
2023.04.06외판원 순회 문제(TSP) 외판원 순회 문제(TSP)는 조합 최적화 문제 일종으로, NP-난해 집합에 속하기 때문에 계산 이론에서 해를 구하기 어려운 문제의 대표적인 사례로 많이 다룬다. 즉, 아직까지 다항 시간에 해결할 수 있는 해결책을 못찾았으며 해결하지 못한다는 것도 증명하지 못했다. 외판원 문제의 내용은 다음과 같다. 예를 들어, 어떤 외판원이 n개의 도시를 방문할 계획을 갖고 있다고 하자. 각 도시는 다른 모든 도시와 도로로 연결되어 있다. 출장 비용을 최소로 줄이기 위해 외판원이 출발하는 도시에서 각 도시를 한 번씩만 방문하고 다시 출발한 도시로 돌아오는 가장 최소 비용의 경로를 찾고자 할 때, 어떻게 찾을 수 있을까? 만약 20개의 도시가 있을 때 정답을 찾기 위해 다녀야 하는 총 경로 수는..
[Algorithm] 보이어-무어 알고리즘(Boyer-Moore Algorithm)
[Algorithm] 보이어-무어 알고리즘(Boyer-Moore Algorithm)
2023.04.04보이어-무어 알고리즘(Boyer-Moore Algorithm) 보이어-무어 알고리즘은 문자열 검색에 사용되는 알고리즘이다. 보이어-무어 알고리즘은 일반적인 상황에서 문자열은 앞부분보다 뒷부분에서 불일치가 일어날 확률이 높다는 성질을 활용한다. 때문에 오른쪽 끝부터 비교하게 된다. 보이어 무어 알고리즘은 다음과 같이 이동할 칸의 개수를 저장해 놓은 테이블을 미리 만들어 저장해 놓는다. 오른쪽 끝과 일치하지 않는 경우 오른쪽 끝 문자가 일치하지 않는다면, 패턴에 해당 문자가 존재하는지 검사한다. 만약 패턴에 존재하지 않는다면, 패턴의 길이만큼 패턴을 이동시킨다. 만약 패턴에 존재한다면, 패턴의 오른쪽 끝에서부터 그 문자까지의 칸 수를 세서, 해당 칸수만큼 이동시킨다. 오른쪽 끝과 일치하는 경우 오른쪽 끝 문..
[Algorithm] 벨만-포드 알고리즘(Bellman-Ford Algorithm)
[Algorithm] 벨만-포드 알고리즘(Bellman-Ford Algorithm)
2023.03.30벨만-포드 알고리즘(Bellman-Ford Algorithm)? 벨만-포드 알고리즘은 한 정점에서 다른 정점까지의 최단 거리를 구하는 알고리즘이다. 특징 벨만-포드 알고리즘의 시간 복잡도는 O(VE)로, O((V+E)logV)인 다익스트라보다 시간 복잡도가 더 크지만, 다익스트라는 가중치가 음수인 경우에는 사용할 수 없다. 반면, 벨만-포드 알고리즘은 가중치가 음수인 경우에도 사용할 수 있기 때문에 음수인 가중치가 존재한다면 벨만-포드 알고리즘을 사용할 필요가 있다. 구현 P[A][B]는 A와 B사이의 거리라고 가정한다. 출발점으로부터 최단거리를 저장할 배열 d[v]를 만들고, 출발 노드에는 0을, 출발점을 제외한 다른 노드들에는 매우 큰 값 INF를 채워 넣는다. 실무에서는 보통 d의 원소 타입에 대한..
[Algorithm] 페르마의 소정리
[Algorithm] 페르마의 소정리
2023.03.18페르마의 소정리? 페르마의 소정리는 피에르 드 페르마가 알아낸 정리로서, 정수론의 가장 기본이 되는 정리이다. 이 내용을 간단히 말하면, 임의의 소수 p와 서로소인 수 a에 대해, a^(p-1)을 p로 나눈 나머지는 무조건 1이라는 말이다. 예를 들어, 3^6 = 729를 7로 나누면 나머지는 1이라는 사실을 알 수 있다. 증명 이항정리를 사용한 증명 먼저 페르마의 소정리는 다음과 동치이며, n = 0일 경우는 자명하다. 이항정리에 의하면 여기서, 0 < n < p이면 은 p의 배수이다. 따라서, 는 항상 성립하는 명제이다. 같은 방법으로 도 항상 성립한다. 따라서 n일 때 성립한다 가정하면, n+1, n-1일 때도 성립한다. 즉, 모든 정수 n에 대해 이 공식이 성립한다는 것을 알 수 있다. 기약잉여계..
[Algorithm] 플로이드-워셜(Floyd-Warshall)
[Algorithm] 플로이드-워셜(Floyd-Warshall)
2023.03.12플로이드-워셜(Floyd-Warshall)? 플로이드-워셜은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다. 다익스트라 알고리즘과는 달리 모든 노드 쌍에 대해 최단 거리를 구하고, 음의 가중치를 가지는 그래프에서도 쓸 수 있다는 것이 특징이며 다익스트라보다 구현이 쉽다. 플로이드-워셜은 모든 지점에서 다른 모든 지점까지의 최단 거리를 저장해야하기 때문에 2차원 배열에 최단 거리 정보를 저장한다. 또한, DP의 특징을 가지고 있어서 노드의 개수(N)번 만큼의 단계를 반복하며 점화식에 맞게 2차원 배열을 갱신해나간다. 구현 설명 플로이드-워셜은 임의의 노드 s에서 e까지 가는데 걸리는 최단거리를 구하기 위해, s와 e 사이의 노드인 m에 대해 s에서 m까지 가는 데 걸리는 최단거리와..
[Algorithm] 상계/하계(Upper Bound/Lower Bound)
[Algorithm] 상계/하계(Upper Bound/Lower Bound)
2023.03.11상계/하계(Upper Bound/Lower Bound)? Lower Bound와 Upper Bound는 이진 탐색을 기반으로 하여 경곗값을 찾는 알고리즘이다. 이진 탐색을 기반으로 하기 때문에 당연히 데이터가 정렬되어 있어야 한다. 값을 찾을 때, 원하는 값이 없을 때 못찾았다는 신호(-1, false 등)를 반환하는 일반적인 이진 탐색과 달리 Upper Bound와 Lower Bound를 이용하면 찾고자 하는 값 또는 그 값의 초과값이 처음 나타나는 위치를 찾을 수 있다. 때문에 주로 특정 값을 어느 위치에 삽입해야 하는지 탐색할 때 많이 사용한다. 상계 (Upper Bound) Upper Bound는 찾고자 하는 값(target)보다 큰 값의 처음 위치를 반환한다. 구현 public class Upp..
[Algorithm] 이진 탐색(Binary Search)
[Algorithm] 이진 탐색(Binary Search)
2023.03.11이진 탐색(Binary Search)? 이진 탐색이란 데이터가 정렬되어 있는 상태에서 탐색 범위를 줄여나가며 특정한 값을 탐색하는 알고리즘으로, 탐색할 때마다 탐색 범위가 반으로 줄어들기 때문에 속도가 빠르다는 장점이 있다. 구현 코드 public class BinarySearch { public static void main(String[] args) { int[] array = {1, 3, 4, 6, 7, 9, 10, 11, 14, 16, 17, 20}; int target = 16; int left = 0; int right = array.length - 1; while (left right가 되므로 종료한다) 시간 복잡도 선형 탐색의 경우 O(n)이지만 이진 탐색의 경우 O(log n)이므로 대부..
[Algorithm] 모듈러 산술(modular Arithmetic)
[Algorithm] 모듈러 산술(modular Arithmetic)
2023.03.09모듈로(Modulo) 연산 컴퓨팅에서 어떤 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산으로, 나머지 연산(mod)이라고 한다. 즉 일반적으로 정수 범위의 내에서 대부분 a를 n으로 나눈 나머지 r과 몫 q는 다음을 충족한다. 일반적으로 a와 n이 모두 정수인 상태에서 수행되지만 요즘은 많은 곳에서 정수 범위 이상의 피연산자를 사용할 수 있다. 하지만, mod 0은 Divide by Zero 에서 예외가 발생할 수 있기 때문에 주의해야한다. 이 모듈로 연산에 관련된 규칙이 모듈러 산술이다. 모듈러 산술(Modular Arithmetic) 모듈로 합동(Congruence Modulo) 두 정수 a, b와 정수 n (n > 1)이 주어질 때 n이 a, b의 차의 약수인 경우 (즉, a - b = kn을 ..
[Algorithm] 위상 정렬(Topological Sort)
[Algorithm] 위상 정렬(Topological Sort)
2023.03.07위상 정렬(Topological Sort)? 위상 정렬은 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘으로, 비순환 방향 그래프(DAG)에서 정점을 선형으로 정렬하는 것이다. 실생활을 예로 들면, 인터넷 검색을 하기 위해선 다음과 같은 순서로 행동해야한다. 컴퓨터 전원 키기 -> 브라우저 키기 -> 검색 엔진 포털 진입 -> 검색 위 순서가 바뀐다면 검색을 할 수 없을 것이다. 위상 정렬은 모든 간선 (u, v)에 대해 정점 u가 정점 v보다 먼저 오는 순서로 정렬이 된다. 그래프가 DAG가 아닌 경우 그래프에 대한 위상 정렬은 불가능하다. 여기서 주의할 점은 E가 수행되기 위해선 B와 D가 모두 수행되어야 한다는 점이다. 비순환 방향 그래프 (DAG: Di..
[Algorithm] 프림 알고리즘(Prim's algorithm)
[Algorithm] 프림 알고리즘(Prim's algorithm)
2023.02.28프림 알고리즘(Prim's algorithm)? 프림 알고리즘은 임의의 정점부터 시작하여 해당 정점에 연결된 가장 작은 가중치의 간선을 선택하며 확장해나가서 최소 신장 트리를 만드는 알고리즘이다. 구현 탐색을 시작할 임의의 정점을 하나 선택한다. 선택한 정점과 인접하는 정점 중 최소 비용의 간선을 갖는 정점을 선택한다. 모든 정점이 선택될 때 까지(n-1 개의 간선을 가질 때 까지) 반복한다. 동작 과정 코드 다음 코드는 baekjoon: 1197 - 최소 스패닝 트리를 기준으로 작성하였다. 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B..
[Algorithm] 다익스트라(Dijkstra)
[Algorithm] 다익스트라(Dijkstra)
2023.02.26다익스트라(Dijkstra)? 다익스트라(Dijkstra) 알고리즘은 에츠허르 다익스트라가 고안한 알고리즘으로, 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 대표적인 최단 경로 알고리즘이다. 특징 그래프 방향의 유무는 상관 없으나, 간선들 중 하나라도 가중치가 음수이면 이 알고리즘은 사용할 수 없다. 음의 가중치를 가지는 간선이 있으며, 가중치 합이 음인 사이클이 존재하지 않는 경우 벨만-포드 알고리즘을 사용할 수 있다. 또한 그래프 내에 가중치 합이 음인 사이클이 존재한다면 무한히 음의 사이클을 도는 경우 경로 합이 음수 무한대로 발산하기 때문에 그래프 내의 최단 경로는 구성할 수 없다. 구현 P[A][B]는 A와 B사이의 거리라고 가정한다. 출발점으로부터 최단거리를..
[Algorithm] 크루스칼 알고리즘 (Kruskal Algorithm)
[Algorithm] 크루스칼 알고리즘 (Kruskal Algorithm)
2023.02.19크루스칼 알고리즘 (Kruskal Algorithm)? 크루스칼 알고리즘은 그래프 내의 모든 간선의 가중치를 확인하고 가장 작은 가중치부터 확인해서 최소 신장 트리를 만드는 알고리즘으로, 탐욕적인(greedy) 방법을 통해 구현할 수 있다. greedy? 그 순간에 가장 좋다고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 것 그 순간에는 최적이지만, 전체적인 관점에서 최적이라는 보장이 없기 때문에 반드시 검증해야 한다. 크루스칼 알고리즘은 최적의 해답을 주는 것으로 증명되어 있다. 구현 그래프의 간선들을 가중치의 오름차순으로 정렬한다. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다. 가장 낮은 가중치를 먼저 선택한다. 사이클을 형성하는 간선을 제외한다. 해당 간선을 현재의..