For a better world

가우스 소거법을 이용하여 연립 방정식의 해를 구하는 과정이며, 아래에서 $R_2$는 2열을 의미한다.

Reference

[1] http://blog.naver.com/PostView.nhn?blogId=alwaysneoi&logNo=100194836897

개요

중국인의 나머지 정리의 경우 연립 합동식의 해의 존재성과 유일성을 증명하는 정리이며 그 기원은 다음과 같다.

중국의 5세기 문헌인 『손자산경(孫子算經)』에는 다음과 같은 문제가 있다고 한다.

3으로 나누었을 때 2가 남고, 5로 나누었을 때 3이 남고, 7로 나누었을 때 2가 남는 수는 무엇인가?

정의

$gcd(n,m) = 1$면 $\begin {cases} x \equiv b\ (mod\ n) \\ x \equiv c\ (mod\ m) \end {cases}$는 $1 \leq x \leq nm$에서 단 하나의 해를 갖는다.

증명

$x \equiv b\ (mod\ n)$    (1)

$x \equiv c\ (mod\ m)$    (2)

$x \equiv b\ (mod\ n)$이므로 $x = ny + b$를 만족하는 $y \in Z$가 존재할 것이고, 이를 (2)에 대입하면 다음과 같다.

$ny \equiv c -b\ (mod\ m)$

위 정의에 의해 위 합동식은 $1 \leq y \leq m$에서 유일한 해 $y_0$를 갖고, 따라서 $x = ny_0 + b$는 $1 \leq x \leq nm$에서 유일한 해 $x_0$를 가진다. 따라서 다음과 같다.

$x_0 = ny_0 + b$

여기서 $x_0$는 (1)의 해다. 이제 $ny_0 \equiv c -b\ (mod\ m)$에 $ny_0 = x_0 - b$를 대입하면 다음과 같다.

$x_0 \equiv c\ (mod\ m)$

$x_0$은 (2)의 해가 된다. 증명 끝.

Reference

[1] https://namu.wiki/w/중국인의%0나머지%0정리 

[2] https://freshrimpsushi.tistory.com/493

군, 환, 체의 경우 대수학에서 사용되는 개념으로 기본적이면서 가장 중요한 개념으로 여겨진다.

군 환 체 정의

군

공집합이 아닌 집합 G 위에 다음 세 조건을 만족하는 이상연산 $\circ$가 정의될 때 $<G, \circ>$를 군이라 한다.

군의 공리

• 결합법칙 : $G$의 임의의 원소 $a, b, c$에 대해 다음이 성립한다.
  • $(a \circ b)\ \circ \ c\ =\ a\ \circ \ (b \circ c)$

• 항등원 : $G$의 모든 원소 $a$에 대해 다음이 성립하는 $e \in G$가 존재해야하며, 이 때 $e$를 $G$의 단위원 또는 항등원이라한다.
  • $a \circ e\ =\ e\circ a = a$

• 역원 : $G$의 각 원소 $a$에 대해 다음이 성립하는 $a^{-1}이 $G$에 존재해야 하며, 이 때 $a^{-1}$를 $a$의 역원이라한다.
  
  • $a \circ a^{-1} = a^{-1} \circ a = e$

• 닫힘 : 어떤 집합의 임의의 두 원소(순서쌍)간에 연산이 행해질 때, 그 결과 역시 그 집합의 원소가 되는 것을 의미한다.
  • $a \circ b$ 연산의 결과도 집합 $G$에 속하며 순서쌍 $(a,b)$들의 곱(카테시안 곱) 연산에 대해 닫혀있음

군은 결합법칙, 항등원, 역원, 닫힘의 네 가지 특성을 가지고 있어야 한다.

군의 종류

• 가환군 or 아벨군
  • 군의 네 가지 특성에 추가적으로 교환법칙까지 성립할 경우 이를 아벨군(abelian group) 또는 가환군(commutative group)이라 한다.

• 순환군(Cyclic Group)
  
  • 한 원소로 군의 모든 원소를 표시할 수 있는 군을 의미하며, 이 때 해당 원소를 생성원(generator)라 한다.

• 덧셈군(Additive Group)
  
  • 군의 이항 연산이 덧셈 연산인 군

• 곱셉군(Muliplicative Group)
  
  • 군의 이항 연산이 곱셈 연산인 군

• 부분군(Subgroup)
  • 군 $G$의 부분집합으로 군 $G$와 같은 연산 구조를 가지는 군

군의 표기

• $(G, \circ)$ 또는 $<G, $circ>$ 또는 ${G, \circ}$
  • $G$: 군의 원소 집합
  • $\circ$ : 군의 연산
• 군의 차수/위수(order): $|G|$ 또는 $O(g)$ 또는 $G_n$ 또는 $ord(G)$로 나타낼 수 있다.

환

어떤집합 R 및 그 집합 위에 2개의 이항연산$(+, \circ)$이 정의되는 대수 구조를 의미하며 다음과 같이 표기한다.

• $(R, +, \circ)$ 또는 $< R, +, \circ>$ 또는 $환 R$

환의 공리

• 덧셈 연산에 대해 : $(R, +)$는 가환군
  • 닫혀 있음
  • 항등원(`0`)이 존재 $\rightarrow a + 0 = 0 + a = a$
• 각 성분에 대해 역원이 존재함$\rightarrow a + (-a) = (-a) + a = 0$

• 모든 성분에 대해 교환법칙이 성립 $\rightarrow a + b = b + a$

• 모든 성분에 대해 결합법칙이 성립 $\rightarrow (a + b) + c = a + (b + c)$

• 곱셈(\circ) 연산에 대해 : $(R, \circ)$
  • 닫혀 있음
  • 모든 성분에 대해 결합법칙이 성립 $\rightarrow (a\circ b)\circ c = a\circ (b\circ c)$
• 덧셈 및 곱셉 연산에 대해 : $(R, +, \circ)$
  • 모든 성분에 대해 분배법칙이 성립 $\rightarrow a\circ (b + c) = a\circ b + a\circ c, (a + b)\circ c = a\circ c + b\circ c$

추가적인 조건에 따른 환의 종류

