컴퓨터 알고리즘 중급

컴퓨터 알고리즘 중급

...아묻따 ㄱㄱㄱ

강좌정보	Tacademy강좌링크
학습내용	Graph, Greedy, Dynamic programming 등 컴퓨터 알고리즘 이론을 보다 깊이 있게 학습하고 이해한다. Maximum Flow, Number Theory, String matching 등의 심화 알고리즘 관련 지식을 학습한다.
강사	조호성 박사 (한양대학교 SW융합원)
학습기간	2021.04.27~2021.05.03 + 테스트20문항 이수완료
학습시간	05:19:40
강의목록	[1강] 컴퓨터 알고리즘 성능분석(1)
	[2강] 컴퓨터 알고리즘 성능분석(2)
	[3강] 확률분석(1)
	[4강] 확률분석(2)
	[5강] 동적계획법(1)
	[6강] 동적계획법(2)
	[7강] Greedy Approach(1)
	[8강] Greedy Approach(2)
	[9강] 스트링 매칭(1)
	[10강] 스트링 매칭 (2)
	[11강] 정수론(1)
	[12강] 정수론 (2)
	[13강] Flow networks (1)
	[14강] Flow networks (2)
	[15강] Amortized Analysis
GitHub	None

컴퓨터 알고리즘 정의 4가지

문제를 해결하기 위한 과정을 상세하게 단계적으로 표현한 것으로 입력과 출력으로 문제를 정의
|단계|내용|
|:-:|:-:|
|문제정의|현실 세계의 문제를 컴퓨터를 이용하여 풀 수 있도록 입력과 출력의 형태로 정의|
|알고리즘 설명|문제를 해결하기 위한 단계를 차례대로 설명|
|정확성 증명|항상 올바른 답을 내고 정상적으로 종료되는지 증명|
|성능분석|수행시간이나 사용공간에 대한 알고리즘의 성능을 비교하기 위한 분석|
가장 적합한 알고리즘을 고르기 위해 성능평가와 비교가 필요하다.
어떻게 하면 객관적으로 분석할 수 있는가?
ex) 특정기계X, 절대적시간X
그래서 상대적인 평가를 할 수 있는 점근적 표기법(Asymptotic notations) 을 사용해야 한다!

• $O$-notation : 점근적 상한(asymptotic upper bound)아무리 느려도 기준함수보다 느리다
• $\Omega$-notation : 점근적 하한(asymptotic lower bound) 항상 빠르다
• $\Theta$-notation : 그 사이
  $$T(n) = 3T([n/4])+\Theta(n^2)$$
  대체법(Substitution Method)
  재귀알고리즘은 T(n)으로 간단히 계산하기가 쉽지 않기 때문에(자기자신을 다시 리콜하기때문에.. 다차식형태로 변환해야함)
  해답의 형태를 추측하는 수학적 귀납법을 이용하여 추측한 해답이 맞음을 증명함.
  (다차식으로 변환하는 방법 3가지)
• Substitution Method : 값을 대체해서 계산하여 증명!!!
• Recursion-tree Method : 재귀를 트리형태로 그려보고 트리형태의 값이 무엇인지
• Master Method : 공식에 넣어서 적용

재귀 트리를 이용한 성능분석

(주어진 함수에 값을 추측하고. 추측한것을 대체법을 이용하여 증명.)
재귀 함수의 성능 분석을 위해 재귀 트리를 그려 해답을 추측하고(Recursion-tree Method),
이를 대체법(Substitution Method)을 이용하여 증명하는 방법이 있음.
(각 노드들을 코스트로 계산, 레벨들의 합을 구하고, 전체 트리의 합을 구함. )

Hiring문제를 이용한 확률분석

Hiring problem : 지원자 중 가장 뛰어난 직원을 고용하려고 할 때, 최소의 비용을 계산하는 문제.

고용문제는 인터뷰비용과 고용비용을 최소로 하면서
가장 좋은 사람을 뽑는 방법으로 이 문제를 해결하기 위한 확률분석방법을 이해함
(가장 좋은 사람이 몇 번째 인터뷰에 오느냐?+ 각각의 경우가 몇 가지인가?)
(지원자는 1명씩 인터뷰, 인터뷰후 고용여부 바로 판단, 고용할경우 기존직원은 해고된다, 면접비용과 고용비용은 각각 다르다. 무작위순서가 필요한이유: 입력의 순서는 다양할 수 있기 때문에.. )

