Lecture 1. 알고리즘 소개
1. 수업 목표
The goal of this class is to teach you to solve computation problems,
and to communicate that your solutions are correct and efficient.
이 수업의 목표는 계산 문제를 해결하는 방법을 배우게 하고,
풀이가 올바르고, 효율적임을 전달할 수 있도록 하는 것이다.
다시 말해 단순히 “정답”만 내는 것이 아니라,
✔️ 왜 맞는지 (correctness),
✔️ 얼마나 효율적인지 (efficiency),
✔️ 그것을 어떻게 표현하는지 (communication)
배울 것이다.
* computation problem: 계산을 통해 해결 할 수 있는 문제
2. Problem
2-1. 문제란? ( Problem )
Binary relation from problem inputs to correct outputs
Problem이란 문제에서 제공하는 입력에서 그에 상응하는 정확한 아웃풋으로 연결되는 관계
* Binary relation: 이진 관계 → 두 집합 사이의 관계, 즉 (입력, 출력) 쌍들의 집합
2-2. 문제를 어떻게 정의할까? ( how to define a computation problem )
Usually don’t specify every correct output for all inputs (too many!)
보통 각각의 입력에 대해 모든 올바른 출력을 일일이 명시하지는 않는다 (너무 많기 때문!)
문제를 정의할 때, 예를 들어 문제가 “두 수를 더해라.”인 경우
(1, 2) → 3,
(10, 20) → 30,
(1000, 9999) → 10999 …
이렇게 경우의 수를 전부 나열하며 문제를 정의하지 않고,
“두 입력 정수 a, b의 합을 반환하라” 같은 출력 규칙으로 정의한다.
Provide a verifiable predicate (a property) that correct outputs must satisfy
올바른 출력이 반드시 만족해야 하는 검증 가능한 조건(속성)을 제공하라
문제를 정의할 때 모든 올바른 출력을 다 나열하는 게 아니라, 올바른 아웃풋은 이런 조건을 만족해야 한다
라는 명확한 기준을 써주어라.
예시1) 문제: “두 수의 합을 구하라.”
verifiable predicate (출력 검증 조건): 출력값은 입력 두 수의 합과 같아야 한다. 결과는 True / False가 되도록 함
예: 입력 (3, 5) → 출력 8, 여기서 8은 3 + 5 == 8을 만족.
예시2) 문제: “그래프에서 최단 경로를 구하라.”
verifiable predicate (출력 검증 조건): 경로의 길이는 가능한 경로들 중 최소여야 한다.
* verifiable → 검증 가능한, 확인할 수 있는
* predicate → 어떤 조건을 참/거짓을 판단할 수 있는 기준, 논리적 표현. return True/False
* property → 어떤 대상(여기서는 출력)이 가져야 할 속성, 특징
6.006 studies problems on large general input spaces
이 알고리즘 강의는 크고 일반적인 입력 공간에서의 문제들을 연구한다
이 알고리즘 강의는 특정한 소수의 입력에만 맞춘 문제나,
제한된 작은 범위의 문제만 다루는 게 아니라,
아주 큰 입력 공간(예: 수백, 수천, 수억 개의 가능한 입력)에 대해,
일반적으로 적용 가능한 알고리즘 문제들을 연구한다.
small -> n (general input) 으로 확장해서 문제 접근할 거임
Not general: small input instance
– Example: In this room, is there a pair of students with same birthday?
일반적이지 않은 경우: 작은 입력 사례
“이 방 안에서 같은 생일을 가진 학생 쌍이 있을까?” → 특정한, 작은 규모의 문제 (지금 이 방에 있는 학생들만 봄)
General: arbitrarily large inputs.
– If birthday is just one of 365, for n > 365, answer always true by pigeon-hole
– Assume resolution of possible birthdays exceeds n (include year, time, etc.)
– Example: Given any set of n students, is there a pair of students with same birthday?
일반적인 경우: 임의로 큰 입력들을 생각
사람 수를 n으로 확장한 경우:
생일이 1~365일 중 하나라고만 가정하고, 사람 수를 항상 같은 생일 가진 쌍이 존재한다 하지만
생일을 n으로 확장한 경우:
“생일”의 구분을 연도, 시간, 분, 초까지 확장해서 구분할 수 있게 만들면,
사람 수 n이 커져도 무조건 중복된 생일이 있다고는 말할 수 없게 된다.
예: “어떤 학생 집합 이 주어졌을 때, 같은 생일을 가진 학생 쌍이 존재하는가?”
→ 입력의 크기를 임의로 키우고, 문제를 일반화한 형태이다
* pigeonhole principle: 비둘기 수가 집 수보다 많으면 어떤 집에는 반드시 두 마리 이상 들어간다는 원리
* resolution: 구분 정도 resolution을 높이면 경우의 수가 많아져서 중복 가능성이 줄어듦 (365 일 X 24 시간 X 60 초), 해상도
resolution 낮은 경우
2000, 01, 01일에 태어난 사람
2000, 01, 02일에 태어난 사람
2000, 01, 03일에 태어난 사람
resolution 높은 경우
2000, 01, 01, 00:00 01초에 태어난 사람
2000, 01, 01, 00:00 02초에 태어난 사람
2000, 01, 01, 00:00 03초에 태어난 사람
* arbitrarily: 임의의, 제한없이 자유롭게
3. Algorithm
Algorithm is the procedure mapping each input to a single output (deterministic)
Algorithm is some kind of a function that takes inputs and then maps to a single output.
알고리즘이란 무엇을 넣으면 무엇을 내놓을지 정해주는 절차
일종의 함수로, 입력들을 받아서 하나의 아웃풋에 매핑하는 것
입력 → 알고리즘 → 출력
* deterministic: 동일한 input을 넣으면 항상 동일한 output이 나오는 것.
예) [2,1,3] → [1,2,3] 로 항상 정렬해서 나온 경우 값이 같음
랜덤 알고리즘은 나오는 결과가 달라서 deterministic 아님
Algorithm solves a problem if it returns a correct output for every problem input
알고리즘으로 모든 문제 입력에 대해 올바른 출력을 반환했을 때 그 문제를 해결했다고 할 수 있다
특정 입력에서만 맞는 건 불완전한 알고리즘이고, 모든 입력에서 문제의 정의에 맞게 정답을 내야 “문제를 해결한다”고 인정
Example: An algorithm to solve birthday matching
– Maintain a record of names and birthdays (initially empty)
– Interview each student in some order
- If birthday exists in record, return found pair!
- Else add name and birthday to record
– Return None if last student interviewed without success
생일이 같은 학생 쌍을 찾는 알고리즘 예시
1. 이름과 생일을 기록하는 자료를 만든다 (처음에는 비어있음)
2. 학생들을 한 명씩 순서대로 물어본다
3. 이미 같은 생일이 기록에 있으면 “found pair!” 리턴 - 종료
4. 없으면 이름과 생일을 기록에 추가한다
→ 다음 학생으로 넘어감
5. 마지막 학생까지 확인했는데도 못 찾으면 None 반환 - 종료
4. Correctness
Programs/algorithms have fixed size, so how to prove correct?
작고 고정된 알고리즘 코드로 무한한 입력을 올바른 결과를 낸다는 걸 어떻게 증명할까?
For small inputs, can use case analysis
작은 입력에 대해서는 case analysis를 사용할 수 있다
* case analysis: 모든 가능한 경우(case)를 하나하나 살펴보는 분석. 일일이 인풋 다 넣어서 결과 맞나 보는 방법
For arbitrarily large inputs, algorithm must be recursive or loop in some way
하지만 임의로 큰 입력에 대해서는 알고리즘이 어떤 식으로든 재귀(recursive)나 반복(loop)을 포함해야 한다.
* recursive: 함수가 자기 자신을 다시 호출하면서 문제를 점점 더 단순하게 쪼갠 후 마지막에 더 이상 쪼갤 수 없는 base case에 도달하면 거기서부터 차례차례 답을 쌓아 올라가는 방식
Must use induction (why recursion is such a key concept in computer science)
귀납법(induction)을 반드시 사용해야 한다 (이것이 재귀가 컴퓨터 과학에서 핵심 개념인 이유다).
* Induction (수학적 귀납법)
→ n = 1 같은 작은 기본 케이스가 참이고,
→ n에서 n+1로 넘어갈 때도 참이면
→ 모든 n에 대해 성립한다고 증명할 수 있는 방법
예: 피보나치 수열 (Fibonacci Sequence): 이전 두 항의 합이 다음 항이 되는 수열이다
| n | F(n) |
| 0 | 0 |
| 1 | 1 |
| 2 | 1 (=0+1) |
| 3 | 2 (=1+1) |
| 4 | 3 (=1+2) |
| 5 | 5 (=2+3) |
| 6 | 8 (=3+5) |
| 7 | 13 (=5+8) |
| ... | ... |
base case: f(0), f(1)은 알고 있음
induction: f(n) = f(n-1) + f(n-2)로 쌓아올림 - Recursion 사용
이걸 귀납적으로 증명하면:
→ 작은 값에서 맞다.
→ 작은 값에서 큰 값으로 넘어갈 때도 성립한다?
→ 오 그러면 모든 값에서 맞다!
Example: Proof of correctness of birthday matching algorithm
– Induct on k: the number of students in record
– Hypothesis: if first k contain match, returns match before interviewing student k + 1
– Base case: k = 0, first k contains no match
– Assume for induction hypothesis holds for k = k’ , and consider k = k’ + 1
– If first k’ contains a match, already returned a match by induction
– Else first k’ do not have match, so if first k’ + 1 has match, match contains k’ + 1
– Then algorithm checks directly whether birthday of student k’ + 1 exists in first k’
다음은 birthday matching algorithm이 맞는지 확인하기 위해
정확성 증명을 귀납법으로 증명하는 예제를 설명하고 있다
알고리즘 내용은 다음과 같다.
학생들을 한 명씩 인터뷰하는 과정을 보기 편하게 표로 정리해 보았다.
| 단계 (인터뷰 순서) | 기록된 학생 수 k | 귀납 가설 k′ (이전 단계) | 다음 단계 (현재 단계) |
|
| 인터뷰 시작 전 | 0 명 | 아직 아무도 없음 | ||
| 첫 번째 학생 인터뷰 | 1 명 | 1 단계 | 아직 match 없음, 기록에 추가 | |
| 두 번째 학생 인터뷰 | 2 명 | 1 단계 | 2 단계 | 첫 번째 학생과 생일 비교 → match? |
| 세 번째 학생 인터뷰 | 3 명 | 2 단계 | 3 단계 | 앞 두 명과 생일 비교 → match? |
| 네 번째 학생 인터뷰 | 4 명 | 3 단계 | 4 단계 | 앞 세 명과 생일 비교 → match? |
| … | … | … | … | 계속 같은 방식으로 진행 |
귀납법 용어 설명
induction variable (귀납 변수)
k = 학생 인터뷰를 몇 명 끝냈는지 현재 기록에 있는 학생 수를 변수 k에 담았다.
induction hypothesis (귀납 가설)
어떤 에서 명제가 참이라고 가정.
→ 예: “학생 명까지는 알고리즘이 문제없이 동작했다”고 가정.
알고리즘이 문제없이 동작했다는 건
처음 명의 학생 안에 match(같은 생일 쌍)가 있으면,
→ 번째 학생을 인터뷰하기 전에 이미 match를 찾아서 리턴함
Base case:
가장 작은 경우에서 성립하는지 확인
예: 또는 에서 참인지 확인
→ 아직 기록에 아무도 없음 → 당연히 match 없음 → 알고리즘은 진행
inductive step (귀납 단계)
귀납적 관점에서 알고리즘 실행 단계
Base case에서 출발해,
이전 단계 → 다음 단계가 참이면
무한히 이어지는 모든 단계에서 전부 참이라고 결론낼 수 있음.
부터 출발해서
단계에서 가설이 맞다고 가정하고
단계에서도 가설이 유지되는 지 확인하는 것
→ 이게 바로 귀납법 증명 방식
5. Efficiency
5-1. Performance Analysis
How fast does an algorithm produce a correct output?
알고리즘이 얼마나 빨리 (즉, 얼마나 효율적으로) 올바른 결과를 내놓느냐?
– Could measure time, but want performance to be machine independent
실제 실행 시간을 재볼 수도 있지만, 그건 컴퓨터 성능(하드웨어)에 따라 달라질 수 있으니
기계에 의존하지 않는 방식으로 성능을 평가하는 방법이 없을까?
– Idea! Count number of fixed-time operations algorithm takes to return
알고리즘이 정답을 내놓기까지 고정된 시간에 처리되는 연산의 개수를 세자!
– Expect to depend on size of input: larger input suggests longer time
연산 개수는 입력 크기에 따라 달라질 거라고 예상한다.
입력이 커지면 연산도 늘어나고 시간도 늘어나겠죠?
– Size of input is often called ‘n’, but not always!
입력의 크기를 보통 n이라고 부르지만, 항상 n만 쓰는 건 아니다.
– Efficient if returns in polynomial time with respect to input
알고리즘이 입력 크기(n)에 대해 다항 시간(polynomial time) 안에 정답을 주면
그걸 효율적이라고 본다.
효율적 예: O(n), O(n²), O(n³), O(n⁵) 같은 시간 복잡도
Sometimes no efficient algorithm exists for a problem!
효율적인(다항 시간 안에 끝나는) 알고리즘이 아예 존재하지 않을 때도 있다!
비효율적 예: O(2ⁿ) (지수 시간), O(n!) (팩토리얼 시간)
정리하면
- 실제 실행 시간을 재기보다는, 기계와 상관없이 기본 연산 개수로 평가한다.
- 그 연산 개수는 보통 입력 크기 에 따라 결정된다.
- 다항 시간 안에 답을 주면 “효율적”이라고 본다.
5-2 Asymptotic Notation
asymptotic 분석이란?
작은 입력에서는 실행 시간이 복잡하게 보일 수 있지만, 입력이 매우 커질수록 실행 시간의 성장 패턴은 일정한 규칙을 따르게 되는데
이때 n → ∞ (무한히 커질 때)를 보는 것이 asymptotic 분석이다.
알고리즘을 비교할 때 정확한 시간보다는 성능 추세가 더 중요해서 asymptotic 분석을 쓴다.
Asymptotic Notation?
ignore constant factors and low order terms
상수 배수와 낮은 차수 항은 무시하고, 입력이 커질 때 어떤 항이 지배적인지만 본다
5n + 3 → O(n),
n² + 100n + 10 → O(n²)
Upper bounds (O), lower bounds (Ω), tight bounds (Θ) ∈, =, is, order
| 기호 | 이름 | 예시 |
| O(g(n)) | 최악의 상한 (Upper bound) | "최대 이 정도 걸린다" |
| Ω(g(n)) | 최선의 하한 (Lower bound) | "최소 이 정도는 걸린다" |
| Θ(g(n)) | 정확한 차수 (Tight bound) | "정확히 이 정도 걸린다" |
Time estimate below based on one operation per cycle on a 1 GHz single-core machine
아래 시간 추정치는, 1초에 10억 번 연산이 가능한 단일 코어 컴퓨터에서, 연산 하나를 1클럭 사이클에 처리한다고 가정할 때의 시간 개념이다
컴퓨터는 CPU clock cycle이라는 단위로 연산을 수행한다.
one operation per cycle 고로 CPU의 클럭 사이클 한 번에 연산 하나를 수행한다고 가정하겠다는 뜻이다.
현실에서는 한 사이클에 여러 연산을 하기도 하고, 명령어마다 다르지만, 단순화를 위해 이렇게 가정한다.
1 GHz = 10⁹ cycles per second (10억 사이클/초). 1초에 최대 10억 번의 연산
single-core machine: 요즘은 CPU에 여러 개의 코어가 있지만, 이 가정에서는 하나의 코어만 사용한다 가정, 왜냐면 알고리즘 분석은 보통 단일 프로세스 기준으로 하기 때문이다.
Particles in universe estimated < 10^100
우주 전체에 있는 입자 갯수가 10^100보다 작다
6. Model of Computation
CPU bit: 한 번에 다룰 수 있는 데이터의 최대 크기
word는 CPU가 사용할 수 있는 램(메모리)의 크기를 나타낸다.
64bit CPU의 경우 64bit가 1word가 된다.
Specification for what operations on the machine can be performed in O(1) time
컴퓨터에서 어떤 연산들이 O(1) 시간에 수행될 수 있는지 규정
O(1): 입력 크기에 상관없이 고정된 시간에 실행됨
예: 덧셈 하나, 변수 하나 읽기 → 크기에 상관없이 한 번에 끝난다고 가정
Model in this class is called the Word-RAM
이 수업에서 사용하는 계산 모델 이름은 Word-RAM
RAM: Random Access Machine, 랜덤 접근 가능 메모리 모델
Word: 특정 비트 수(w bits)의 데이터 단위
Machine word: block of w bits (w is word size of a w-bit Word-RAM)
머신 워드란? → 개의 비트로 구성된 블록
예: 32-bit 시스템 → word 크기 = 32비트
64-bit 시스템 → word 크기 = 64비트
Memory: Addressable sequence of machine words
메모리란? → 워드들이 순서대로 나열된 공간, 각각의 워드는 주소로 접근 가능.
예: 배열처럼, 각 칸에 0, 1, 2… 같은 인덱스(주소)가 붙어있음
Processor supports many constant time operations on a O(1) number of words (integers):
프로세서는 하나 또는 소수( O(1) 개)의 워드에 대해 여러 가지 연산을 상수 시간에 지원한다.
즉, 워드 하나 처리하는 건 빠름
연산 예시들
– integer arithmetic: (+, -, , //, %)
– logical operators: (&&, ||, !, ==, <, >, <=, =>)
– (bitwise arithmetic: (&, |, <<, >>, ...))
– Given word a, can read word at address a, write word to address a
주소 를 주면 a 위치에서 워드를 읽을 수 있고, a 위치에 워드를 쓸 수도 있다.
이것도 O(1) 시간에 수행된다고 가정
Memory address must be able to access every place in memory
메모리 주소는 메모리 내 모든 위치를 가리킬 수 있어야 함.
즉, 주소 범위가 전체 메모리 크기를 커버해야 한다
- Requirement: w ≥ # bits to represent largest memory address, i.e., log₂ n
(word 크기) ≥ 최대 메모리 주소를 표현할 수 있는 비트 수.
예: 개의 메모리 셀이 있으면, 최대 주소 = n, 이걸 표현하려면 log₂(n) 비트 필요
왜 log₂(n)? 비트로 표현할 수 있는 경우의 수
컴퓨터에서 1비트는 2개의 주소를 표현할 수 있다: 0, 1
1비트 → 2개
- 0, 1
2비트 → 4개
- 00, 01, 10, 11
3비트 → 8개
- 000, 001, 010, 011, 100, 101, 110, 111
4비트 → 2^4=개
8비트 → 2^8 개
16비트 → 2^{16} 개
32비트 → 2^{32} billion (약 43억 개)
일반적으로 k비트 → 2^k개의 서로 다른 값을 표현 가능
- 32-bit words → max ∼ 4 GB memory, 64-bit words → max ∼ 16 exabytes of memory
32비트 시스템 → 개 주소 ≈ 최대 약 4GB 주소 가능.
64비트 시스템 → 개 주소 ≈ 최대 약 16엑사바이트 주소 가능
Python is a more complicated model of computation
파이썬은 훨씬 복잡한 계산 모델이다.
왜냐하면 파이썬은 무제한 정수, 복잡한 객체, 해시 테이블 등 고급 기능을 제공하기 때문이다
Word-RAM처럼 간단한 모델로 다루기 어렵다.
7. Data Structure
A data structure ?
a way to store non-constant data, that supports a set of operations.
데이터 구조란 고정되지 않은 (즉, 변할 수 있는) 데이터를 저장하는 방법이면서,
그 위에서 수행할 수 있는 일련의 연산(작업)들을 지원하는 것
interface ?
A collection of operations
그 자료구조가 외부에 제공하는 연산들의 모음
예를 들어 어떤 자료구조는 삽입, 삭제, 검색 같은 연산들을 제공한다
– Sequence interface: Extrinsic order to items (first, last, nth)
아이템들이 외부에서 주어진 순서를 따름. 첫 번째, 마지막, n번째 요소 같은 식으로 순서가 있다
– Set interface: Intrinsic order to items (queries based on item keys)
아이템들이 순서보다 내부 속성(키 값)을 기준으로 다뤄짐. 예: “이 키 값 가진 아이템 있어?” 같은 검색 연산 중심이다.
Data structures may implement the same interface with different performance
같은 인터페이스(같은 기능 목록)를 제공하더라도, 자료구조마다 성능(속도, 효율)은 다를 수 있다.
예: 배열로 구현한 검색과, 해시셋으로 구현한 검색의 속도는 다르다
Example: Static Array - fixed width slots, fixed length, static sequence interface
슬롯(칸)의 크기가 고정돼 있고 길이도 고정돼 있으며 시퀀스 인터페이스(순서 기반 접근)를 제공함
– StaticArray(n): allocate static array of size n initialized to 0 in Θ(n) time
StaticArray(n) 함수는 크기 인 고정 배열을 만들고, 모든 값을 0으로 초기화하는데, 이 작업은 Θ(n) 시간이 걸린다
– StaticArray.get at(i): return word stored at array index i in Θ(1) time
StaticArray.get at(i)는 인덱스 에 저장된 값을 반환하는데, 칸 크기는 그대로 유지하기 때문에,
이건 Θ(1)으로 가능함
– StaticArray.set at(i, x): write word x to array index i in Θ(1) time
StaticArray.set at(i, x)는 인덱스 위치에 값 를 교체하는데,
칸 크기는 그대로 유지하고, 데이터만 바꾸는 거라 이것도 Θ(1)으로 가능함
Stored word can hold the address of a larger object
배열에 저장된 하나의 word는, 실제로 더 큰 객체의 주소를 담을 수도 있음 (즉, 포인터처럼 동작할 수 있다는 의미)
Like Python tuple plus set at(i, x), Python list is a dynamic array (see L02)
Python의 튜플(tuple)은 저장된 값을 바꿀 수 없지만, set at(i, x) 기능이 추가되면 수정 가능한 배열이 된다.
Python의 리스트(list)는 사실상 동적 배열(dynamic array)이다.
(Static Array vs dynamic array 는 Lecture 2 강의에서 다룰 예정이다)
같은 생일 찾는 알고리즘
def birthday_match(students):
'''
Find a pair of students with the same birthday
Input: tuple of student (name, bday) tuples
Output: tuple of student names or None
'''
n = len(students) # O(1) - students 배열의 길이 (학생 수)를 n에 저장
record = StaticArray(n) # O(n) - 길이가 n인 StaticArray 생성
for k in range(n): # n
(name1, bday1) = students[k] # O(1) - 확인할 학생 생일 담음
# Return pair if bday1 in record
for i in range(k): # k - 0부터 k까지 하나씩 확인
(name2, bday2) = record.get_at(i) # O(1)
if bday1 == bday2: # O(1)
return (name1, name2) # O(1)
record.set_at(k, (name1, bday1)) # O(1)
return None # O(1)
Example: Running Time Analysis
이 알고리즘에 대해 시간 복잡도를 계산해 보자.
Two loops: outer k ∈ {0, . . . , n − 1}, inner is i ∈ {0, . . . , k}
이 알고리즘은 학생 명을 한 명씩 돌면서,
이전까지 인터뷰한 학생들의 생일과 하나하나 비교해 본다.
그래서 외부 루프 번, 내부 루프(k)도 최대 까지 반복된다.
학생 리스트에서 한 명씩 이름 + 생일을 꺼내와서,
이미 본 학생들 기록과 모두 비교하는 방식이다.
- 1번째 학생: 비교할 대상 없음.
- 2번째 학생: 앞에 1명과 비교.
- 3번째 학생: 앞에 2명과 비교.
- 4번째 학생: 앞에 3명과 비교.
- …
- n번째 학생: 앞에 (n-1)명과 비교.
Running time
런타임을 다음과 같은 수식으로 나타낼 수 있다. 자세한 설명은 조금 아래를 보기 바란다
for loop 안에 for loop 이라 n^2
Quadratic in n is polynomial. Efficient? Use different data structure for record!
8. How to Solve an Algorithms Problem
1. Reduce to a problem you already know (use data structure or algorithm)
문제를 해결할 때 새 알고리즘 짤려고, 일단 기존에 있는 자료 구조, 알고리즘을 써라
| Search Problem (Data Structures) | Sort Algorithms | Shortest Path Algorithms |
| Static Array (L01) | Insertion Sort (L03) | Breadth First Search (L09) |
| Linked List (L02) | Selection Sort (L03) | DAG Relazation(L11) |
| Dynamic Array (L02) | Merge Sort (L03) | ㄴ Depth First Search (L10) |
| Sorted Array (L03) | Counting Sort (L05) | ㄴ Topological Sort (L10) |
| Direct-Access Array (L04) | Radix Sort (L05) | Bellman-Ford (L12) |
| Hash Table (L04) | AVL Sort (L07) | Dijkstra (L13) |
| Balanced Binary Tree (L06) | Heap Sort (L08) | Johnson (L14) |
| Binary Heap (L08) | Floyd-Warshall (L18) |
2. Design your own (recursive) algorithm
기존에 있는 걸로 안되면 새로 디자인 해라
- Brute Force
- Decrease and Conquer
- Divide and Conquer
- Dynamic Programming (L15-L19)
- Greedy / Incremental
출처
자료: Lecture 1: Introduction Note - 6.006 Introduction to Algorithm - MIT Open Course
https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/mit6_006s20_lec1/
강의: https://youtu.be/ZA-tUyM_y7s?si=WXk9ulT3DMrDyOVa
'Computer Science > MIT Introduction to Algorithms 6.006' 카테고리의 다른 글
| Lecture 6: Binary Trees, Part 1 이진 트리 (2) | 2025.06.08 |
|---|---|
| Lecture 5: Linear Sorting (3) | 2025.06.06 |
| Lecture 4: Hashing 해시 (0) | 2025.06.03 |
| Lecture 3: Sorting 정렬 (0) | 2025.06.02 |
| Lecture 2: Data Structures (0) | 2025.05.30 |
댓글