• 가환환
  • 추가적으로 곱셈(\circ)에 대해서 가환이 되는 환 : $a \circ b = b \circ a)$

• 단위원을 갖는 환(Ring with Unity)
  • 추가적으로 곱셈 항등원 즉, 단위원을 갖는 환 : $1 \circ a = a \circ 1 = a$

• 나눗셈환
  • 단위원 1을 갖는 환으로써, 곱셈 역원이 존재하는 환 : 각 원소 $a \in R, a \neq 0$에 대해, $a \circ a^{-1} = a^{-1}\circ a = 1$

• 정역(Integraldomain)
  • 단위원 1을 갖는 가환환으로써, 추가적으로 다음 조건을 만족
    • $a \neq 0, b \neq 0$이면 $a \circ b \neq 0$을 만족함 또는
    • $a \circ b = 0$이면, $a = 0$ 또는 $b = 0$ $(a,b \in R)$

체

• 코드(부호) 등을 기술하는데 사용될 수 있는 수학적 대수 구조
  • 예) 실수 $R$, 유리수 $Q$, 복소수 $C$와 같은 수 체계에 대한 추상화
• 특정한 성질을 만족하는 2개의 연산이 정의되는 가환환
  • 그 요소들이 집합을 이루면서, 덧셈과 곱셈 연산 두 쌍을 사용할 수 있는 구조(2개 산술연산자)

체의 공리

• 덧셈 연산에 대해 : $<F, +>
  • 집합 내 원소의 연산 결과가 다시 그집합 내에 있게된다. $\rightarrow\ 닫혀있음
  • 항등원 (`0`)이 존재 : $a + 0 = a = 0 + a$
  • 모든 성분에 대해 덧셈 역원이 존재 : $a + (-a) = 0 = (-a) + a$
  • 모든 성분에 대해 결합법칙이 성립 : $(a + b) + c = a + (b + c)$
  • 모든 성분에 대해 교환법칙이 성립 : $a + b = b +a$
• 곱셈 연산에 대해 : $<F, \circ>$
  • 모든 성분에 대해 분배법칙이 성립 : $a (b +c) = a b + a c$

위 체의 공리에서 덧셈 공리들 만을 만족할 경우는 아벨군 또는 가환군이며, 곱셈의 역원 존재 만을 제외한 나머지 공리들을 만족하는 경우는 환이다.

체의 공리가 성립하는 예제

• 실수체 : 실수 전체의 집합
• 복소수체 : 복소수 전체의 집합
• 유리수체 : 유리수 전체의 집합

유한개의 원소를 갖는 체 $\rightarrow$ 유한체(갈로이스체)

Reference

[1] https://booolean.tistory.com/300

확장 유클리드 알고리즘

$x, y$에 대한 부정방정식 $ax + by = c$는 $c$의 값이 $gcd(a,b)$의 배수일 때만 정수 해를 가진다 알려져있다. 즉, $ax + by = c$가 정수 해를 가지는 $c$의 최솟값이 $gcd(a,b)$가 되는 것이다. 따라서 확장 유클리드 알고리즘은 $a,b$의 최대공약수를 구하는 것에 더 나아가, $ax + by = gcd(a,b)$를 만족하는 정수 해 $x,y$도 구하는 알고리즘이라할 수 있다. 즉, 다음과 같다.

• 확장 유클리드 호제법을 이용하면 $ax + by = gcd(a,b)$의 해가 되는 정수 $x, y$ 짝을 찾아낼 수 있다. 특히 $a,b$가 서로소$(gcd(a,b)=1)$인 경우 유용한데, 이와 같을 경우 $ax + by = 1$이 되고, 여기서 a는 모듈러 연산의 곱의 역원이 되기 때문이다.

유클리드 확장 알고리즘 증명

유클리드 확장 알고리즘 증명에 앞서 먼저 유클리드 알고리즘은 다음과 같다.

두 양의 정수 a,b의 최대공약수 $gcd(a,b)$는 다음과 같은 절차를 거쳐 구할 수 있다.

$r_0 ← a$

$r_1 ← b$

$r_{i+1} = r_{i-1} - q_i r_i$

$q_i = r_{i-1} \div r_i$

만약 $r_{i+1} = 0$이라면, $r_i$가 바로 $gcd(a,b)$이다.

확장 유클리드 알고리즘의 경우 최대공약수 이외에도 다음을 만족하는 두 개의 정수 $s, t$를 추가로 구할 수 있다.

$sa + tb = gcd(a,b)$

초기 조건은 다음과 같다.

$s_1 = 1,\ s_2 = 0$

$t_1 = 0,\ t_2 = 1$

$r_1 = a,\ r_2 = b$

$as_i + bt_i = r_i\ \ for\ i = 0,1$

초기 조건을 대입하여 확인할 수 있으며, $i >$ 1일 때 참이라 가정하고 수학적 귀납법을 사용하면 다음과 같다.

$r_{i+1} = r_{i-1} -r_iq_i$

$= (as_{i-1} + bt_{i-1}) - (as_i+bt_i)q_i$

$= a(s_{i-1}-s_iq_i)+b(t_{i-1}-t_iq_i)$

$= as_{i+1}+bt_{i+1}$

따라서 $r_{i+1} = 0$일 때, $as_i + bt_i = r_i$는 $sa + tb = gcd(a,b)$가 된다.

모듈러 연산에서 곱셈에 대한 역원 구하기

법 $m$에 대한 모듈러 연산에서 정수 $a$의 곱셈에 대한 역원 $a^{-1}$은 다음을 만족하는 정수 $x$로 정의한다.

$ax \equiv 1\ (mod\ m)$

모듈러 연산의 정의에 의해 $ax - 1 = -my$를 만족하는 정수 $y$가 존재해야하며 이는 다시 말해 다음을 만족하는 정수$x, y$가 존재해야 한다는 의미이다.

$ax + my = 1$

$a$와 $m$의 최대공약수가 1, 즉 서로소이면 해가 존재하고 그렇지 않을 경우 $a^{-1}$은 존재하지 않는다.

그렇다면... (추가 기술 필요)

확장 유클리드 알고리즘 의사코드

#1