• Indicator Random Variables을 적용해야 계산이 쉬워진다.
• Randomized Order : 무작위성추가

Balls and Bins 문제를 이용한 확률분석

Binomial Cistribution과 Geometric Distribution에 대해 알아보았는데
확률분석의 결과가 일반적으로 생각하는 확률과 크게 다르지 않음을 확인
(공의 크기와 모양, 바구니의 크기와 모양, 방향 동일하다. 속도는 연관이 없다.)

동적계획법(Dynamic Programming)

동적계획법을 적용하기 위해서는 최적해 구조와 재귀 구조를 가져야 함.
✨문제해결방법의 4가지✨

1. Brute-Force Approach : 전수조사(모든경우를 다해보고;; 가장빠르다, 가장적다라는 판결을 내리기 때문에 시간이 오래걸림)
   모든 경우의 답을 구해보는 일반적인 방법
   답이 있다면 항상 답을 탖으며 구현이 쉬운 편
   경우의 수에 비례하여 시간이 증가
   ex)약수구하기
2. Divide and Conquer Approach : 큰문제를 작게쪼개어 병렬적으로 해결.
   문제의 크기를 작게 나누어서 문제를 쉽게 풀기 위한 방법
   문제의 크기는 두 개 이상으로 쪼개어지고 문제의 해답을 바로 구할 수 있을 정도가 될 때까지 문제를 계속 분할
   하위 문제들이 서로 독립적이어야 함
   ex) 정렬문제(quick, merge, radix)
3. Dynamic Programming Approach : 주어진 문제를 하위로 나누어서 해결.(Divide and conquer와 비슷하지만 문제간의 관계가 다름)종속성을 가질 때 사용.
   하위 문제에 대한 답을 저장하였다가 동일한 문제가 나오면 재계산하지 않고 저장된 답을 사용
   ex) 피보나치 수열
4. Greedy Approach : 해당문제의 최적답을 고르면 전체에 답이 최적일 것이다.
   현재 상황에서 최선의 답을 선택
   현재 상황에는 최선이지만 전체에는 최선이라는 보장은 없음
   최적 부분 구조 조건을 만족하면 결과가 우수
   ex) 허프만코드

동적프로그래밍의 특징

• 모든 하위 문제를 풀고 그 결과를 저장해 둠
• 저장되어 있던 결과는 다음 단계의 문제를 푸는 데 사용(연관성)
• 동적프로그래밍은 최적화 문제를 푸는 데 쓰임

동적프로그래밍과 최적화 문제
가능한 해답이 무수히 존재하며,
각각의 해답은 숫자 등의 크기가 있는 값을 가짐
가장 크거나 가장 작은 최적의 값을 가지는 해답을 찾을 수 있고,
그런 해답을 최적화 문제의 최적해라고 부름
즉, 최적화 문제란 문제의 여러답이 서로 비교 가능하고
복수 개인의 경우, 목적에 따라 가장 좋은 결과를 찾아야 하는 문제.
ex) 최단경로문제

1단계 : 최적해에 대한 구조적 특징을 분석
(하위 문제로부터 해답을 구해서 원래의 답을 구할 수 있는 구조인지 확인해 본다.)
2단계 : 최적해 값을 구하기 위한 재귀적 정의가 가능한지 확인
3단계 : 하위문제로부터 최적해의 값을 계산
수행시간은 $\Theta(2^n)$
4단계 : 계산된 값으로부터 최적해를 만듦

동적계획법을 적용한 Assembly Line Scheduling

조립을 통해 제품이 완성될 때 여러 개의 과정과 여러 개의 라인이 존재할 때 최적의 조합을 찾아
가장 빠른 시간과 경로를 동적계획법을 이용하여 해결

동적계획법을 적용한 Matrix-Chain Multiplication

행렬의 곱은 그 순서에 따라 곱셈의 횟수가 달라지기 때문에 효율적으로 계산하기 위해서는 가장 최소인 경우를 찾아야 함

수행시간
$O(n^3)$ time in total : 주어진 매트릭스에 대해 매번 동일값을 매번 반복해서 계산.
$\Theta(n2)$ subproblems : 주어진값을 매트릭스형태로 n*n으로 계산된값을 모든 매트릭스에 반복적용.
$O(n)$ time for each subproblem

공간사용
$\Theta(n^2)$

Overlapping Subproblems : 하위 문제가 반복적으로 등장하는 경우
Memoization : 하위 문제가 반복적으로 등장하는 경우 계산한 값을 저장하여 효율성을 올림

