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) 보이어-무어 알고리즘은 문자열 검색에 사용되는 알고리즘이다. 보이어-무어 알고리즘은 일반적인 상황에서 문자열은 앞부분보다 뒷부분에서 불일치가 일어날 확률이 높다는 성질을 활용한다. 때문에 오른쪽 끝부터 비교하게 된다. 보이어 무어 알고리즘은 다음과 같이 이동할 칸의 개수를 저장해 놓은 테이블을 미리 만들어 저장해 놓는다. 오른쪽 끝과 일치하지 않는 경우 오른쪽 끝 문자가 일치하지 않는다면, 패턴에 해당 문자가 존재하는지 검사한다. 만약 패턴에 존재하지 않는다면, 패턴의 길이만큼 패턴을 이동시킨다. 만약 패턴에 존재한다면, 패턴의 오른쪽 끝에서부터 그 문자까지의 칸 수를 세서, 해당 칸수만큼 이동시킨다. 오른쪽 끝과 일치하는 경우 오른쪽 끝 문..
[Baekjoon] 1629: 곱셈
[Baekjoon] 1629: 곱셈
2023.03.21문제 a^b % c를 구하는 문제이다. 풀이 내 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Q1629 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] input = br.readLine().split(" "); long a = Long.parseLong(input[0]); long b = Long.parseLong(input[1]); long c ..
[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에 대해 이 공식이 성립한다는 것을 알 수 있다. 기약잉여계..
[Baekjoon] 17626: Four Squares
[Baekjoon] 17626: Four Squares
2023.03.17문제 특정 숫자의 제곱수 합을 구할 때 그 수들의 최소 개수를 구하는 문제이다. 풀이 내 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Q17626 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int[] dp = new int[n + 1]; dp[..
[Data Structure] 이진 탐색 트리(Binary Search Tree)
[Data Structure] 이진 탐색 트리(Binary Search Tree)
2022.08.17이진 탐색 트리(Binary Search Tree)? 이진탐색트리란 다음과 같은 특징을 갖는 이진트리를 말한다. 각 노드에 중복되지 않는 키가 있다. 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다. 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다. 좌우 서브 트리는 각각이 다시 이진탐색트리여야 한다. 이진탐색트리는 이진탐색(Binary Search)과 연결리스트(Linked List)를 결합한 자료구조이다. 이진탐색트리(BST)는 이진탐색의 빠른 탐색 시간과 연결리스트의 빠른 삽입/삭제의 장점들을 가져왔다. 이진탐색은 탐색 시간이 O(log n)으로 빠르지만 삽입/삭제가 불가능하다. 또 연결리스트의 경우, 삽입/삭제는 O(1)이지만..