본문 바로가기

Computer Science/MIT Introduction to Algorithms 6.00611

조합, 순열 (combination, permutation) 조합(conbination)과 순열(permutation) 둘 다 n 개 중에서 r 개를 선택하여 나오는 수를 계산하는 방법이다순서를 상관없으면 조합이고, 순서를 고려하면 순열이다 1. 순열 (nPr)n개 중에서 r개를 순서가 있도록 고르는 경우의 수 예를 들어, 친구 5명(A, B, C, D, E) 중에서 3명을 뽑아서 1등, 2등, 3등을 뽑는 상황일 때.즉, 순서가 중요한 경우입니다. 1. 첫 번째 자리에 올 수 있는 사람은?A, B, C, D, E → 총 5명 중에서 누구든 올 수 있음 → 5가지 2. 두 번째 자리는?첫 번째에서 1명 이미 선택했으니 남은 사람은 4명 → 4가지 3. 세 번째 자리는?이미 2명 골랐으니 남은 사람은 3명 → 3가지 5 x 4 x 3 = 60 즉 5명 중에서 .. 2025. 6. 23.
Lecture 10: Depth-First Search (깊이 우선 탐색) Lecture 10: Depth-First Search 0. Previously 복습하기 • Graph definitions (directed/undirected, simple, neighbors, degree)그래프 정의 (방향있는 그래프 / 무방향 그래프, 단순 그래프, 이웃 정점, 차수)→ 그래프는 정점(vertex)들과 간선(edge)들로 구성되며, → 간선에 방향이 있으면 방향 그래프, 없으면 무방향 그래프라 합니다.→ 단순 그래프(simple): 자기 자신으로 가는 간선이 없고, 간선이 중복되지 않는 그래프→ 이웃(neighbors): 각 정점에 연결된 다른 정점들→ 차수(degree): 이들 이웃과 연결된 간선의 수 • Graph representations (Set mapping verti.. 2025. 6. 18.
Lecture 9: Breadth-First Search (BFS) 너비 우선 탐색 Lecture 9: Breadth-First Search (BFS) 너비 우선 탐색이 강의에서는 BFS라는 알고리즘을 알아보겠습니다 1. Graph Applications• Why? Graphs are everywhere!왜 그래프를 배우는가? 그래프는 어디에나 존재한다!다양한 시스템이나 문제들이 그래프로 표현되는 경우가 많기 때문에 그래프를 배우는 것이 중요합니다. • any network system has direct connection to graphs모든 네트워크 시스템은 그래프와 직접적으로 연결되어 있다 • e.g., road networks, computer networks, social networks예: 도로망, 컴퓨터 네트워크, 소셜 네트워크각각 도로나 사람(vertex)과 그 사이의 .. 2025. 6. 15.
Lecture 8: Binary Heaps 바이너리 힙, 이진 힙 Lecture 8: Binary Heaps바이너리 힙은 특정 연산에 최적화된 트리 기반의 자료구조입니다.주로 우선순위 큐(priority queue)를 구현하는 데 사용됩니다. 1. Priority Queue Interface이전에 배운 자료 구조 * Stack: 가장 나중에 삽입된 데이터 먼저 뺌 * Queue: 가장 먼저 삽입된 데이터 먼저 뺌 오늘 배울 우선 순위 큐가장 우선 순위가 높은 데이터를 먼저 뺌 트리에서 root에 위치한 데이터 Priority Queue Interface여러 항목을 관리하면서, 가장 중요한(우선순위가 높은) 항목을 빠르게 접근하거나 제거할 수 있도록 합니다. • Keep track of many items, quickly access/remove the most im.. 2025. 6. 14.
Lecture 7: Binary Trees, Part 2: AVL 7강 : Binary Trees II: AVL1. Last Time and Today’s Goal 2. Height Balance • How to maintain height h = O(log n) where n is number of nodes in tree?트리의 노드 수가 n일 때, 높이 h를 O(log n)으로 유지하려면 어떻게 해야 할까요?즉, 삽입이나 삭제가 있어도 트리가 너무 한쪽으로 치우쳐 깊어지지 않도록 높이를 로그 수준으로 유지하는 방법이 없을까요? • A binary tree that maintains O(log n) height under dynamic operations is called balanced삽입, 삭제 등 동적 연산이 일어나도 높이가 O(log n)으로 유지되는 이.. 2025. 6. 9.
Lecture 6: Binary Trees, Part 1 이진 트리 Lecture 6: Binary Trees, Part 1 이진 트리 1. Previously and New Goal 이전에 배운 자료구조들의 시간 복잡도를 표로 나타낸 것이다. 2. How? Binary Trees! 이진 트리 Pointer-based data structures (like Linked List) can achieve worst-case performance포인터 기반 자료구조(예: 링크드 리스트)는 최악의 경우 성능이 매우 나쁠 수 있다. 잠깐 이 전에 배운 Linked list 연결 리스트를 복습해보면Linked list 연결 리스트는 일렬로 쭉 이어진 선형 구조였다. 각 노드는 값(data) + 다음 노드(next) 에 대한 포인터로 구성되어 있는 자료 구조이다.이 링크드 리.. 2025. 6. 8.
Lecture 5: Linear Sorting Lecture 5: Linear Sorting 1. Review 복습Comparison search lower bound: any decision tree with n nodes has height ≥ ⌈log₂(n+1)⌉−1비교 기반 탐색 알고리즘은 최소한 ⌈log₂(n+1)⌉−1 높이의 결정 트리를 가진다.즉, 어떤 비교 기반 탐색을 사용하더라도 최소 log(n) 만큼은 비교해야 한다 Can do faster using random access indexing: an operation with linear branching factor!"하지만 비교 기반이 아닌 방법, 예를 들어 랜덤 액세스 인덱싱을 사용하면, 브랜칭 팩터가 선형(즉, 한 번에 많은 선택지 접근 가능)이라서 더 빠르게 탐색할 수 있다.. 2025. 6. 6.
Lecture 4: Hashing 해시 Lecture 4: Hashing이 전 강의에서 배운 Array, Sorted Array의 시간 복잡도를 아래처럼 다뤄보았다. Idea! Want faster search and dynamic operations.아이디어! 더 빠른 검색과 동적 연산을 하고 싶다.이 전에 배운 자료구조 (Sorted Array)에서 find(k) 같은 검색 연산은 보통 O(log n) 시간에 동작한다. Can we find(k) faster than Θ(log n)?아이템 탐색(Search)인 find(k) 연산을 Θ(log n)보다 더 빠르게 할 수는 없을까? Answer is no (lower bound)! (But actually, yes...!?)답은 아니다 (최소한), 하지만 사실, 할 수 있다비교 기반에서는 O.. 2025. 6. 3.
Lecture 3: Sorting 정렬 검정색 볼드체: MIT에서 제공하는 자료에 나오는 내용 그대로 적음 검은색 글자: 자료 내용 해석파란색 글자: 자료에는 없지만 추가 설명을 적어 놓은 것 Lecture 3: Sorting 1. Set Interface 이 전 강의에서 아이템 순서가 있는 인터페이스는 Sequence Interface이고, 아이템 순서가 없지만 아이템 중복도 없는 인터페이스를 Set Interface라고 하였다. Containerbuild(X)given an iterable X, build set from items in X len()return the number of stored itemsStaticfind(k)return the stored item with key kDynamicinsert(x)add x to se.. 2025. 6. 2.
Lecture 2: Data Structures Lecture 2: Data Structures1. Data Structure Interfaces 1-1. data structure?A data structure is a way to store data, with algorithms that support operations on the data데이터 구조는 데이터를 저장하는 방법이다. 그리고 저장된 데이터를 다루는 알고리즘을 함께 제공한다 배열, 연결 리스트, 해시맵 → 단순히 값만 저장하는 게 아니라 값을 넣기, 찾기, 꺼내기 같은 연산을 어떻게 할지까지 포함한다. 1-2. interface?Collection of supported operations is called an interface (also API or ADT)데이터 구조가 제공하는 .. 2025. 5. 30.
Lecture 1: Introduction - MIT Introduction to Algorithm 6.006 알고리즘 소개 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. Prob.. 2025. 5. 28.

티스토리툴바