자료구조 & 알고리즘

내비게이션 앱으로 목적지까지의 경로를 검색한다고 하자.

그래프 탐색 알고리즘은 어떤 노드를 먼저 확장할지 결정해야 한다.

BFS의 동작 원리는 단순하다.

Computational Thinking을 한마디로 정의하자면 컴퓨터 입장에서 생각하기다.

DFS는 미로를 탐험하는 것에 비유할 수 있다.

힙에는 두 가지 변형이 있다.

힙 정렬은 우선순위 큐에서 원소를 하나씩 꺼내면 자동으로 정렬된다는 관찰에서 출발한다.

두 개의 $n$자리 정수 $x$와 $y$를 곱한다고 하자.

병합 정렬의 시간 복잡도를 구한다고 하자.

출발지에서 목적지로 향하는 최적의 경로를 찾는 일반적인 탐색 문제에서는 에이전트 혼자 목표를 향해 나아가지만, 게임에서는 나의 이익을 최소화하려는 상대방이 존재한다.

어떤 게임을 수행하는 컴퓨터 유저를 설계할 때, 기존의 핵심 알고리즘은 미니맥스 알고리즘이었다.

우선순위 큐는 최소한 다음 세 가지 연산을 지원해야 한다.

큐의 가장 핵심적인 특징은 먼저 들어간 자료가 먼저 나온다는First-In-First-Out, FIFO 것이다.

모든 핵심 연산이 $O(1)$이라는 점이 스택의 강점이다.

$n \times n$ 행렬 $A$와 $B$의 곱 $C = AB$를 정의대로 계산하면 각 $C{ij} = \sum{k=1}^{n} A{ik} B{kj}$에 $n$번의 곱셈이 들고, 원소가 $n^2$개이므로 총 $\Theta(n^3)$번의 스칼라 곱셈이 필요하다.

너비 우선 탐색는 얕은 깊이의 노드부터 차례대로 확장한다.

몬테카를로 방법의 씨앗은 18세기로 거슬러 올라간다.

배열의 핵심은 연속적인 메모리 배치에 있다.

연결 리스트의 각 원소를 노드node라 부른다.

PDT(Primitive Data Type)는 프로그래밍 언어 수준에서 데이터를 담기 위한 가장 기본적인 형태의 자료형을 말한다.