네이버 부스트코스의 파이썬을 이용한 알고리즘의 이해 강의를 들으며 기록했습니다.
알고리즘이란 뭘까?
추상적 정의 : 문제를 푸는 계산이나 계산 과정을 정의하는 방법
input - alg - output
컴퓨터 프로그램의 수학적 표현
계산모델(model of computation)이 규정하는 것
- 알고리즘이 할 수 있는 연산
- 각 연산에 드는 비용(시간)
- 각 연산모델의 비용을 모두 더 하면 '알고리즘의 비용'이 된다.
계산 모델의 두 가지 분류
- RAM(Random Access Machine)
- Random Access Memory와 약간 다른 개념이지만 수학적 표현에서의 RAM인 것
- 컴퓨터에 있는 램은 기본적으로 커다란 '배열'이고, 워드로 조직됨
- 상수의 시간(O(1))동안 알고리즘은 메모리로부터 상수개의 워드를 읽거나 불러낼 수 있고, 상수 개의 계산을 실행할 수 있으며, 그것을 워드에 기록할 수 있다.
상수 개의 레지스터가 있다고 하면, 레지스터로 워드를 불러와서, 계산을 실행하고, 레지스터가 저장한 위치에 기록하는 것 - 캐시같은 것을 무시한다면 워드를 불러오고 계산을 실행하고, 기록하는 것에 전부 상수시간이 소요되는 것이 우리가 기본적으로 컴퓨터를 인식하는 방법
- 워드란?
워드 = w(w >= log(memory size) bit
기본적인 객체가 워드에 들어맞는다고 가정한다
현실적이고 강력한 모델이지만 배열을 사용하지 않는 경우도 있음
- Pointer Machine
- 동적 할당 객체(네임드 튜플)
- 하나의 객체는 특정 개수(O(1))의 필드를 가진다.
- 필드는 워드가 될 수도 있고(여기서 워드는 정수, 입력 객체, 계산 대상, 카운터 등을 저장하는 것)
- 필드는 포인터(다른 객체를 가리키거나 null이라는 값을 가질 수 있다)가 될 수도 있다
- RAM보다 약하다(RAM으로 구현 가능 - 포인터는 인덱스가 됨)
파이썬 모델
파이썬 모델은 위 두 모델을 모두 적용할 수 있다
1. list = array(Random Access Machine)
2. 상수개(너무 많은 수는 안됨)의 속성을 가진 객체(Pointer Machine)
파이썬 모델의 연산은 매우 다양하지만, 기본적으로 위의 두 연산을 기반으로 한다.
어떤 연산에 대해 계산할 때, 위의 두 연산을 기반으로 파이썬이 동작하는 방식을 생각하면 자원의 소모를 측정 할 수 있다.
- 파이썬에서 구현된 다양한 연산모델을 강의 및 강의자료를 통해 살펴볼 수 있으므로 참고
예시문제 :
Document distance problem : 문서 거리 계산
- 두 문서가 얼마나 유사한가에 대한 계산
- 문서는 연속적인 단어이고, 단어는 영어와 숫자로 이뤄진 문자열(공백, 문장부호를 무시한) 이라고 정의
- 아이디어 : 공통 단어를 이용하여 문서의 거리를 정의
- 문서를 '백터'라고 가정하고 이야기 하면
- D[w]는 그 단어가 문서에 등장하는 횟수를 말함(음이 아닌 정수)
만일 'the cat', 'the dog'라는 두 문서가 있다면, 등장하는 단어가 3개 이므로 아래의 백터 그래프로 표현할 수 있음
강의에서는 두 벡터 사이의 각도를 이용하여 문제를 해결하였다.
문제 해결 코드