7강 9:49

Greedy Approach vs Brute-Force approach
현재상황의 베스트 / 정답을 고를 수 있지만시간이 걸림
베스트와 차선값이 차이가 많이 나지 않아 경향만 보고싶을때는 greedy해도 상관없다.
꼭 정확한 답이 필요하다면 Brute-Force.
Greedy Approach vs Dynamic programming
현재상황의 베스트 / 이전상황을 모두 고려한 현재상황의 베스트
Greedy Approach vs Divide and Conquer
완전 다르기때문에 이 둘은 유사성이 없다.

0-1 Knapsack Problem

가방이 담을 수 있는 무게가 정해져 있을때,
가방에 담은 물건들의 가치가 최고가 되도록 선택하는 문제
(엇? 앞전에 봤었는데??)
Brute-Force 각각의 가치를 따져서 이방법 저방법 다해보고 정답을 고름.
Greedy 일단 가장 가치가 최고인것부터 넣고본다.

8강_ Huffman code

Huffman code는 데이터를 압축하고 해제하는데 광범위하게 사용되는 알고리즘으로 유동길이 코드를 효율적으로 설정하여 Encoding과 Decoding에 문제가 없으면서 크기를 최대한 줄이기 위해 사용한다.

• 압축(compression) : 처리 효율을 높이든가 데이터 양을 적게 하는 정보의 집약도를 높이는 등의 목적에서 통상의 데이터를 특수한 데이터 형식으로 치환하는것. 압축된 데이터는 역의 변환에 의해서 원래의 데이터로 돌아간다.

고정길이 코드

• 6가지 {a,b,c,d,e,f}로 구성된 십만 개의 문자를 표현한다면, 총 6가지 문자를 표현해야하므로 최소 3비트가 필요
• 3비트의 고정길이 코드(fixed-length code)로 표현한다면 300,000비트가 필요
  (000, 001, 010, 011, 100, 101)

유동크기 코드

• 사용공간은 고정크기가 아닌 유동크기 코드(variable-length code)를 사용하면 줄일 수 있음(Frequency에 따른 유동크기코드는 적은공간사용 224,000비트필요)
  (0, 101, 100, 111, 1101, 1100)

Greedy Approach를 이용하여 Huffman code 풀기.

Prefix가 중복되지 않는 유동길이 코드를 만들기 위해서
모든 경우를 계산하여 가장 효율적인 방법을 고를 수도 있지만
Greedy Approach를 이용하여 가장 빈도수가 낮은 문자들을 합치면서 트리구조를 생성하는 방법

유동길이 코드의 압축과 해제

• Encoding and Decoding
  문자코드가 다른 문자코드의 prefix가 되면 중복이 발생함으로, 중복을 피하면서 유동길이 코드로 만들어야 함.

• Huffman code의 생성 : Greedy approach로 해결하는 방법

  1. 빈도수Frequency에 따라 오름차순으로 정렬
  2. 제일작은 1,2번을 합쳐서 부모노드를 만든다.
  3. 1.2 반복 (끝날때까지)
  4. 트리의 왼쪽은0, 오른쪽은1을 주면 Codeward가 나온다
  5. 비트계산 Frequency*길이 (빈도수가높은건 길이를 짧게해서 비트수를 줄인다)

스트링매칭(String Matching)

텍스트T와 패턴P가 주어졌을 때, 'T에 P가 존재하는가?'에 대한 해답을 찾는 문제.
한 칸씩 이동하여 text가 끝날때까지 비교하여 횟수와 위치를 찾는 문제.

KMP알고리즘

비교횟수를 최고화하는 스트링매칭 알고리즘으로 선형시간에 검색이 가능함.

비교의 횟수를 줄여서 좀더 빠르게 스트링매칭의 결과를 내고자.
불필요한 비교가 많은 기존 스트링매칭과 달리 여러칸을 옮김.
패턴P의 발생을 놓치지 않으면서 비교 횟수를 최소화할 수 있을것인가.

시간복잡도 : 비교의 횟수와 패턴의 재 비교 횟수로 고려할 수 있다.
비교의횟수 : 매치된 수 + 믹스매치된 수의 합이다.

Exact Matching

주어진 텍스트T에서 찾고자 하는 패턴P가 발생하는 횟수와 모든 지점을 찾는 문제

Approximate string matching(exact의 반대)

