Minwoo Dev.

퀵 정렬(Quick Sort)퀵 정렬은 평균적으로 가장 빠른 정렬 방법으로 알려져있다.분할 정복(Divide and Conquer) 방법을 사용하는 정렬이다. 퀵 정렬은 피봇(pivot)이라는 값을 기준으로 리스트를 나누어 정렬한다.피봇의 설정은 여러가지 방법이 있는데, 우리는 첫번째 값을 피봇으로 설정하는 비교적 간단한 방법을 사용하겠다. 연산 방법은 쉽게 말하자면피봇을 기준으로 왼쪽으로 이동하며 피봇보다 작은 값을 찾고 low에 저장한다, 오른쪽으로 이동하며 피봇보다 큰 값을 찾아 high에 저장한다.그리고 그 두 값의 위치를 바꾼다.반복한다.그리고 high가 low보다 앞에 있다면 종료한다. pivot과 high의 위치를 바꾼다. 글로는 설명이 어려울 거 같아 사진을 참조했다.개념이 이해가 어렵다면..

삽입 정렬(Insertion Sort)삽입 정렬은 1차원 배열 상에서 정렬된 부분과 정렬되지 않은 부분으로 나누어 정렬을 수행하는 방법이다.오름차순으로 정렬한다면, 위와 같은 오름차순으로 정렬된 리스트와 정렬되지 않은 리스트로 나누고정렬되지 않는 리스트에서 첫번째 원소를 정렬된 리스트의 각 값과 비교하여 알맞는 위치에 끼워넣는 방식이다.   위 방식을 구현하기 위해서는 정렬된 리스트와 정렬되지 않는 리스트의 인덱스값이 각각 필요하다.0부터 정렬된 리스트의 인덱스까지, 그리고 정렬되지 않은 리스트의 인덱스 부터 배열의 끝까지로 나누기 위함이다. 위 사항들을 고려해서 코드를 작성해보았다. 삽입 정렬  #include // 삽입 정렬 함수void insertionSort(int arr[], int n) { ..

Dijkstra 알고리즘 Dijkstra 알고리즘은 가중치 그래프에서, 한 정점에서 다른 정점으로 바로 가는 것보다 다른 정점을 거쳐서 가는 가중치 값이 더 효율적인 경우에 그 경로를 최단경로로 정하는 알고리즘이다.  식으로 표현하면 위와 같다.정점 v에서 정점 u까지 가는 최단 경로를 찾는 과정에서, v에서 u로 가는 기존에 알고있던 가중치값보다 어떤 k라는 정점을 거쳐서 가는 가중치가 작은 경우, 그 가중치값이 distance[u], 즉 v에서 u로 가는 최단거리로 업데이트되는 것이다. 예시 그래프로 자세히 보자.  위 그래프에서 시작 정점을 0이라고 해두고 시작하자.0에서 갈 수 있는 정점은 1, 2, 3이다. 이 세 정점에 대하여 간선의 가중치 값을 기록한다.그려둔 가중치 값 중 가장 작은 값을 ..