수학과의 개발자 도전기

공부한 날짜: 2021. 11. 09

1. 고정길이 코드와 접두어 코드 

-고정길이 코드(fixed length code): 모든 코드의 길이가 똑같은 값을 갖는 코드 체계 

장점은 다루기 쉽다(연산에 편의성이 있다) 

-가변길이 코드: 코드의 길이에 변동이 있음

장점은 저장공간의 절약을 할 수 있다는 것

-접두어코드(Prefix Code): 가변 길이 코드의 한 종류로, 무접두어 코드와 동일어. 

코드 집합의 어느 코드도 다른 코드의 접두어가 되지 않는 코드.

2. 허프만 코딩 

:기호의 빈도와 이진트리 개념이 핵심

+기호의 빈도는 길이가 짧은 접두어 코드를 빈도가 높은 기호에 부여하기 위해 사용한다 -> 저장공간을 아낄 수 있다 

+이진트리는 접두어코드를 표현하는데 사용한다.

+왼쪽 자식 노드는 0, 오른쪽 자식 노드는 1을 나타내고,

+모든기호는 잎노드에만 기록,

+기호의 접두어 코드 : 루트 노드에서부터 잎 노드까지 이르는 경로

-압축 과정

ㄱ. 해 선택: 빈도 가장 작은 노드들끼리 연결한다

ㄴ. 실행 가능성 검사: 기호를 가진 노드가 잎 노드인지 확인 

ㄷ. 해 검사: 트리가 최종 트리인지 확인 

-압축해제 

ㄱ. 허프만 트리와 압축 해제된 데이터를 담을 버퍼를 준비한다. 루트노드부터 잎노드까지 순회한다

ㄴ. 압축 데이터에 아직 읽지 않은 부분이 남아있으면 잎 노드까지 순회한다

ㄷ. 읽어낸 비트가

0 -> 현재 노드의 왼쪽 자식노드

1-> 오른쪽 자식 노드로 이동.

현재 노드가 잎 노드이면 저장되어 있는 기호를 버퍼에 추가하고 

다시 루트 노드로 이동 

<=> 비트를 읽을 때마다 잎 노드를 만니기 전가지 허프만 트리의 왼쪽/오른쪽으로 노드를 순회하라

공부한 날짜: 2021. 11. 08

1. 탐욕 알고리즘 

: 최적화 문제의 답을 얻기 위해 사용하며, '탐욕'은 각 단계의 부분 문제를 풀 때 근시안 적으로 최적해를 구한다고 해서 붙여진 이름이다. 

-동작 순서

(1) 해 선택: 현재 상태에서 부분 문제의 최적해를 구한 뒤, 이를 부분해 집합(Solution Set)에 추가한다 

(2) 실행 가능성 검사: 새로운 부분해 집합이 실행가능한지를 확인. 문제의 제약 조건을 위반하지 않는지를 검사

(3) 해 검사: 새로운 부분해 집합이 문제의 해가 되는지를 확인. 아직 전체 문제의 해가 완성되지 않았다면 (1) 단계부터 다시 시작. 

-편의점 점원의 거스름돈 줄이기 구현 

공부한 날짜: 2021. 11. 08

1. 동적계획법

• 제일 작은 부분 문제부터 상위에 있는 문제로 풀어올라가는 방법(Bottom up) 

문제의 각 단계에 있는 부분 문제들은 그 이전 단계에 있는 문제들의 답에 의존하고, 한번 푼 적이 있는 부분 문제의 답은 테이블에 저장한다

• 동적계획법의 조건

1. 부분 문제들이 겹치는가(반복 되는가)
2. 최적 부분구조(문제의 정답을 작은 문제의 정답으로부터 구할 수 있는가), 부분문제 최적해의 disjoin union은 전체문제의 최적해

• 동작방식

(1) 문제를 부분 문제로 나눈다

(2) 가장 작은 부분 문제부터 해를 구한 뒤 테이블에 저장한다

(3) 테이블에 저장되어 있는 부분 문제의 해를 이용하여 점차적으로 상위 부분 문제의 최적해를 구한다

1_2. 부분 문제들이 겹치는가: 동적계획법으로 피보나치 수 알고리즘 구현 (python)

• 재귀함수로 구현 

• 동적계획법으로 구현 

: 한번 거쳤던 항들은 모두 memo에 저장된다. 따라서, 다음에 구할 때는 연산없이 리턴이 가능하다 

1_3:   최적 부분구조 : 문제의 정답을 작은 문제의 정답으로부터 구할 수 있는가 

ex) 최단경로 구하기: A에서 C로 가는 최단경로(큰 문제)= A에서 B로 가는 최단경로(작은 문제) + B에서 C로가는 최단경로(작은문제)

따라서, 정답을 한번 구했으면 Memoization하여, 반복연산을 없애는 과정이 중요하다 

2. 다이나믹 프로그래밍 구현 (두 방법의 정확한 차이점을 잘 모르겠음)

Top-down : 위에서 아래로 해결한다(ex: 재귀함수)

1. 문제를 쪼갠다.(이게 bottom-up과 다른점)