주어진 텍스트T에서 찾고자 하는 패턴P의 일부를 찾아서 발생하는 횟수와 모든 지점을 찾는 문제
$$(1개틀린것과 2개틀린것 p=ab, aa, ba 와 a, *b, **a)$$
여러 번 반복해서 찾아야 하는 문제가 발생 -> 시간복잡도 증가

Exact Set Matching(Approximate와 비슷)

주어진 텍스트T에서 찾고자 하는 패턴P의 집합이 주어졌을 때, 패턴 P의 집합을 효율적으로 찾는 문제
여러 번 반복해서 찾아야 하는 문제가 발생 -> 시간복잡도 증가

Aho-Corasik알고리즘

Output-link와 Failure-link를 적용한 키워드 트리를 이용하여 Exact Set Matching문제를 선형시간에 해결이 가능
중복되는것을 한번에 검사한다 p ={pat, party} 중복pa

• 키워드 트리(Keyword Tree) 생성규칙
  1. 각 간선은 문자 하나를 할당
  2. 한 정점으로부터 간선이 두 개로 나누어졌다면 두 간선은 각기 다른 문자가 할당
  3. 패턴집합 P안의 모든 패턴들은 정점들의 집합에 모두 매칭됨

정수론(Number Theory)과 암호

정수론은 수의 성질을 연구하는 분야로 나눗셈정리, 페르마 정리, 소인수분해, 중국인 나머지 정리 등의 이론이 있으며
수의 성질을 이용한 암호알고리즘이 연구되고 있음

암호는 특정인에게 비밀정보를 전달하는데 사용하는 방법이나 체계를 의미

공개키 암호알고리즘

공개키 암호 시스템은 공개키와 개인키를 사용하여 메시지의 암호화와 사용자의 인증을 수행할 수 있는 암호 시스템으로
대표적으로는 RSA, ECC, DSS등이 있음
RSA 암호알고리즘 : 소인수분해가 어렵다는 성질, 정수론의 연구결과를 이용.
공격자가 암호된 내용을 쉽게 파악할 수 없도록한다는 특징이 있다.
Eucli'd GCD함수(최대공약수), Extended Euclid's GCD함수, Euler's totient function 등을 사용하여 암호를 수행.
ex)공인인증서

ECC 암호알고리즘 : 타원의 두 중심점을 찾기 어렵다는 성질을 이용

Diffie와 Hellman 연구자가 1976년에 제안하였으며 기존의 키를 1개 사용하는 시스템과 달리 2개의 키를 사용하여 암호화와 사용자인증을 수행함.

공개키 암호시스템은 다음 두 가지 문제를 해결하기 위해 개발되었다.

1. 기존의 비밀키를 사용하는 시스템에서 키를 분배하는 문제를 해결
   사람A,사람B모두 암호화된 문장을 해석할 수 있는 키를 가지고 있어야만 복원해볼 수 있는데..
   사람C라는 제3자가 나서서 '사람A,사람B 서로 통신(암호,복호)을해도 문제가없다'라는 것을 보장해줘야하는 것이
   "키를 분배한다"라고한다;;;
2. 네트워크에서 부인방지를 막기 위해 전자서명의 필요성이 크게 대두
   보내놓고 안보냈다고 하거나, 받아놓고 안받았다고 하거나

공개키 암호 시스템의 구성 3가지

1. 평문(M)과 암호문(C)
2. 공개키(Pu)와 개인키(Pr)
3. 암호알고리즘(Enc)과 복호알고리즘(Dec)

공개키 암호 시스템의 특징
Trap Door One-Way Function
단방향 함수로 역함수를 계산하는 것은 거의 불가능하지만,
특정 정보(Trap Door)를 알고 있다면 역함수를 계산할 수 있음

공개키 암호 시스템의 조건

• 공개키는 모든 사람이 필요로 하면 얻을 수 있도록 공개
• 개인키는 사용자만 보관/사용함
• 공개키-개인키는 쌍으로 만들어지고 사용됨
• 공개키로 암호화한 내용은 개인키로 복호화함
• 개인키로 암호화한 내용은 공개키로 복호화함

RSA 암호알고리즘 소개

1977년 MIT에서 개발되어 현재까지 활발히 사용 중인 암호알고리즘(ex.공인인증서)
Rivest-Shamir-Adelman 연구자가 공동으로 개발
블록단위로 암호를 수행
0과 n-1사이의 정수를 평문과 암호문으로 사용
사용하는 키의 크기는 2048bit이상이 일반적 (60승 어마어마 큼!!)
크기가 아주 큰 수는 소인수분해가 어렵다는 수의 성질을 이용하여 암호화를 수행.

