이아손의 아르고호

1. 탄생배경 (정렬 알고리즘들의 탄생 배경은 사실 특별한 것이 별로 없다. 자료구조 같은 경우 처음 의도와 현재 상용되는 방식과 다른 경우가 가끔 있지만 정렬 알고리즘들은 말 그대로 "정렬"을 위해 생겨난 것들로 탄생배경에 대한 자세한 이해가 공부에 큰 영향을 주지는 않을 것 같다. 참고 정도만 해도 충분할 것이라 생각한다.) 퀵소트는 1961년 영국의 컴퓨터과학자 Tony Hoare에 의해 고안되었다. 당시 기계번역 프로젝트를 하고 있었는데 입력받은 러시아어 문장을 자동으로 번역하는 과정이었다. 당시 전산화(?)된 사전은 자기 테이프 (magnetic tape)에 알파벳순으로 저장된 형태였는데 효율적인 사전 검색을 위해 입력받은 문장의 단어들을 알파벳 순으로 정렬하는 과정이 필요했다. 일차적으로 개발..

1. 탄생 배경 이 알고리즘의 저자인 다익스트라는 1956년 암스테르담에서 ARMAC이라는 새로운 컴퓨터의 성능을 보여주기 위한 적절한 주제를 고민하고 있었다고 한다. 그러던 어느 날 오전에 쇼핑을 하던 중 지쳐서 카페에서 커피를 마시다가 최단 경로 탐색 법을 고민하게 되었고 이 알고리즘을 약 20분(...!) 만에 완성했다고 한다. 2. 이해하기: 다익스트라 알고리즘 2-1. 기본 로직 다익스트라 알고리즘은 하나의 시작점에서 다른 모든 점들까지의 최단 경로를 구한다. 어떠한 원리로 최단 경로를 찾아가는지 직관적으로 이해를 돕기 위해 아래의 예시처럼 가장 기초적인 그래프부터 살펴보겠다. 1) 첫 단계는 현재 노드를 기준으로 나머지 노드들까지의 거리를 계산을 하는 것이다. 인접해 있는 노드들은 해당 거리(..