2.작은 문제를 푼다.

3. 작은 문제의 정답으로 큰 문제를 해결한다.

Bottom-up : 아래에서 위로(ex: 반복문)

1. 작은 문제부터 풀어나간다.

2.문제의 크기를 점점 크게 만들어 푼다.

3. 작은 문제들을 해결했기 때문에, 한단계 위의 큰 문제를 풀 수 있다.

4. 최종적인 문제를 해결한다.

시간 복잡도는 비슷한 수준이며, 문제에 따라 구현하기 편한것을 선택하여 풀면된다(즉, 어떤것으로 풀어도 큰 상관은 없다)

다만 파이썬 같은 경우는 재귀로 풀게되면 메모리초과가 날 가능성이 타 언어보다 높기 때문에, 반복문(bottom-up)으로 푸는게 낫다고 한다

-문제를 해결할때

• 점화식을 정의한다
• 문제를 어떤식으로 쪼갤지(작게 만들지) 생각한다
• 작은 문제의 답을 통해 어떻게 최종적인 문제를 해결할 수 있을지 생각한다 

예를 들어 카드를 i개 구매하는 문제라고하면, 하나 구매할때, 두개구매할때, 차근차근 생각해보고, 적어보면 규칙이 보이거나 점화식이 보인다. 비슷한 유형을 풀어보며 감을 기르는게 무엇보다 중요한 것 같다.

출처: https://infinitt.tistory.com/246

3. 최장 공통 부분 순서-> 두 데이터를 비교할 때 유용하다 

-순서: 정렬되어 있는 객체의 목록

-부분 순서: 순서에서 일부 요소를 제거한 것 

-공통 부분 순서: 두 순서 사이에 공통적으로 존재하는 부분순서

-최장 공통 부분순서: 여러개의 공통 부분순서 중에서 가장 긴것을 가리킨다 

(1) LCS 알고리즘

먼저 최적 부분 구조로 이루어져있는지 확인하기 

• 점화식

 : 위 점화식은 X와 Y의 LCS가 부분 LCS의 답으로부터 만들어지고 있음을 보여준다. 따라서 이 알고리즘은 최적부분구조를 가지므로 동적 계획법으로 해를 구하는 것이 가능하다

-LCS 테이블의 크기는 (i+1)x(j+1). 아무것도 없는 행(i=0)과 열(j=0)을 표현하기 위함.

• 코드 구현

+ 이렇게 코드를 구현하면 수행시간이 지수적으로 증가함. O(2^(n+m))만큼

(2) 동적계획법으로 설계하는 LCS 알고리즘 -> LCS의 길이를 구할 수 있음

(3) LCS 자체를 구하는 방법

• 오른쪽/아래 모서리 요소를 시작 셀로 지정하고, LCS의 요소를 담기 위한 리스트를 하나 준비한다
• 현재위치한 셀의 값이 왼쪽, 왼쪽 위, 위 셀의 값보다 크면 현재 셀의 값을 리스트의 헤드에 삽입하고 왼쪽 위 셀로 이동한다
• 현재 위치한 셀의 조건이 단계 ㄴ.에 해당하지 않으며, 현재 셀의 값과 왼쪽 셀의 값이 같고 위 셀의 값보다 큰 경우에는 왼쪽으로 이동한다. 이동만 할 뿐 리스트에 아무것도 넣지 않는다
• 2,3번째 중 어느 경우에도 해당하지 않는 경우에는 위 셀로 이동. 리스트에 아무것도 안 넣음
• i=0 or j=0 이 될때까지 ㄱ~ㄹ 단계 반복

공부한 날짜: 2021. 11. 07

-분할 정복 알고리즘: 문제를 더 이상 나눌 수 없을 때까지 나누고, 나눠진 문제들을 각각 풂으로써 전체 문제의 답을 얻는 알고리즘

핵심: '문제 잘게 쪼개기'

 -요령

(1)분할(divde): 문제가 분할이 가능한 경우, 2개 이상의 하위 문제로 나눈다

(2)정복(conquer): 하위 문제가 분할 가능하면 (1) 반복, 분할 되지 않는다면 하위 문제를 푼다

(3)결합(combine): (2) 과정에서 정복된 답을 취합한다

1. 병합 정렬 : 나누고 합쳐라

(1) 정렬한 데이터 집합을 반으로 나눈다

(2) 나누어진 하위 데이터 집합의 크기가 2 이상이면 하위 데이터 집합에 대해 (1)을 반복

(3) 하위 데이터 집합 둘을 하나로 병합하고, 이때 원소는 순서에 맞춰서 정렬한다

(3)-1 두 데이터 집합을 합한 것 만큼의 비어 있는 데이터 집합을 마련

(3)-2 두 데이터 집합의 첫 번째 요소들을 비교하여 작은 요소를 새 데이터 집합에 추가. 그리고 새 데이터 집합에 추가된 요소는 원래의 데이터 집합에서 삭제

(3)-3 양쪽 데이터 집합이 빌 때가지 (3)-2 과정 반복

2. 거듭 제곱

3. 피보나치 수열