function extended_gcd(a, b)
    s <- 0;    old_s <- 1
    t <- 1;    old_t <- 0
    r <- b;    old_r <- a
    while r ≠ 0
        quotient <- old_r div r
        (old_r, r) <- (r, old_r - quotient * r)
        (old_s, s) <- (s, old_s - quotient * s)
        (old_t, t) <- (t, old_t - quotient * t)       
    output "Bézout coefficients:", (old_s, old_t)
    output "greatest common divisor:", old_r
    output "quotients by the gcd:", (t, s)

#2

// 초기화
r1 ← a, r2 ← b

s1 ← 1, s2 ← 0

t1 ← 0, t2 ← 1



// 루프
while(r2 > 0)
{
　q ← r1 / r2

　r ← r1 - q*r2
　r1 ← r2
　r2 ← r

　s ← s1 - q*s2
　s1 ← s2
　s2 ← s

　t ← t1 - q*t2
　t1 ← t2
　t2 ← t
}

Reference

[1] https://codepractice.tistory.com/79?category=885924

[2] https://brilliant.org/wiki/extended-euclidean-algorithm/

[3] https://ko.wikipedia.org/wiki/유클리드_호제법

[4] https://codeonwort.tistory.com/295

[5] https://joonas.tistory.com/25

[6] https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

정의

유클리드 호제법이란 두 정수 사이에 최대공약수(GCD)를 보다 효과적으로 구하는 것으로, 인류 최초의 알고리즘이라 한다. 

두 개 자연수 $A, B$가 있고 $A\ \%\ B = r$이면 다음과 같다. (단, $A > B$)

$GCD(A,B) = GCD(B,r)$

이 때, $A\ \%\ B = r$에 의해 다음과 같은 식이 기본적으로 유도된다.

$A = Bq + r$

증명

두 자연수 $A,B (A > B)$의 최대공약수를 $G$라 하자. $G$는 공약수이므로 두 서로소 $a, b$에 대해 다음 식이 성립한다.

$A = aG, B = bG$

위의 식을 사용하여 $A = Bq + r$에 대입하면 다음과 같다.

$aG = bGq + r$

$r = aG - bGq$

$ r = (a - bq)G$

$A = aG, B = bG$에서 $a, b$가 서로소라면 $G$가 최대공약수이기 때문에 $b, a - bq$가 서로소임을 증명하면 된다.

이를 증명하기 위해서는 가정에 모순을 확인하는 귀류법을 사용하여 해결할 수 있다.

$b$와 $a - bq$가 서로소가 아니라면 두 수는 공약수 $k$를 가지기 때문에 다음과 같이 나타낼 수 있다.

$a - bq = mk$

$b = nk$

위 식의 항을 옮기고 대입하여 정리하는 과정은 다음과 같다.

$a = mk + bq$

$a = mk + nkq$

$a = (m+nq)k$

따라서 다음과 같은 식을 확인할 수 있다.

$a = (m+nq)k$

$b = nk$

하지만 $a$와 $b$는 서로소이나 공약수 $k$를 가지므로 거짓 명제이다.

따라서 $a-bq$와 $b$는 서로소이다.

Reference

[1] https://baeharam.github.io/posts/algorithm/extended-euclidean/

잉여류

잉여류는 정수 $a$와 법 $m$에 대해 합동인 모든 정수의 집합이다.

예를 들어 7을 5로 나누면 2가 남으며 이러한 수는 7, 12, 17, 22, $\dots$가 될 수 있다.

이를 법 5에 ~대한 7의 잉여류/합동류라 표현할 수 있다.

합동의 정의

• 정수론에서는 합동을 $a, b$를 $m$으로 나눈 나머지가 같을 때, $a$와 $b$가 법$(modulo)\ m$에 관하여 합동 (Congruence)이라고 하고, $a \equiv b(mod\ m)$으로 나타낸다.

• 두 정수 $a,b$에 대해서 $a-b$가 $m$의 배수일 때,  $a$와 $b$는 $m$을 법으로 합동(Congruent modulo m)이라한다.

합동의 기본 성질

$a\equiv b(mod\ m)$이고, $c\equiv d(mod\ m)$이면, 다음과 같다.

1. $a + c \equiv b + d(mod\ m)$
2. $ac \equiv bd(mod\ m)$
3. $a^n \equiv b^n(mod\ m)$

기약 잉여계와 완전 잉여계의 정의

• 기약 잉여계
  • $\{a_1, a_2, \dots , a_m \}$가 법 $m$에 대한 완전 잉여계일 때, 여기서 $m$과 서로소인 원소만 모은 집합을 법 $m$에 대한 기약잉여계라 한다.

• 완전 잉여계
  • $\{a_1, a_2, \dots , a_m \}$에서 $a \equiv a_i \pmod{m}$인 $a_i$가 유일하게 있을 때, $\{a_1, a_2, \dots , a_m \}$ 를 완전잉여계라고 한다.

기약 잉여계와 완전 잉여계의 예시

$4$를 예시로 들면, $\{0, 1, 2, 3\}$은 완전잉여계, 그리고 $4$와 서로소가 아닌 $0, 2$를 제외한 $\{1, 3\}$는 기약잉여계가 된다. 기약잉여계가 중요한 이유는, 곱셈의 역원이 있다는 점 때문이다. 예컨대, 6에 대한 완전잉여계 $\{0, 1, 2, 3, 4, 5\}$와 그것의 기약잉여계 $\{1, 5\}$를 생각하자. $\{1, 5\}$의 원소는 모두 곱셈 역원을 갖는다. 그러나, 다른 완전잉여계 원소는 그렇지 않다. 이는, $m$과 $a$가 서로소일 때, 정수 $x,y$가 존재하여 $ax + my = 1$ 즉, $ax \equiv \ 1(m)$이기 때문이다.

역원의 정의

집합 $S$와 이항연산자 *에 대해, 만약 항등원 e가 존재한다고 할 때, S의 원소 a에 대해

$a * b = b * a = e$를 만족하는 $S$의 원소 b가 유일하게 존재할 때, b를 a의 역원이라고 한다.

오일러 정의

