자료구조 & 알고리즘
20개 글
- A*내비게이션 앱으로 목적지까지의 경로를 검색한다고 하자.
- Best-First Search그래프 탐색 알고리즘은 어떤 노드를 먼저 확장할지 결정해야 한다.
- Breadth-First SearchBFS의 동작 원리는 단순하다.
- Computational ThinkingComputational Thinking을 한마디로 정의하자면 컴퓨터 입장에서 생각하기다.
- Depth-First SearchDFS는 미로를 탐험하는 것에 비유할 수 있다.
- Heap힙에는 두 가지 변형이 있다.
- Heap Sort힙 정렬은 우선순위 큐에서 원소를 하나씩 꺼내면 자동으로 정렬된다는 관찰에서 출발한다.
- Karatsuba Multiplication두 개의 $n$자리 정수 $x$와 $y$를 곱한다고 하자.
- Master Theorem병합 정렬의 시간 복잡도를 구한다고 하자.
- Minimax Algorithm출발지에서 목적지로 향하는 최적의 경로를 찾는 일반적인 탐색 문제에서는 에이전트 혼자 목표를 향해 나아가지만, 게임에서는 나의 이익을 최소화하려는 상대방이 존재한다.
- Monte Carlo Tree Search어떤 게임을 수행하는 컴퓨터 유저를 설계할 때, 기존의 핵심 알고리즘은 미니맥스 알고리즘이었다.
- Priority Queue우선순위 큐는 최소한 다음 세 가지 연산을 지원해야 한다.
- Queue큐의 가장 핵심적인 특징은 먼저 들어간 자료가 먼저 나온다는First-In-First-Out, FIFO 것이다.
- Stack모든 핵심 연산이 $O(1)$이라는 점이 스택의 강점이다.
- Strassen Algorithm$n \times n$ 행렬 $A$와 $B$의 곱 $C = AB$를 정의대로 계산하면 각 $C{ij} = \sum{k=1}^{n} A{ik} B{kj}$에 $n$번의 곱셈이 들고, 원소가 $n^2$개이므로 총 $\Theta(n^3)$번의 스칼라 곱셈이 필요하다.
- Uniform-Cost Search너비 우선 탐색는 얕은 깊이의 노드부터 차례대로 확장한다.
- 몬테카를로 방법몬테카를로 방법의 씨앗은 18세기로 거슬러 올라간다.
- 배열배열의 핵심은 연속적인 메모리 배치에 있다.
- 연결 리스트연결 리스트의 각 원소를 노드(node)라 부른다.
- 자료구조의 개념PDT(Primitive Data Type)는 프로그래밍 언어 수준에서 데이터를 담기 위한 가장 기본적인 형태의 자료형을 말한다.