Basic/알고리즘

최단 경로 알고리즘가장 짧은 경로를 찾는 알고리즘 보통 '길 찾기'에 많이 사용하는 알고리즘 이다.최단 경로 알고리즘의 경우 보통 그래프로 표현하는데 각 지점은 그래프에서 노드로 표현되고, 지점 간 연결된 도로는 그래프에서 간선으로 표현된다.주로 많이 사용 되는 최단 경로 알고리즘에는 밑에 3개가 있다.다익스트라 최단 경로 알고리즘플로이드 워셜벨만 포드 다익스트라 최단 경로 알고리즘그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 중요한 점은 음의 간선이 없을 때 정상적으로 동작한다.음의 간선 : 0보다 작은 값을 가지는 간선현실 세계에서의 길은 음의 간선으로 표현되지 않기 때문에 다익스트라 알고리즘은 실제로 GPS 소프트웨어의 기본 ..

DFS(깊이 우선 탐색)그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘.동작 방식DFS는 재귀함수 또는 스택을 이용해 구현이 가능하다. 구체적인 동작 과정은 다음과 같다.탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 최상단 노드를 꺼낸다.2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.그림을 통해 과정을 보자면, 시작 노드인 '1'을 방문 처리를 한다.최상단 노드('1')에 방문하지 않은 인접 노드들 중 작은 노드인 '2'를 방문 처리 한다.현재 노드('2')에 방문하지 않은 인접 노드들 중 작은 노드인 '3'을 방문 처리를 한다.현재 노드('3')에 방문하지 않은 인접한..

순차 탐색 이진 탐색에 대한 공부전에 순차 탐색에 대해 이해할 필요가 있다. 순차 탐색 은 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩  차례대로 확인하는 방법이다. 보통의 경우 정렬되지 않은 데이터를 찾아야 할 때 사용하며 시간이 충분할 경우 항상 원하는 데이터를 찾을 수 있다.이진 탐색  배열 내부의 데이터가 정렬되어 있어야만 사용 가능하고 탐색 범위를 절반씩 좁혀가며 데이터를 탐색한다. 위치를 나타내는 변수 3개를 사용하는데 탐색하고자 하는 범위의 시작점, 끝점, 중간점이다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하여 원하는 데이터를 찾는 것이 이진 탐색의 과정이다.그림을 통해서 자세하게 알아보도록 하자. 우리는 회색으로 칠해진 '2'라는 데이터를 ..

퀵 정렬퀵 정렬은 앞서 배웠던 선택 정렬, 삽입 정렬과 같은 정렬 알고리즘들 중에서 가장 많이 사용되는 알고리즘이다.기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작이 이루어진다. 이 퀵 정렬엔 피벗(Pivot)이 사용된다. 이 피벗이라는 것은 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'에 해당하는 것이다. 퀵 정렬을 수행하는 데 있어서 피벗을 어떻게 설정할 것인지 미리 명시를 해야 한다. 피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러 가지 방식으로 퀵 정렬을 구분하는데, 여기서는 호어 분할 방식을 기준으로 퀵 정렬을 설명 한다. 호어 분할 방식먼저 다음 규칙으로 피벗을 설정한다. - 리스트에서 첫 번째 데이터를 피벗으로 정한다. 그 뒤에 왼쪽에..