기약 잉여계 개념은 정수론에서 오일러의 정의를 증명하는 데 사용된다. 정수론에서 유용하게 쓰이는 정리로, 합동식과 관련이 있다. 페르마의 소정리를 일반화한 것이다.

• $a$와 $n$이 서로소인 양의 정수일 때, $a^{\varphi(n)} \equiv 1(mod\ n)$이다.
  • 여기서 $\varphi(n)$은 $1$부터 $n$까지의 정수 중 $n$과 서로소인 정수의 개수이다. 오일러 피 함수라고도 불린다.

• 양의 정수 $m$에 대하여, $m$ 이하의 자연수 중에서 $m$과 서로소인 정수의 개수를 $\varphi (m)$으로 나타내고 함수 $\varphi : Z→N$ 를 오일러의 $\varphi$ 함수라고 한다.
  
  • $\varphi$ = varphi

또한 오일러 정리는 대표적인 공개키 암호화 방식 중 하나인 RSA의 가장 중요한 이론이 되는 정리이다.
참고로 오일러 공식, 오일러 방정식과는 다른 것이다.

페르마의 소정리

$p$가 소수일 때, $gcd(a, p)=1$인 정수 $a$에 대하여 $a^(p-1) \equiv 1(mod p)$이다.

증명:  오일러 정리에서 $n=p$대입하고, $\varphi (p)=p-1$ 이용하면 증명

Reference

[1] http://blog.naver.com/PostView.nhn?blogId=dlrbtjd86&logNo=113315940

[2] https://namu.wiki/w/기약잉여계

[3] https://schbeom.tistory.com/367

[4] https://minq.tistory.com/90

[5] https://thewiki.kr/w/오일러%20정리

1. 시간 복잡도

1.1 분석 종류

• $T(n)$: Every-case analysis
  • 입력크기(input size)에만 종속
  • 입력값과는 무관하게 결과값은 항상 일정

• $W(n)$: Worst-case analysis
  • 입력크기와 입력값 모두에 종속
  • 단위연산이 수행되는 횟수가 최대인 경우 선택

• $A(n)$: Average-case analysis
  
  • 입력크기와 입력값 모두에 종속
  • 모든 입력에 대해 단위연산이 수행되는 기대치(평균)
  • 각 입력에 대해서 확률 할당 가능

• $B(n)$: Best-case analysis
  
  • 입력크기와 입력값 모두에 종속
  • 단위연산이 수행되는 횟수가 최소인 경우 선택

1.2 시간 복잡도 정의

• Big-O

모든 $n$, $n \geq n_0$에 대해 $f(n) \le c\times g(n)$인 조건을 만족시키는 두 양의 상수 $c$와 $n_0$가 존재하기만 하면 $f(n)=O(g(n))$이다.

예를 들면 $O(n)$: 최악의 경우 $n$번까지 수행되면 프로그램을 끝낼 수 있다.

• Big-Omega

모든 $n$, $n \geq n_0$에 대해 $f(n) \geq c\times g(n)$인 조건을 만족시키는 두 양의 상수 $c$와 $n_0$가 존재하기만 하면 $f(n)=\Omega(g(n))$이다.

예를 들면 $O(n)$: 최소 $n$번은 수행되어야 프로그램을 끝낼 수 있다.

• Theta

모든 $n$, $n \geq n_0$에 대해 $c_1\times g(n) \le f(n) \le c_2\times g(n)$인 조건을 만족시키는 세 양의 상수 $c_1, c_2, n_0$가 존재하기만 하면 $f(n)=\theta(g(n))$이다.

Theta의 경우 $O와\ \Omega$의 교집합이다. 즉, 차수가 같은 문제이다.

• Small-O

모든 $n$, $n \geq n_0$에 대해 $0 \leq f(n) \lt c \times g(n)$인 조건을 만족시키는 두 양의 상수 $c, n_0$가 존재하기만 하면 $f(n)=O(g(n))$이다.

예를 들면 $O(n)$: 최악의 경우에도 n번 미만으로 수행되면 프로그램은 끝낼 수 있다.

$\lim_{x \to \infty}$ $f(x)\over g(x)$ $=0$로 나타낼 수 있다.

Small-O와 Big-O의 차이점은 다음과 같다.

- Big-O는 실수 $c>0$ 중에서 하나만 성립해도 된다.

- Small-O는 모든 실수 $c>0$에 대해서 성립해야 한다.

- Small-O는 Big-O에서 등호를 뺀다.

추가적으로 Small-omega($\omega$)도 존재한다.

1.3 시간복잡도 정의를 이용하여 다음 4개의 문제에 대하 statement의 참, 거짓을 판별하시오 (시간복잡도 계산 문제)

1.4 $8n^2 + \sqrt2 = O(n^2)$임을 보여라.

모든 $n, n \geq n_0$에 대하여 $f(n) \leq c \times g(n)$인 조건을 만족시키는 두 양의 상수 $c$와 $n_0$가 존재하기만하면 $f(n) = O(g(n))$이다.

1. $f(n) = 8n^2 + \sqrt2$

2. $g(n) = n^2$

3. 대입 => $8n^2 + \sqrt2 \leq c \times n^2$

4. $\sqrt2$는 약 1.414

5. $8n^2 + 1.414 \leq c \times n^2$

6. n = 2라 가정하면

7. $32 + 1.414 \leq c \times 4$

8. $33.414 \leq c \times 4$

9. $c \geq 9$

1.5 Big-O, Omega, Theta, small-o의 정의를 이용하여 $5x^3 + 4x^2 + 6x \in \Theta(n^3)$ 임을 보이시오.

1. $g(x) = x^3$

2. $g_2(x) = 6x^3$

3. $x^3 \leq 5x^3+4x^2+6x \leq 6x^3$

2. 프림, 크루스칼, 다익스트라

2.1 비방향 그래프를 보고 크루스칼 알고리즘을 이용하여 최소 비용 신장 트리를 구하는 과정을 단계별로 보이시오

