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(log⁡N)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..

3.4 MANIPULATING BIG-O

3.4 MANIPULATING BIG-O 171. Prove that if $f_i(n) = O(g_1(n))$ and $f_2(n) = O(g_2(n))$, then $f_1(n) + f_2(n) = O(g_1(n)+g_2(n))$. $$ \begin{aligned} f_1(n) &\leq c_1 \cdot g_1(n) \\ f_2(n) &\leq c_2 \cdot g_2(n) \\ \end{aligned} $$ 일 때 $$ \begin{aligned} f_1(n) + f_2(n) = O(g_1(n)+g_2(n)) \\ f_1(n) + f_2(n) \leq c(g_1(n)+g_2(n)) \end{aligned} $$ 를 증명하자 $$ \begin{aligned} f_1(n) + f_2(n) &\leq ..

3.1 RANK THE FUNCTIONS

3.1 RANK THE FUNCTIONS 98 Consider the following eighteen functions: $\sqrt{n}$ $n$ $2^n$ $n\log n$ $n-n^3+7n^5$ $n^2+\log n$ $n^2$ $n^3$ $\log n$ $n^{1/3}+\log n$ $(\log n)^2$ $n!$ $\ln n$ $n/\log n$ $\log \log n$ $(1/3)^n$ $(3/2)^n$ $6$ Group these functions so that f(n) and g(n) are in the same group if and only if f(n) = O(g(n)) and f(n) = O(f(n)), and list the groups in increasing order. 1...

2.7 FIBONACCI NUMBERS

2.7 FIBONACCI NUMBERS The Fibonacci numbers $F_n$ for ($n \geq 0$) are defined recursively as follows: $F_0 = 0, F_1 = 1$, and for $n \geq 2, F_n = F_{n-1} + F_{n-2}$ 52 Prove by induction on n that $\sum_{i=0}^{n}F_i = F_{n+2} -1$ 52-1. Basis Condition n = 0일 때 성립하는가? $$ \begin{aligned} F_{2} &= F_1 + F_0 \\ &= 1 + 0 = 1 \\ \end{aligned} $$ $$ \begin{aligned} \sum_{i=0}^{n}F_i &= F_{n+2} -1 \\ ..