[MIT] 파이썬을 이용한 알고리즘의 이해 - 계산 모델

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다.

 

 

 

✔ 알고리즘이란?

 - 문제 해결을 위한 계산 과정

 - 컴퓨터 프로그램의 수학적 추상화

⭐ 계산 모델은 알고리즘이 할 수 있는 연산과 그 연산에 걸리는 비용(시간, 공간, ...)을 결정합니다. 각각의 연산의 비용을 계산하여 전부 더하면 알고리즘의 총 비용이 됩니다. 이번 강의에서는 2가지 계산 모델을 살펴봅니다.

⭐ 각 연산마다 시간 비용이 있는데 그것들을 모두 더하면 알고리즘의 실행 시간이 됩니다.

 

 

 

✔ 임의 접근 머신(Random Access Machine)

 - 거대한 배열로 만들어진 임의 접근 기억장치

 - O(1) 레지스터(각 1개의 워드)

 - O(1) 시간 안에 할 수 있는 일

    - 레지스터에 있는 워드를 다른 레지스터로 불러오기
    - 레지스터에서 (+, −, ∗, /, &, |, ˆ) 계산

    - 레지스터를 다른 레지스터에 있는 메모리에 저장

 - 워드란? w ≥ lg(메모리 크기) bit

    - 기본적인 객체가 워드에 들어맞는다고 가정

 - 현실적이고 강력함 → 추상적 개념 구현

 ⭐ lg는 log_2이다.

 

 

✔ 포인터 머신(Pointer Machine)

이중 연결 노드

 - 동적 할당된 객체

 - 객체는 O(1)개의 필드를 가짐

 - 필드 = 워드(예: 정수) 또는 객체/널을 가리키는 포인터(참조)가 될 수 있음

 - 임의접근머신(RAM)으로 구현 가능

   → 이것은 포인터 머신이 임의접근머신(RAM)보다 약한 모델이라는 것을 나타냅니다. 하지만 생각하는 방식에 변화를 주는 모델이고 실제로 많은 자료 구조들이 포인터 머신 형식으로 만들어집니다.

 

 

 

✔ 파이썬 모델

 파이썬은 두 가지 사고(RAM과 포인터 머신)를 모두 적용할 수 있습니다.

 - 임의접근머신(RAM) : "List"는 현실 세계의 배열과 같음

L[i] = L[j] + 5    →    O(1) 시간

 - 포인터 머신 : O(1)개의 속성을 가진 객체(백만 개나 n개는 안됨)

x = x.next    →    O(1) 시간

 

 파이썬에는 많은 연산이 있습니다. 그중 list를 간략하게 살펴보면 다음과 같습니다.

L.append	-	θ(1)
L = L1+L2	- L라는 빈 list 생성  - for 사용하여 L에 L1, L2 내용 추가	θ(1+|L1|+|L2|)
L1.extend	- for 사용하여 L1에 L2 내용 추가	θ(1+|L2|)
L2 = L1[i:j]	- L2라는 빈 list 생성  - for 사용하여 L2에 L1의 i부터 j까지 내용 추가	O(|L|)
x in L, L.index(x), L.find(x)	- for 사용하여 x 값이 L에 존재하는지 if로 검증	θ(|L|)
len(L)	- list는 자신의 길이를 field에 저장함	θ(1)
L.sort()	- 비교 정렬 사용	θ(|L| log |L|)

👀 tuple, str, dict, set 등의 내용은 앞으로의 강의에서 배우므로 넘어갔습니다.

 

 

 

✔ 문서 거리

 문서 거리 문제는 두 문서 D1과 D2에 대해 둘 사이의 거리를 계산하는 것입니다. 공통 단어를 이용하여 공통된 단어가 많을 경우 거리를 가깝게 하고 적을 경우 거리를 멀게 하여 문서 거리를 정의합니다.

 ⭐ 문서 거리는 유사한 문서 탐색이나 중복(위키피디아 미러 사이트와 구글)과 표절 발견 그리고 웹 검색에 적용됩니다.

 

문제를 풀기 위한 정의

 - 단어 = 영어와 숫자로 이루어진 문자열

 - 문서 = 단어의 나열 (공백, 문장 부호 등 무시)

 -  공통으로 갖는 단어를 통해 거리를 정의하고자 한다. 문서 D를 벡터로 생각합니다.

    : D[w] = 단어 w의 등장 횟수

 

알고리즘

1) 각 문서를 단어들로 쪼갠다.

2) 단어 빈도를 센다.(문서 벡터)

3) 내적을 계산한다.(& 나눈다)