• 크루스칼 알고리즘의 핵심
  • 오름차순
    1. 가중치를 기준으로 간선을 오름차순 정렬
    2. 낮은 가중치의 간선부터 시작해서 하나씩 그래프에 추가
    3. 사이클을 형성하는 간선을 추가하지 않음
    4. 간선의 수가 정점의 수보다 하나 적을 때 MST가 완성
  • 내림차순
    1. 가중치를 기준으로 간선을 내림차순으로 정렬
    2. 높은 가중치의 간선부터 시작해서 하나씩 그래프에서 제거
    3. 두 정점을 연결하는 다른 경로가 없을 경우 해당 간선은 제거하지 않음
    4. 간선의 수가 정점의 수보다 하나 적을 때 MST가 완성

2.2 그래프를 보고 다익스트라 알고리즘을 이용하여 v6를 출발점으로하는 최단 거리를 구하는 과정을 단계별로 보이시오

• 간선의 가중치를 오름차순으로 정렬한다.
• 가중치가 낮은 순서대로 간선을 하나씩 그래프에 추가한다.
• 그래프 내에서 사이클을 형성하는 간선은 추가하지 않는다.
• 간선의 개수가 정점의 개수보다 '1' 작으면 끝낸다.

3. NP, NP-complete

3.1 NP, NP-hard, NP-complete의 정의

• $P$ : 어떤 문제가 주어졌을 때 다항식으로 표현되어 polynomical time 즉, 다항 시간내에 해결 가능한 알고리즘을 의미하며 알고리즘의 복잡도가 $O(n^k)$로 표현되는 문제를 '$P$'라 한다. (복잡도 $O(n^k)$ 이하를 가지는 경우 같은 복잡도 내에 모든 해를 구한다.)

• $NP$ : 어떤 문제가 주어졌을 때 다항식으로 표현될 수 있는지의 여부가 결정되지 않은 문제들을 'NP(Non-deterministic polynomial)'라 한다.

• $NP-Complete$ : NP이면서 동시에 NP-Hard 에 속한다면 그 문제는 'NP-Complete'라 한다. (전수조사가 답)

• $NP-Hard$ : 적어도 모든 NP 문제만큼은 어려운 문제들의 집합이며, 만약 P-NP 문제가 P=NP로 풀린다면 P=NP=NP-Complete이므로 P와 NP는 NP-Hard의 부분집합이 되고, P≠NP인 경우는 P와 NP-Hard는 서로소가 된다. *다항시간 : $T(n) = O(n^k), k$ 는 상수  => $k$가 상수로 고정이 된다면 그 문제는 해결하기 쉬운 문제. 다항시간안에 풀 수 있는 문제이므로.

3.2 해밀턴회로 거리 구하기(그래프가 주어질 때 그래프의 모든 점을 정확하게 한번씩만 지나는 경로가 존재하는가?) (NP-hard)

4. 배열 제시 후 소팅 알고리즘을 사용하여 정렬 과정을 보여라

4.1 Merge sort 알고리즘을 사용하여 8개의 숫자를 정렬하는 과정을 보여라

4.2 각종 정렬 기법들의 장단점과 시간복잡도

5. Divide and Conquer 알고리즘과 Dynamic Programming 알고리즘 차이

5.1 분할 정복법이 비효율적인 경우를 설명하라

5.2 분할 정복법과 동적프로그래밍을 이용하여 이항계수를 구하는 알고리즘 작성 후 두방식의 차이점에 대해 적으시오

• 분할 정복법(Divide and Conquer)
  • 어떠한 큰 문제를 해결하기 위해 큰 문제를 작은 단위의 문제로 나누어 해결하는 방법 (Top-down)
  • 문제의 크기가 충분히 작아질때까지 반복적으로 분할
  • 해결한 작은 문제를 가지고 바로 윗 단계의 문제를 해결해 나가는 방식
  • 대표적인 예로는 Binary Search와 Merge Sort, Quick Sort 등이 있다.

• 동적 프로그래밍(Dynamic Programming)
  • 문제를 작은 인스턴스들로 나누고 Bottom-up 순서로 풀어나가면서 문제의 값을 정해놓고 필요할 때 가져와  문제를 해결하는 방식이다. "기억하며 풀기"라 생각하면 된다.
  • 대표적인 예로는 TSP 문제, 피보나치 수열, 파스칼의 트리 작성 등이 있다.

분할정복법과 동적 프로그래밍의 공통점과 차이점

• 공통점 : 문제를 작은 단위로 나누어 해결
• 차이점 : 분할정복법은 Top-down 방식이며, 동적 프로그래밍은 Bottom-up 방식이다.

5.3 Binomial coefficient를 계산하려할 때 다음을 구해라

• Divide-and-Conquer 방법을 사용하는 pseudo code 작성
• Dynamic Programming 방법을 사용하는 pseudo code 작성
• 위 두 접근 방법의 차이점을 서술

5.4 이항계수 수학적 귀납법으로 증명하고, 동적 프로그래밍으로 알고리즘을 구현하라.

bottom-up 방식

int binomial(int n, int k) 
{
 for (int i=0; i<=n; i++) 
 {
     for (int j=0; j<=k && j<=i; j++) 
     {
         if (k==0 || n==k)
             arr[i][j] = 1;
         else
             arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
     }
 }
 return arr[n][k];
}

6. DFS(Depth First Search)와  BFS(Breadth First Search)의 차이

• DFS, BFS의 의사코드를 작성하고 이들의 차이를 제시한 다음, 간단한 트리를 작성하여 순회하는 것을 보이시오.

8. 행렬을 주고 TSP에 관한 문제

9. Strassen 행렬 알고리즘을 사용하여 2*2 행렬 A,B의 곱 C를 구하라(m1,m2,...,m7)을 사용해야함

9.1 Strassen's Matrix Multiplication 알고리즘에 대해 설명하라

9.2 행렬 곱셉 알고리즘 + 쉬트라센 + 복잡도

아래와 같이 행렬 A,B가 있고 두 행렬의 곱이 행렬 C로 표현한다 가정한다.

$A = \left[ \begin{array}{cc|c} a_{11} & a_{12} \\\\ a_{21} & a_{22} \end{array} \right],\ $ $B= \left[ \begin{array}{cc|c} b_{11} & b_{12} \\\\ b_{21} & b_{22} \end{array} \right],\ $ $C=\left[ \begin{array}{cc|c} c_{11} & c_{12} \\\\ c_{21} & c_{22} \end{array} \right]$

