Per ardua ad astra.

그래프의 활용 네트워크의 데이터 흐름이나 스케줄링, 논리회로 설계, 정렬, 탐색, 인공지능의 지식 정보 생성 과정 등 그리고 실생활에서 많이 접할 수 있는 도로망 설계나 버스 및 지하철 노선 설계 등과 같이 어떤 문제를 해결하기 위한 모델링 과정에서 그래프 이론은 매우 중요하게 쓰인다. 이러한 모델링에서 최단 경로를 구하거나 정보 탐색을 하는 방법이 많이 쓰인다. 최단 경로 문제(Shortest Path Problem) $|E| > 0$ 인 연결 그래프 $G = (V, \; E)$ 에서 정점 $v_{1}, v_{2} \in V$ 간의 가장 짧은 거리의 경로를 찾는 문제 지도의 어떤 지역 A에서 다른 지역 B로 이동하는 경로나, 네트워크의 어떤 호스트 A에서 다른 호스트 B로 이동하는 경로는 다양할 수 있..

백트래킹(Backtracking) 개념 모든 경우의 수를 고려하는 알고리즘 상태 공간을 트리(Tree)로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘(Tree Search Algorithm)이라고 봐도 된다. 방식에 따른 분류 깊이 우선 탐색(Depth First Search, DFS) 너비 우선 탐색(Breadth First Search, BFS) 최선 우선 탐색(Best First Search / Heuristic Search) 경우의 수 구하기는 일반적으로 DFS가 편리하며, 대다수의 문제들은 DFS를 써도 일단 답은 나온다. 하지만, 트리의 깊이(Depth)가 무한대가 될 경우에는 DFS를 사용하면 안된다. 예) 미로 찾기에서 루프(회로)가 발생하는 경우, DFS는 이 가지를 ..

브루트 포스(Brute Force) 개념 브루트(Brute)와 포스(Force)가 결합되어 만들어진 단어이며, "난폭한 힘(폭력)" 이라는 뜻이다. 문제 해결을 위해 오래 걸리고 자원이 많이 들어서 무식하다고 생각될 수도 있지만, 항상 100%의 정확성을 보인다. 정답(Solution)이 발견될 때까지 가능한 모든 선택지를 찾는 방법이다. 예) 4자리 숫자의 패스워드를 찾기 위해 0000부터 9999까지 하나씩 입력하여 찾아보는 경우 따라서 브루트 포스 알고리즘은 완전 탐색 알고리즘이라고 할 수 있다. 간단하고 일관적이지만, 매우 느리다는 단점이 있다. 거의 완벽하게 병렬 작업이 가능하여 병렬 프로그래밍에서 사용된다. 패턴 매칭(Pattern Matching) 등의 작업에 사용될 수 있다. 너비 우선 탐..