컴퓨터 - ACM ICPC
17/01/19 08:05(년/월/일 시:분)
아주대 김동윤 교수 (2016년 8월 정년퇴임하셨고, 이 강의는 한달 전인 7월이었다)
0. Intro
최근 Computer science 쪽에 큰 걸 2개 꼽자면, Neural net, Information theory.
Neural net은 Hidden layer가 없던 시절, XOR 안되서 Marvin Minsky가 AI라는 말을 대중화시킨 이후로 20년동안 up & down을 겪었다. 그러다가 Hidden Layer가 들어가고 Probability 개념이 들어가면서 크게 좋아짐. 예를 들어 Face recognition은 매년 0.x %씩 좋아지던게 Neural net 이후로 x % 씩 좋아짐.
이걸 하려면 (Computer science의 다른 분야와 달리) Math에 기초가 있어야 함. (이것이 오늘 Algorithm 강의에 기초 수학을 하는 이유이다)
그 다음으로 information theory(정보 이론). 여기에는 entropy(엔트로피) 개념이 들어간다. 이것은 열역학에 쓰이던 말인데, 왜 굳이 이 말을 가져왔는지 모르겠다. 헷갈리고 오해할 여지만 생긴다. 하지만 처음에 정보 이론을 만든 섀넌이 그렇게 정했고, 달리 더 좋은 말도 없으니 그렇게 부르자.
여기에 Counting과 확률 문제, 순열 및 조합을 하고
추가로 확률적 알고리듬(Probabilistic Algorithm) 특성 및 실제 응용 예를 보고 마치기로 하자.
1. Measure
기업이 인재를 채용한다고 생각해보자. 어떤 사람을 뽑아야 할까? 여러 가지를 봐야 할 것이다. 예를 들면
1) 문제 해결 능력
2) 문제를 만드는 능력
3) 도덕성
이런 여러 가지를 고려해야 할 것이다. 하나만 보면 안되고, 다양한 조건을 모두 고려해야 할 것이다. 그래서 결국에는 합격시킬지 불합격시킬지를 결정해야 한다. 어떻게 결정할 것인가?
각 요소 별로 점수를 매기고,
각 요소 별 가중치를 매겨서,
각 요소 별 점수 * 가중치의 총합으로 정렬하면 될 것이다.
예를 들어
1번 요소: 문제 해결 능력 (가중치 30)
2번 요소: 문제를 만드는 능력 (가중치 40)
3번 요소: 도덕성 (가중치 30)
이라고 하고
각 지원자별로 다음과 같이 점수를 받았다고 했을 때,
1번 지원자 점수: 1번 80점, 2번 90점, 3번 100점
2번 지원자 점수: 1번 90점, 2번 80점, 3번 100점
이라고 하면, 각 지원자 별 점수는
1번 = 80*0.3 + 90*0.4 + 100*0.3 = 90점
2번 = 90*0.3 + 80*0.4 + 100*0.3 = 89점
그래서 1번이 2번보다 총점이 더 높으므로, 1번 지원자를 채용할 것이다.
이런 식으로 생각하는 방법을 Decision Theory 라고 한다.
수식으로 쓰면
max ∑(i)w(i)x(i) w.r.t. ∑(i)w(i) = 1
(w.r.t. = with regard to)
이렇게 측정하는 데 수학이 필요하다.
또 수학이 필요한 데가 거리, 두 점 사이의 거리를 구하는 것이다.
거리가 여러가지 거리가 있는데, 종류와 상관없이 다음을 만족한다.
점(Point)이니까 p라고 하고
점이 여러개니까 순차적으로 p,q,r이라고 하자.
거리(Distance)니까 d()라고 하면
1) d(p,q)>=0 거리는 0 이상이어야 하고
and d(p,q)=0 iff p=q 거리가 0이면 두 점은 같다
(iff = if and only if 필요충분조건)
2) d(p,q) = d(q,p) 교환법칙
3) d(p,r) = d(p,q) + d(q,r) 결합법칙
거리를 재는 방법은
1) Euclidean method 유클리디안 방법 (직선거리)
2) City-block method 도시 블럭 방법 (격자 상에서 이동하는 거리)
3) Chessboard method 체스판 방법 (x,y축 이동거리 중에 큰 거 하나만)
다음으로 대표값을 구하는 방법
1. mean (평균)
2. median (중간값)
3. mode (최빈수)
norm(놈)은 벡터의 길이인데, 수식은 이렇다
절대값 기호(|x|)를 두번 겹쳐 씀
||x||(p) = (∑(i=1..n)|x(i)|^p)^(1/p)
norm(놈)의 종류는 다음과 같다
길이(Length)니까 L이라고 하자
L(2) norm : ||x||(2) = (∑(i=1..n)|x|^2)^(1/2) = mean
L(1) norm : ||x||(1) = ∑(i=1..n)|x| = median
L(∞) norm : ||x||(∞) = max|x(i)| = mode
norm(놈)의 성질
1) ||x|| >= 0 길이니까 0 이상
2) ||λx|| = λ||x|| 람다(λ)를 상수값으로, ||x|| 바깥으로 끄집어낼 수 있다
3) ||x+y|| <= ||x||+||y|| 결합법칙은 아니고
근데 이런 여러가지 norm(놈) 중에서 어떤 거를 쓸거냐?
L2-norm이 좋긴 한데 계산이 복잡해서 좀 느리고,
L1-norm이 계산이 간단해서 더 빠르긴 한데 그렇게 좋지는 않다.
즉 Robustness vs. Efficiency
강건함이냐 효율이냐,
이상한 값들이 많아도 잘 견딜거나, 아니면 계산이 빠를 거냐 중에 선택해야 한다.
2. Entropy
통계란 무엇인가? 우리는 왜 통계를 쓰나?
이런 문제들이 있다.
- 새로 개발한 제품이 기존 제품보다 품질이 좋아졌나?
- 이 사람이 정말 잘 알아맞추는 능력자인가?
- 남녀의 시력 차이가 있는가?
타협의 문제도 있다.
1. 생산자 위험(Manufacturers' Risk) : 양품인데도 불량으로 판정하는 위험
2. 소비자 위험(Consumers' Risk) : 불럄인데도 양품으로 판정하는 위험
1번은 false positive, 2번은 false negative다.
여기서 1번을 줄이면 2번이 늘어나고, 2번을 줄이면 1번이 늘어난다.
- 어디서 타협할까?
- Information Theory 섀넌의 정보 이론
정보란? 발생할 확률이 낮은 사건이 더 큰 정보를 가진다.
엔트로피란? 확률*정보 합친거
이걸 이용해서 Huffman code 만든다
--> 오늘의 과제: 허프만 코드를 실제로 짜보자
Recursive Huffman code
Optimal Huffman code vs. Entropy
Quality of the Huffman code : 허프만 코드가 잘 안 돌아가는 경우
허프만 코드의 복잡도는 O(n log n)
Run-Length coding
Golomb code of Order m
- Choosing m 최적의 m값 찾기
골룸 코드는 한 쪽으로 매우 쏠린 데이터 압축에 좋다
근데 order m 값을 지정해줘야 한다
Tunstall codes
고정 길이에 적합
에러 저항성: 중간에 몇 비트 에러 나도 전체로 퍼지지 않음 (허프만 코드는 한 비트만 에러나도 전체로 퍼짐)
3. Counting
완전 순열 갯수 점화식 구하기
!n = d(n) 이라면
d(n) = (n-1)(d(n-1)+d(n-2)) (왜?)
또는 d(n) = n * d(n-1) + (-1)^n (왜?)
중복 조합 갯수
n명에서 중복 허용하여 k명 뽑는 방법
H(n,k) = C(n+k-1,k) (왜?)
n개의 집합에서 중복을 허용하여 r개를 뽑는 조합의 경우의 수
=집합 n과 r을 n-1개의 칸막이 속에 r개를 집어넣는 것으로 하여, n-1+r개의 집합에서 r개를 뽑는 조합
카탈란 수(Catalan Number)
(n+2)각형을 n개의 삼각형으로 나눌 수 있는 경우의 수
C(n) = (2n)! / n! * (n+1)!
점화식은
C(0) = 1
C(n) = ∑(i=0..n-1) C(i)*C(n-1-i)
점근적으로는 다음에 근사
C(n) ≈ 4^n / (n^(3/2) * √π
카탈란 수는 이것 자체가 생각하기 재밌기도 하지만, 이것과 전혀 비슷해보이지 않는 문제들도 같은 방식으로 풀 수 있다는 게 재밌다. 예를 들면
- dyck word (뒤크 단어)의 갯수 세기
여기서 뒤크 단어를 괄호 2개 (, ) 로 생각하면, 올바르게 닫히는 괄호 구조의 갯수와 동일하기도 하다.
- lattice paths (격자 경로) 의 경우의 수와도 동일하다.
Inversion Counting
a(1),a(2),...a(n) 순열에서
i
a(j)인 inversion들의 갯수
그냥 세면 O(n^2)인데, 더 좋은 방법이 있을까? O(n log n)짜리
Inversion Counting의 응용으로, 순서에 대한 Similarity Measure 문제
심사위원들이 경연자들의 순위를 매긴다.
경연자 1,2,3,4 순으로 매긴 순위
심사위원A: 1 2 3 4
심사위원B: 1 3 2 4
심사위원C: 3 4 2 1
이때, 심사위원 별로 각 경연자들에게 매긴 순위의 차이 합은?
A,B 차이 합 = 1
A,C 차이 합 = 5
A,B 차이 합 = 4
이걸 Inversion Counting을 응용해서 푸는 방법은?
점수의 합을 사용하지 않는 이유는?
Advanced Permutaion(순열) 문제
Palindrom은 앞에서 보나 뒤에서 보다 같은 문자열이다.
주어진 문자열의 모든 문자를 사용하여 Palindrom을 만드는 문제
1. 주어진 문자열로 Palindrom 가능한지 점검
2. 가능하면 Palindrom의 앞쪽을 구함
3. 앞쪽을 사용하여 Permutation을 구함
1. 각 문자별 빈도가 짝수, 홀수 여부
--> 짝수면 앞뒤로 반복 가능, 홀수는 안됨
2. 반복 가능 순열을 구하고 (앞쪽 반)
3. 생성 가능 순열을 구한다
주어진 문자열에서 가장 긴 Palindrom Subsequence 길이 찾기
- String repeat counting 변형 문제
1,2,...,n 배열에서 한 숫자를 빼고, 중복 숫자를 하나 넣었다. 이를 찾아라
(단, 정렬되어 있지 않음
어떻게 풀까?
1. sorting 사용
2. count 배열 사용
3. 배열을 traverse하고 방문한 곳을 표시
4. 더하고 곱하는 두개의 방정식 사용
5. XOR 이용
주어진 배열에서 두 수간의 차이가 k인 쌍을 찾는 문제
예) {8,12,16,15,9,13}에서 k=3이면, 답은 (9,12) (12,15) (13,16)
문제풀이 방법
1. 모든 원소를 체크
2. sorting 이용
3. hashing 이용
4. self balancing BST 사용
4. 무작위(Randomized) 알고리듬
또는 확률적(Probabilistic) 알고리듬
난수를 발생시는 방법
1) Las Vegas 알고리듬: 전부 다 해보는 것으로 항상 옳은 답을 얻지만 오래 걸릴 수 있다
2) Monte Carlo 알고리듬: 일부만 해보는 것으로 아주 빠르지만 아주 간혹 답이 옳지 않을 수 있다
예) Load Balancing
흔히 Round Robin(순차적으로 돌아가면서 주는 방법)이나, 현재 일이 가장 적은 서버에 새 일을 주는 방법을 쓰는데, Random하게 줘도 좋다. (굳이 계산하지 않아도 계산해서 주는 것만큼 또는 그보다 좋은 성능이 나온다)
예를 들어 초당 2500건의 처리를 하는 서버가 10대 있을 경우, 무작위로 배정했을 떄 특정 서버가 10% 이상 일을 더 할 확률이 1/16000에 불과하다.
예) n개 중에 중간값보다 큰 값 하나 구하기
보통은 n/2개 중에 최대값을 구함 = 100% 확실한 답
몬테칼로 알고리듬: 10개를 임의 추출하여 그 중에 최대값 구함 = 이것이 중간보다 작을 확률은 (1/2)^10 ≈ 0.001
불안한가? 10개 대신 20개면 (1/2)^20 ≈ 0.000001
예) 매우 긴 두 문자열이 같은지 검증 (각 문자열은 원격지에 있고, 서로 통신해야 하는데 통신료가 매우 비싸서 최소한으로 통신해야 한다)
원래는 처음부터 끝까지 다 검사해야 함
몬테칼로 알고리듬: 문자열의 Hash function 결과값을 서로 비교 (hash에 들어가는 값은 임의의 소수 p를 넣는다) 그러면 통신해야 하는 값은 임의의 소수 p와 Hash Function 결과값 2개다.
문자열의 길이가 100,000이고, 해쉬 펑션에서 사용하는 임의의 소수 최대값이 2^32일때, 해쉬 펑션의 결과값이 일치하는데 문자열이 틀릴 확률은 0.0001 이다.
이렇게 굳이 다 해보지 않아도 일부만 무작위로 돌려봐서 매우 높은 확률로 답을 찾는 방법이 있다.
끝