이 때, $A_{ij},B_{ij},C_{ij} \in F^{2^n-1 \times 2^n-1}$ 이다.

따라서 일반적인 행렬의 곱은 다음과 같이 표현할 수 있으며, 총 8번의 곱셈과 4번의 덧셈으로 연산된다.

$C_{11} = A_{11}B_{11} + A_{12}B_{21}$ 
$C_{12} = A_{11}B_{12} + A_{12}B_{22}$ 
$C_{21} = A_{21}B_{11} + A_{22}B_{21}$ 
$C_{22} = A_{21}B_{12} + A_{22}B_{22}$

슈트라센 알고리즘은 행렬의 곱셉을 더하기 연산으로 풀어 각 원소를 구할 수 있는 $M$이라는 연산 행렬로 표현한다. 행렬 $M$은 7번의 곱셈과 10번의 덧셈으로 연산으로 나타낼 수 있으며 아래와 같이 표현한다.

$M_1 = (A_{11} + A_{22})(B_{11}+B_{22})$ 
$M_2 = (A_{21} + A_{22})B_{11}$ 
$M_3 = A_{11} (B_{12}-B_{22})$ 
$M_4 = A_{22}(B_{21}-B_{11})$ 
$M_5 = (A_{11} + A_{12})B_{22}$ 
$M_6 = (A_{21} - A_{11})(B_{11}+B_{12})$ 
$M_7 = (A_{12} - A_{22})(B_{21}+B_{22})$

최종적으로 행렬 C는 행렬 M의 더하기 연산으로 이루어져 있으며 각 원소에 해당하는 방법은 다음과 같다.

$C_{11} = M_1 + M_4 - M_5 + M_7$ 
$C_{12} = M_3 + M_5$ 
$C_{21} = M_2 + M_4$ 
$C_{22} = M_1 - M_2 + M_3 + M_6$

10. 5-Queen 문제를 백트래킹과 상태 설명 트리를 사용하여 해결하라

11. Floyd 알고리즘을 사용하여 W(=D0) 행렬과  D(=D) 행렬을 구하라. W, D를 구하는 과정을 서술하라

11.1 방향 그래프를 보고 플로이드 알고리즘을 이용하여 D와  P를 단계별로 적으시오.

12. 하노이의 탑 알고리즘을 써라

#include <stdio.h>

void HanoiTowerMove(int num, char from, char by, char to)
{
	if (num == 1)
		printf("원반 1을 %c에서 %c로 이동 \n", from, to);
	
	else
	{
		HanoiTowerMove(num - 1, from, to, by);
		printf("원반 %d를 %c에서 %c로 이동 \n", num, from, to);
		HanoiTowerMove(num - 1, by, from, to);
	}
}

int main(void)
{
	// 막대 A의 원반 5개를 막대 B를 경유하여 막대 C로 옮기기
	HanoiTowerMove(5, 'A', 'B', 'C');
	return 0;
}

13. 탐욕적 방법 Greedy Algorithm이 항상 최적의 해를 내지 못하는 경우의 예를 들라

Greedy Algorithm이 사용되는 대표적인 예제로는 "최소 수의 동전으로 거스름돈 거슬러주기" 문제가 있다. 

만약 우리가 마트의 캐셔로 일을 하고 있고, 850원을 거슬러 주어야 할 때 500원 동전 1개와 100원 동전 3개와 50원 동전 1개 총 4개의 동전을 건넴으로써 최소한의 동전을 거슬러 줄 수 있다. 하지만 이렇게 하지 않고 10원짜리 동전 85개를 건네주거나 50원짜리 17개를 건네주는 방법과 같이 다양한 경우의 수가 존재하며 이와 같을 경우 반드시 최적의 해를 내는 것은 아니다.

또한 우리나라의 경우 총 4개의 동전 500원, 100원, 50원, 10원이 있다. 하지만 만약 400원 동전이 발행된다면 400원 동전 2개, 50원 동전 1개를 통해 총 3개의 동전을 거슬러 줄 수 있을 것이다. 가장 최적의 방법이지만, 기존 알고리즘에 따르면 500원 1개, 100원 3개, 50원 1개로 거슬러주게 될 것이다. 이와 같이 탐욕 알고리즘은 항상 최적의 결과를 보장하지 못한다. 

Reference

[1] https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

[2] https://janghw.tistory.com/entry/알고리즘-Greedy-Algorithm-탐욕-알고리즘

1960년대 후반 Strassen이 $O(n^3)$보다 작은 알고리즘을 제시하며 아래와 같은 규칙을 사용한다.

$P = (A_{11} + A_{22})(B_{11} + B_{22})$

$Q = (A_{21} + A_{22})B_{11}$ 
$R = A_{11}(B_{12}-B_{22})$ 
$S = A_{22}(B_{21}-B_{11})$ 
$T = (A_{11}+A_{12})B_{22}$ 
$U = (A_{21}-A_{11})(B_{11}+B_{12})$
$V = (A_{12}-A_{22})(B_{21}+B_{22})$

위의 규칙에서 사용되는 P~V까지를 통해, 덧셈만으로 A 행렬과 B 행렬의 곱인 C 행렬을 찾을 수 있다.

$C_{11} = P + S - T + V$ 
$C_{12} = R + T$ 
$C_{21} = Q + S$ 
$C_{22} = P + R -Q +U$

구체적으로 다시 설명을 하면 다음과 같다.

아래와 같이 행렬 A,B가 있고 두 행렬의 곱이 행렬 C로 표현한다 가정한다.

$A = \left[ \begin{array}{cc|c} a_{11} & a_{12} \\\\ a_{21} & a_{22} \end{array} \right],\ $ $B= \left[ \begin{array}{cc|c} b_{11} & b_{12} \\\\ b_{21} & b_{22} \end{array} \right],\ $ $C=\left[ \begin{array}{cc|c} c_{11} & c_{12} \\\\ c_{21} & c_{22} \end{array} \right]$

이 때, $A_{ij},B_{ij},C_{ij} \in F^{2^n-1 \times 2^n-1}$ 이다.

