알고리즘

그래프 탐색 알고리즘의 대표격이라 할 수 있는 DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색)에 대해 알아보자.

Breadth First Search, 너비 우선 탐색이란 말 그대로 너비를 우선시하여 그래프를 탐색하는 방법이다.

두 문자열 A와 B가 주어졌을 때, A에 연산을 최소 횟수로 수행해 B로 만드는 문제를 "최소 편집" 문제라고 한다.

다익스트라 알고리즘은 그래프의 최단 경로를 탐색하는 대표적인 알고리즘이다.

우선순위 큐, heapq를 이용해서 좀 더 시간적으로 효율적으로 다익스트라 알고리즘을 구현한다.

다익스트라 알고리즘이 한 정점에서 다른 모든 정점까지의 최단거리 였다면, 플로이드 와샬 알고리즘은 임의의 정점에서 임의의 정점까지의 최단거리 를 다루는 알고리즘이다.

외판원 순회 문제 (Traveling Salesman Problem)는 조합 최적화 문제의 일종이다.

LCS (Longest Common Subsequence) 알고리즘은 두 문자열 내에 존재하는 최장 공통 부분 수열을 찾는 알고리즘을 말한다.