@_@12강 정수론(2)😥

RSA와 Entended Euclid GCD

공개키 암호알고리즘인 RSA는 크기가 큰 수는 소인수 분해가 어렵다는 수의 성질을 이용하여

Flow networks

방향성 또는 무방향성 그래프에서
각 간선이 용량(Capacity)과 흐름(Flow)을 갖는 경우
ex) 도로, 순환, 전자회로, 파이프의 흐름 등을 표현
-Maximum flow problem은 그래프에서 최대 흐름의 양을 찾는 문제

Flow networks를 Ford-Fulkerson Method로 풀어보자

• Greedy 알고리즘으로 Flow networks에서 Max, flow 문제를 해결
• Augmenting paths와 residual nerwork를 이용하여 여분의 경로를 찾고 흐름의 양을 계속 추가하는 과정을 반복

Amortized Analysis(분할상환 방식)

• 자료구조에서 하나의 Operation을 수행할 때 필요한 시간을 전체 Operation을 수행할 때의 평균 시간으로 바꾸어 놓는 것
• Amortized Analusis는 Average Case Analysis와는 다르며 차이점은 확률적인 계산이 포함되지 않음(모든 경우, 최악의 경우 모두를 고른다)
• 목표는 최악의 경우일 때, 각 Operation의 평균 성능을 보장해주는 것

3가지 기술 사용
(3가지 모두 고비용의 Operation이 있을때 미리 비용을 계산해놓고, 크레딧 혹은 포텐샬값을 가지고 앞으로 있을 비용들을 미리 지불하는 형식으로 최대값이 얼마가 될것인지를 잡는것이 목표 )

1. Aggregate Method 합계
2. Accounting Method 회계
   Accounting Method란,
   은행에 적립해놓고 쓰는것과 같다.
   • Operation이 다르면 비용Charges도 다름
   • 추가로 Change된 부분은 Credit에서 보관
   • Credit은 실제 Operation보다는 차후에 수행될 operation에 사용
   • Aggregate Method에서는 모든 Operation이 동일했던 것과는 반대
   • 전체 Amortized Analysis는 실제 Cost의 상한이어야 함
   • 전체 Credit은 양의 정수 혹은 0 이어야 함
   • 따라서, 선택된 Amortized 비용은 음의 값이 나오지 않음
3. Potential Method 가능성

2가지 적용 예

• Stack operation (push, pop, multi-pop)
  stack operation이란,
  Push와 pop, multi-pop은 (n번들어갔다가 n번나오니까)아무리 커도 최악의 경우 O(n)
  각 object는 push되는 경우에 대해 아무리 커도 한번 pop.
  push operation의 최대는 O(n)
  따라서 pop의 횟수는 최대 O(n)
• Binary counter using the increment operation

1-1.Aggregate Analysis기술을 이용한 Stack operation 분석방법

Amortized Cost는 O(n)/n = O(1)

1-2.Aggregate Analysis기술을 이용한 Binary counter 분석방법(15강 6:15)

😭

2-1.Accounting Method기술을 이용한 Stack operation 분석방법

Push 2, pop 0, multi-pop 0
비어있는 stack에 push를 먼저 한다면 Amortized Credit에 저장
모든 pop에 저장된 credit을 이용하여 수행
pop의 수는 push의 수와 동일
전체 Amortized Analysis는 O(n)

2-2.Accounting Method기술을 이용한 Binary counter 분석방법

Accounting Method의 Amortized Cost는
1이 되면 2, 0이 되면 0, 1에 대해서 credit이 저장
모든 bit를 reset하는 것은 credit을 사용
1의 숫자는 항상 0 또는 양수이므로 credit도 0 또는 양수
전체 Amortized cost는 O(n)

Dynamic Expansion and Contraction

Table을 사용하다가 할당한 크기가 데이터를 담기에 작아지는 경우
Table은 더 큰 크기를 재할당 받고
기존의 데이터는 새로운 table로 모두 복사

반대의 경우로
Table을 사용하다가 Table의 크기에 비해 데이터가 너무 작은 경우에도
Table을 (낭비를 줄이기 위해)재할당 받고
데이터를 모두 복사

Table-Insert와 Table-Delete Operation을 지원한다고 가정
Table-Insert는 Table에 빈 슬롯이 있으면 한 칸을 차지하고 데이터를 집어 넣음
Table-Delete는 Table에서 데이터 하나를 삭제하여 빈 슬롯 하나를 추가