내비게이션 앱으로 목적지까지의 경로를 검색한다고 하자.
#algorithm
14개 글
그래프 탐색 알고리즘은 어떤 노드를 먼저 확장할지 결정해야 한다.
BFS의 동작 원리는 단순하다.
Computational Thinking을 한마디로 정의하자면 컴퓨터 입장에서 생각하기다.
DFS는 미로를 탐험하는 것에 비유할 수 있다.
힙 정렬은 우선순위 큐에서 원소를 하나씩 꺼내면 자동으로 정렬된다는 관찰에서 출발한다.
두 개의 $n$자리 정수 $x$와 $y$를 곱한다고 하자.
병합 정렬의 시간 복잡도를 구한다고 하자.
출발지에서 목적지로 향하는 최적의 경로를 찾는 일반적인 탐색 문제에서는 에이전트 혼자 목표를 향해 나아가지만, 게임에서는 나의 이익을 최소화하려는 상대방이 존재한다.
어떤 게임을 수행하는 컴퓨터 유저를 설계할 때, 기존의 핵심 알고리즘은 미니맥스 알고리즘이었다.
$n \times n$ 행렬 $A$와 $B$의 곱 $C = AB$를 정의대로 계산하면 각 $C{ij} = \sum{k=1}^{n} A{ik} B{kj}$에 $n$번의 곱셈이 들고, 원소가 $n^2$개이므로 총 $\Theta(n^3)$번의 스칼라 곱셈이 필요하다.
너비 우선 탐색는 얕은 깊이의 노드부터 차례대로 확장한다.
몬테카를로 방법의 씨앗은 18세기로 거슬러 올라간다.
+ Computational Thinking + 자료구조의 개념 + 재귀 (예정) + 마스터 정리 + 분할 정복 (예정) + 그리디 알고리즘 (예정) + 비트마스크 (예정) + 배열 + 문자열 (예정) + 연결 리스트 + Stack + Queue + Heap + Priority Queue + 트리 (예정) + 그래프 (예정) + 연결 요소 (예정) + 해싱 (예정) + Breadth-First Search + Depth-First Search + A + Uniform-Cost Search + Best-First Search + 이진 탐색 (예정) + 깊이 제한 탐색 (예정) + 반복 깊이 탐색 (예정) + 양방향 탐색 (예정) + 언덕 오르기 탐색 (예정) + 지역 빔 탐색 (예정) - Strassen Algorithm - Karatsuba Multiplication + 힙 정렬 + 합병 정렬 (예정) + 퀵 정렬 (예정) + 벨만-포드 알고리즘 (예정) + KMP 알고리즘 (예정) + 크루스칼 알고리즘 (예정) + Minimax Algorithm + Monte Carlo Tree Search + 몬테카를로 방법 + 유전 알고리즘 (예정) + 명제 논리 (예정) + 1차 논리 (예정) + DPLL (예정) + WalkSAT (예정) + 전방 연쇄 (예정) + 후방 연쇄 (예정) 추후 업데이트됩니다.