Algorithm
분할 정복 알고리즘
도입분할 정복과 일반적 재귀 호출의 차이일반적 재귀 호출문제를 한 조각과 나머지 전체로 나눔분할정복문제를 항상 거의 같은 크기로 나눔 일반적 재귀 호출분할 정복분할 정복의 구성 요소divide문제를 더 작은 문제로 분할하는 과정merge각 문제에 대해 구한 답을 원래 답으로 병합하는 과정base case매우 작은 문제의 해법예제: 수열의 빠른 합과 행렬의 빠른 제곱가장 간단한 방법은 수식을 이용하여 바로 계산하는 것이다.하지만, 우리는 분할 정복 알고리즘에 익숙해지기 위해 이를 이용하여 계산해보자 1+2+…+n 의 합을 분할 정복을 이용하여 계산해보자 문제를 반으로 나눠보기1부터 n2n\over22n까지의 합과 n2+1{n\over2}+12n+1부터 n까지의 합을 구하는 문제로 나눠보자sum(n)..
유클리드 알고리즘
유클리드 알고리즘💡두 수의 최대공약수를 구하는 방법정의두 수 p, q(p>q)의 공약수 집합은 p-q와 q의 공약수 집합과 같다. 증명p, q의 공약수 g가 존재한다고 해보자그럼 다음과 같이 나타낼 수 있다.p = p’gq = q’g 이때 p-q = (p’ - q’)g 이므로g는 p-q의 약수이며, q의 약수이다. 구현위를 이용하여 코드로 구현해보자int gcd(int p, int q) { if (p < q) { int tmp = q; q = p; p = tmp; } if (q == 0) { return p; } return gcd(p - q, q); }짧은 코드로 구현이 가능하나, 위 코드를 보면 p와 q의 차이가 클 경우에 많은 연산이 이루어 질 수 있다는 단점이 있다.gcd(1024,6)=gcd(1..
소수 판별
소수 판별💡양의 약수가 1과 자기 자신 2개 뿐인 자연수소수가 아닌 수는 합성수이다.가장 단순한 방법2부터 n-1까지 모든 수를 돌면서 나머지가 0이 아니면 소수이다.조금 더 발전한 방법합성수는 n = p*q (p, q ≠ 1, n) 형태로 나타낼 수 있다. 이때 (p≤q) 일때 p는 항상 √n 이하이고 q는 항상 √n 이상이다.따라서 범위를 n-1까지가 아니라 √n 까지 줄일 수 있다.코드// 자연수 n이 소수인지 판별한다. static boolean isPrime(int n) { // 1과 2는 예외처리 if (n
플로이드 최단 경로 알고리즘
플로이드 최단 경로 알고리즘💡모든 정점 쌍에 대해 최단 거리를 구할 때 쓰는 알고리즘개요board[u][v]정점 u에서 정점 v까지의 최단거리를 저장최단 거리를 찾는 방법정점 u에서 정점 v까지 바로 가는 거리를 w(u, v)라고 하자이 때, u→a→v를 가는 거리가 u→v 거리보다 짧다면 갱신하는 방식이다.코드public class 플로이드 { static int board[][]; static void floyd() { // 자기 자신의 거리는 0 for (int i = 0; i < board.length; i++) { board[i][i] = 0; } // 거리 계산하기 for (int k = 0; k < board.length; k++) { for (int i = 0; i < board.lengt..
벨판-포드의 최단 경로 알고리즘
벨판-포드💡다익스트라의 음수 간선 문제를 해결한 최단 경로 알고리즘다익스트라와의 차이벨판-포드는 시작점에서 각 정점까지 가는 최단 거리의 상한을 적당히 예측한 뒤 예측 값과 실제 최단 거리 사이의 오차를 반복적으로 줄이는 방식동작 과정upper[]시작지점으로부터 각 정점까지 최단 거리의 상한시작점→시작점의 거리는 0나머지는 매우 큰 수로 저장시작점이 아닌 임의의 두 지점 u, vdist[u]시작지점 → u 까지의 최단 거리dist[v]시작지점 → v 까지의 최단 거리이때, 다음이 성립한다.dist[v] ≤ dist[u] + w(u, v)dist[u] ≤ upper[u]upper[u] + w(u, v) ≤ upper[v]종료 조건과 정당성의 증명어떻게 upper[] 의 값을 dist[] 값으로 만들 수 있..
이진 검색 트리
1. 이진 검색 트리란?💡자료들을 일정한 순서에 따라 정렬한 상태로 저장해두는 트리사용 예시캐릭터 생성 시 특정 닉네임이 이미 저장되어있는지 확인하기나보다 1등 위인 사람과 1등 아래인 사람을 찾기 대부분 언어 표준 라이브러리에서 제공하기 때문에, 직접 구현하지 않는다.2. 이진 검색 트리의 정의와 조작2-1. 이진트리란?💡한 노드당 최대 2개의 자식 노드만 가질 수 있는 트리따라서 관련 객체 작성 시 다음처럼 구현이 된다.class Node { int data; Node left, right; }2-2. 이진 검색 트리의 특징N개의 원소 중에서 원하는 원소를 찾기까지 걸리는 시간은 다음과 같다.O(logN)O(\log{N})O(logN)시간이 logN이 걸리기 위해선 노드들이 특별한 방식으로 저장될 ..
동적 계획법
동적 계획법이 뭔데?분할 정복에서 중복 부분문제를 캐시(cache)를 이용하여 계산 결과를 재활용하여 속도 향상을 꾀하는 기법이다.예시피보나치 수열의 [i]번째 결과값을 출력하고싶다고 하자.해당 메소드는 fibo(i)를 이용하여 값을 얻는다.int fibo(int i){ // 기저사례 if(i == 0 || i == 1){ return 1; } if(cache[i] != -1){ return cache[i]; } cache[i] = fibo(i-1) + fibo(i-2); return cache[i]; }초기 cache 상태는 다음과 같다.fibo(4)는 fibo(3) + fibo(2) 연산이 이루어진다.fibo(3)에서는 fibo(2) + fibo(1) 연산이 이루어진다.fibo(2)에서는 fibo(1..
문자열 알고리즘
용어 정리 |S| 문자열 S의 길이 S = “abcde” 라면 |S| = 5 S[i] (0 ≤ i < |S|) 문자열 S의 i번 글자 S = “abcde” 라면 S[3] = d S[i…j] 문자열 S[i] 부터 S[j] 까지 부분 문자열 S = “abcde” 라면 S[1…3] = bcd S[…a] 문자열 S[0] 부터 S[a] 까지 부분 문자열 S = “abcde” 라면 S[…3] = abcd S[b…] 문자열 S[b] 부터 S[|S|-1] 까지 부분 문자열 S = “abcde” 라면 S[3…] = de 문자열 검색 긴 문자열 H가 문자열 N을 부분 문자열로 포함하는지 확인하는 방법 H = “avava” N = “ava” 라면 N이 출현하는 모든 인덱스를 반환하는 알고리즘을 작성한다고 하자 이때 결과값은..
[Java] BFS : 너비 우선 탐색
너비우선탐색 개요 너비 우선 탐색은 최초 위치에서 가까운 노드들을 우선적으로 탐색하는 방법이다. 여기서 가깝다는 의미는 가중치가 적은 것이 아니라, 몇 번 만에 도달할 수 있는가를 의미한다. 시간 복잡도 인접리스트로 구현된 경우에는 각 노드마다 모든 간선을 확인해야 하므로, O(|V|+|E|) 입접 행렬로 구현된 경우에는 각 노드마다 다른 노드로 연결되어 있는지 확인해야 하므로, O(|V|^2) 동작 코드 import java.util.LinkedList; import java.util.Queue; import java.util.Vector; public class 너비_우선_탐색 { // 그래프의 인접리스트 static Vector adj; static Vector bfs(int start) { Vec..
[Java] DFS : 깊이 우선 탐색
DFS : 깊이 우선 탐색 개요 그래프의 모든 정점을 특정한 순서로 탐색하는 그래프의 탐색 알고리즘 중 하나이다. 정점 1로부터 시작해서 모든 정점을 탐색하기 위한 목적이다. 현재 지점으로부터 인접한 지점을 찾아야 하므로 "재귀" 를 사용한다. 현재 방식은 단순히 "탐색" 만 할 뿐이며, D, F 등의 계산은 하지 않는다. 탐색의 우선순위는 정점의 번호가 작은 순이다. 파란색 정점은 방문 했다는 표시이다. 주황색 정점은 방문한 뒤 되돌아온다는 표시이다. 동작 코드 import java.util.Vector; public class 깊이_우선_탐색 { // 그래프의 인접 리스트 표현 static Vector adj; // 각 정점을 방문했는지 여부를 나타낸다. static Vector visited; //..