MIT 6.006 Introduction to Algorithms, Spring 2020
1. Algorithms and Computation
문제란?
- input ,output이 있는 이진 관계
이진 관계란, 두 개의 집합 사이에서 정의되는 관계를 말함
알고리즘이란?
- 프로시져이다.
많은 양의 데이터를 비교하여 무엇인가 맞다고 증명할때 어떤 방법을 써야하나?
어떻게 설득할까? 이 알고리즘이 맞는지?
- 귀납적 가설을 사용한다
- Inductive Hypotesis: if first k students contain match alg returns a match before interviewing student k + 1
- 귀납적 가설
- 기저 사례 base case: 명제가 가장 작은 자연수 n=0n = 0n=0 또는 n=1n = 1n=1에서 참임을 증명
- 귀납 단계 Inductive Step:
- 귀납적 가설: 임의의 자연수 k에대해 명제가 참이라고 가정하고, 이를 바탕으로 k+1에서도 명제가 참임을 증명
어떻게 알고리즘이 빠른지 측정할 수 있나?
- 그냥 빠른게 효율적인건 아니다
- 시간을 잰다?
- 컴퓨터의 힘에 따라 시간이 굉장히 다를 것이다 (IBM's research computer vs my computer)
- Don't measure time, instead count ops
- Expect performance to depend on size of our input
- O(n) upper bound Ω(n) lower bound θ both
32비트 CPU라는 말은 참조할 수 있는 메모리의 주소를 32비트로만 나타낼 수 있다는 말이다. 그럼 메모리 주소는 총 2^32이 된다. 약 4GB이다. 따라서, 물리적으로 최대 램을 4GB밖에 못쓴다.
2. Data Structures and Dynamic Arrays
강의 초입 부분에 인터페이스와 자료구조의 다른점을 짚고 넘어 감.
Interface (API / ADT)
- 인터페이스(API, ADT 추상 데이터 타입)에 대한 내용
- "무엇"에 집중
Specification (어떤 명세를 가지는지)
- 인터페이스의 명세는 인터페이스가 어떤 기능을 제공하는지를 기술
- 사용자가 인터페이스를 통해 수행할 수 있는 작업들을 정의
What data can store (어떤 데이터를 저장할 수 있는지)
- 인터페이스가 다룰 수 있는 데이터의 종류를 정의
- 예를 들어, 리스트 인터페이스는 정수, 문자열 등 다양한 타입의 요소들을 저장할 수 있다는 둥.
What operations are supported (어떤 연산을 지원하는지)
- 인터페이스를 통해 수행할 수 있는 연산들을 정의합
- 예를 들어, 리스트 인터페이스는 요소 추가(add), 삭제(remove), 검색(find) 등의 연산을 지원할 수 있다는 둥.
자료 구조
- 자료 구조는 데이터를 실제로 어떻게 저장하고 관리할지를 정의
- "어떻게"에 집중
Representation (어떻게 표현할지)
- 자료 구조의 표현은 데이터를 메모리나 다른 저장 매체에 어떻게 배치할지를 정의
- 예를 들어,
- 배열: 연속된 메모리 블록에 데이터를 저장
- 링크드 리스트: 각 요소가 다음 요소에 대한 참조를 포함하는 방식으로 데이터를 저장
How to store data (어떻게 저장할지)
- 데이터를 실제로 저장하는 방법을 구체적으로 설명
- 예를 들어,
- 배열: 인덱스를 통해 요소에 접근
- 트리: 노드와 간선으로 데이터를 저장
Algorithms to support operations (어떻게 연산할지 알고리즘)
- 자료 구조가 제공하는 연산들을 어떻게 구현할지를 설명
- 예를 들어 이진 검색 트리는 삽입, 삭제, 검색 연산을 효율적으로 수행하기 위한 알고리즘을 제공
Word RAM(Random Access Machine) Model
- 우리가 더 흥미로운 데이터 구조에 도달할수록 이 모델이 정말로 필요하게 될 것이며, 점점 더 이 모델에 의존하게 될 것이다.
- 자세한 건 Word RAM Model 페이지에 정리해둠