따라서 일반적인 행렬의 곱은 다음과 같이 표현할 수 있으며, 총 8번의 곱셈과 4번의 덧셈으로 연산된다.

$C_{11} = A_{11}B_{11} + A_{12}B_{21}$ 
$C_{12} = A_{11}B_{12} + A_{12}B_{22}$ 
$C_{21} = A_{21}B_{11} + A_{22}B_{21}$ 
$C_{22} = A_{21}B_{12} + A_{22}B_{22}$

슈트라센 알고리즘은 행렬의 곱셉을 더하기 연산으로 풀어 각 원소를 구할 수 있는 $M$이라는 연산 행렬로 표현한다. 행렬 $M$은 7번의 곱셈과 10번의 덧셈으로 연산으로 나타낼 수 있으며 아래와 같이 표현한다.

$M_1 = (A_{11} + A_{22})(B_{11}+B_{22})$ 
$M_2 = (A_{21} + A_{22})B_{11}$ 
$M_3 = A_{11} (B_{12}-B_{22})$ 
$M_4 = A_{22}(B_{21}-B_{11})$ 
$M_5 = (A_{11} + A_{12})B_{22}$ 
$M_6 = (A_{21} - A_{11})(B_{11}+B_{12})$ 
$M_7 = (A_{12} - A_{22})(B_{21}+B_{22})$

최종적으로 행렬 C는 행렬 M의 더하기 연산으로 이루어져 있으며 각 원소에 해당하는 방법은 다음과 같다.

$C_{11} = M_1 + M_4 - M_5 + M_7$ 
$C_{12} = M_3 + M_5$ 
$C_{21} = M_2 + M_4$ 
$C_{22} = M_1 - M_2 + M_3 + M_6$

Reference

[1] https://loveisaround.tistory.com/entry/알고리즘-스트라센-strassen

[2] https://09ri.tistory.com/30

분할 정복법과 동적 프로그래밍의 정의

• 분할 정복법(Divide and Conquer)
  • 어떠한 큰 문제를 해결하기 위해 큰 문제를 작은 단위의 문제로 나누어 해결하는 방법 (Top-down)
  • 문제의 크기가 충분히 작아질때까지 반복적으로 분할
  • 해결한 작은 문제를 가지고 바로 윗 단계의 문제를 해결해 나가는 방식
  • 대표적인 예로는 Binary Search와 Merge Sort, Quick Sort 등이 있다.

• 동적 프로그래밍(Dynamic Programming)
  • 문제를 작은 인스턴스들로 나누고 Bottom-up 순서로 풀어나가면서 문제의 값을 정해놓고 필요할 때 가져와  문제를 해결하는 방식이다. "기억하며 풀기"라 생각하면 된다.
  • 대표적인 예로는 TSP 문제, 피보나치 수열, 파스칼의 트리 작성 등이 있다.

분할정복법과 동적 프로그래밍의 공통점과 차이점

• 공통점 : 문제를 작은 단위로 나누어 해결
• 차이점 : 분할정복법은 Top-down 방식이며, 동적 프로그래밍은 Bottom-up 방식이다.

분할정복법의 장점, 단점, 특징

• 장점 : 문제를 나누어 해결한다는 특징상 병렬적으로 문제를 해결하는 데 큰 강점이 있다. 
• 단점 : 함수를 재귀적으로 호출함으로 인해 오버헤드가 발생한다. 또한 스택에 다양한 데이터를 보관하고 있어야 하므로 스택오버플로우가 발생한다.
• 특징 : 분할정복법은 보통 재귀함수를 이용하여 구현하는 것이 일반적이나, 재귀호출을 사용하지 않고 스택, 큐 등의 자료구조를 이용하여 구현하기도 한다.

이항 계수

이항계수는 분할 정복과 동적 프로그래밍에서 차이점을 서술하기 위해 자주 사용된다.

또한 이항계수란 $n$개의 원소에서 $r$개의 원소를 선택하는 방법의 수를 나타내며 재귀 프로그래밍의 기초가 된다.
이항계수는 수학에서 $_nC_r$로 나타낼 수 있으며, 이항계수 프로그래밍의 해결 방법은 $_nC_r =\ _{n-1}C_{r-1}\ +\ _{n-1}C_r$의 공식으로 이루어진다.

위 공식을 재귀적으로 구현할 경우 다음과 같다.

int binomial(int n, int k) {
 if (n == k || k == 0)
     return 1;
 else
     return binomial(n - 1, k) + binomial(n - 1, k - 1);
}

 만약 binomical(5,2)를 계산하면 아래와 같이 동일한 문제들을 중복으로 풀게되어, 부분문제의 중복 문제가 발생한다. 즉, 알고리즘의 효율이 떨어지게 된다.

위와 같이 중복 계산으로 인해 효율이 떨어지는 것을 보완하기 위해서는, 하위 문제를 이용하여 최종 결과의 해를 도출하는 동적 프로그래밍 방법으로 접근하여 해결할 수 있다. 이전 계산 결과 값을 메모이제이션을 이용하여 풀면 다음과 같이 작성할 수 있다.

int binomial(int n, int k) {
 if (n == k || k == 0)
     return 1;
 else if (arr[n][k] > -1) /* 배열 arr이 -1로 초기화되어 있다고 가정 */
     return arr[n][k];
 else {
     arr[n][k] = binomial(n-1, k) + binomial(n-1, k-1);
     return arr[n][k];
 }
}

* 메모이제이션(Memoization) : 이차원 배열에 인덱스에 해당하는 중복 조합을 저장 후, 만약 해당 인덱스에 값이 존재할경우(캐싱되었을 경우) 앞서 계산했다고 판단하여 해당 값을 반환함으로써 중복 계산을 줄여주는 기술. 즉, 동일 계산의 반복 수행을 제거한다.

Bottom-up 방식으로 해결할 경우 다음과 같이 작성할 수 있다.

int binomial(int n, int k) {
 for (int i=0; i<=n; i++) {
     for (int j=0; j<=k && j<=i; j++) {
         if (k==0 || n==k)
             arr[i][j] = 1;
         else
             arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
     }
 }
 return arr[n][k];
}

Reference

[1] https://makefortune2.tistory.com/109

[2] https://kimch3617.tistory.com/entry/알고리즘-분할정복법-Divide-and-Conquer

[3] https://jackpot53.tistory.com/130

[4] https://shoark7.github.io/programming/algorithm/3-ways-to-get-binomial-coefficients

[5] https://new93helloworld.tistory.com/91

정렬 알고리즘 복잡도

정렬 알고리즘 특징 및 장단점

• 버블 정렬
  • 장점 : 인접한 값만 계속해서 비교하는 방식으로 구현이 쉬우며, 코드가 직관적이다. n개 원소에 대해 n개의 메모리를 사용하기에 데이터를 하나씩 정밀 비교가 가능하다.
  • 단점 : 최선이든 최악이든 $O(N^2)$이라는 시간복잡도를 가진다. n개 원소에 대해 n개의 메모리를 사용하기에 원소의 개수가 많아지면 비교 횟수가 많아져 성능이 저하된다.

• 힙 정렬 
  • 장점 : 추가적인 메모리를 필요로하지 않으면서 항상 $O(N\times logN)$의 시간 복잡도를 가진다. $O(N\times logN)$인 정렬 방법 중 가장 효율적인 정렬방법이라 할 수 있다. 퀵 정렬의 경우 효율적이나 최악의 경우 시간이 오래걸린다는 단점이 있으나 힙 정렬의 경우 항상 $O(N\times logN)$이 보장된다.
  • 단점 : 이상적인 경우에 퀵정렬과 비교했을 때 똑같이 $O(N\times logN)$이 나오긴 하나 실제 시간을 측정하면 퀵정렬보다 느리다고 한다. 즉, 데이터의 상태에 따라서 다른 정렬들에 비해서 조금 느린편이다. 또한, 안정성을 보장받지 못한다.

• 선택 정렬
  • 장점 : 정렬을 위한 비교 횟수는 많으나 교환 횟수가 적기에, 교환이 많이 이루어져야 하는 상태에서 효율적으로 사용될 수 있으며, 이에 가장 적합한 자료상태는 역순 정렬이다. 즉, 내림차순이 정렬되어 있는 자료를 오름차순으로 재졍렬할 때 적합하다. 
  • 단점 : 정렬을 위한 비교 횟수가 많으며, 이미 정렬된 상태에서 소수의 자료가 추가되면 재정렬할 때 최악의 처리 속도를 보인다.

• 빠른 정렬
  • 장점 : 기준값(Pivot)에 의한 분할을 통해 구현하는 정렬 방법으로, 분할 과정에서 $logN$이라는 시간이 소요되며, 전체적으로 $N\times logN$으로 준수한 편이다.
  • 단점 : 기존값에 따라 시간복잡도가 크게 달라진다(안정성이 없다). 기준값을 이상적인 값으로 선택했다면 $N\times logN$의 시간복잡도를 가지지만, 최악의 기준값을 선택할 경우 $O(N^2)$라는 시간복잡도를 갖게 된다.

• 삽입 정렬
  • 장점 : 최선의 경우 $O(N)$이라는 빠른 효율성을 가지고 있다. 버블정렬의 비교횟수를 줄이기 위해 고안된 정렬이다. 버블정렬의 경우 비교대상의 메모리 값이 정렬되어 있더라도 비교연산을 진행하나, 삽입정렬은 버블정렬의 비교횟수를 줄이고 크기가 적은 데이터 집합을 정렬하는 알고리즘을 작성할 때 효율이 좋다.
  • 단점 : 최악의 경우 $O(N^2)$이라는 시간복잡도를 가지게 된다. 즉, 데이터의 상태와 크기에 따라 성능의 편차가 큰 정렬 방법이다.

• 병합 정렬
  • 장점 : 퀵 정렬과 비슷하게 원본 배열을 절반씩 분할해가면서 정렬하는 정렬법으로써 분할하는 과정에서 $logN$ 만큼의 시간이 소요된다. 즉, 최종적으로 보게되면 $N\times logN$이 된다. 또한 퀵 정렬과 달리 기준값을 설정하는 과정없이 무조건 절반으로 분할하기에 기준값에 따라 성능이 달라지는 경우가 없다. 따라서 항상 $O(N\times logN)$이라는 시간복잡도를 가지게 된다.
  • 단점 : 병합정렬은 임시배열에 원본맵을 계속해서 옮겨주며 정렬을 하는 방식이기에 추가적인 메모리가 필요하다는 점이다. 데이터가 최악인 면을 고려하면 퀵 정렬보다는 병합정렬이 훨씬 빠르기 때문에 병합정렬을 사용하는 것이 많지만, 추가적인 메모리를 할당할 수 없다면 병합정렬을 사용할 수 없기 때문에 퀵을 사용해야 하는 것이다.

• 쉘 정렬
  • 장점 : 삽입정렬의 단점을 보완하고 개념을 확대해서 만든 정렬방법으로, 삽입 정렬에 비해 성능이 우수하며, 어떤 데이터가 제 위치에서 멀리 떨어져있을 경우 여러 번의 교환이 발생하는 버블정렬의 단점을 해결한다.
  • 단점 : 일정한 간격에 따라 배열을 보아야 하며, 간격을 잘못 설정할 경우 성능이 급격히 저하될 수 있다.

• 기수 정렬
  • 장점 : $O(N)$이라는 시간복잡도를 가지는 정렬방법으로 매우 빠른 속도를 가지고 있다.
  • 단점 : 버킷이라는 데이터 전체 크기와 기수 테이블의 크기만큼의 추가적인 메모리가 할당되어야 한다. 

• 카운팅 정렬
  • 장점 : 비교를 하지 않고 정렬하는 방법으로 $O(N)$이라는 시간복잡도를 가지게 된다.
  • 단점 : 숫자 갯수를 저장해야 될 별도의 공간, 또 결과를 저장할 별도의 공간 등 추가적인 메모리가 필요하다.

정렬 알고리즘 장단점 요약

Reference

[1] https://tctt.tistory.com/47

[2] https://yabmoons.tistory.com/250

[3] https://hsp1116.tistory.com/33

[4] https://yaraba.tistory.com/79