최단경로 - 다익스트라 알고리즘
** 정의 출발 지점이 고정되어있을 때, 인접 노드들을 방문하며 최단 경로 들을 계산해나가는 방법 ** 예시 1. 출발지를 s로 정하고, 다음과 같이 표시한다. (s, t, x, y, z 순) 거리 = [0, inf, inf, inf, inf] 방문 = [True, False, False, False, False] 2. 갈 수 있는 노드들의 최소거리를 측정한다. s->t: 10 s->y: 5 (s, t, x, y, z 순) 거리 = [0, 10, inf, 5, inf] 방문 = [True, False, False, False, False] 3. 방문 안한 녀석들 중 가장 가까운 녀석인 y를 방문하고, 최소거리를 측정한다. y->t: 3 y->x: 9 y->z: 2 (s, t, x, y, z 순) 거리 =..
선택 정렬
**정의 오름차순 정렬 예시 전체를 둘러보고, 가장 크기가 작은 것을 맨 앞과 위치를 바꾼다, 다시 전체를 둘러보고, 다시 제일 작은 것을 2번째에 위치시킨다. 위의 과정을 반복한다. ** 예시 [4, 6, 2, 9, 1] # 정렬되지 않은 배열 1단계 : [4, 6, 2, 9, 1] 4와 6과 2와 9와 1을 차례차례 비교합니다. 그 중 가장 작은 1과 맨 앞 자리인 4를 교체합니다! [**1**, 6, 2, 9, **4**] 이렇게요! 자, 그러면 이제 가장 작은 숫자인 1이 맨 앞으로 왔습니다. 가장 작은 걸 가장 맨 앞으로 옮기기로 했으니까요! 그러면, 맨 앞자리를 제외하고 다시 한 번 반복하면 됩니다. 2단계 : [1, 6, 2, 9, 4] 6과 2와 9와 4를 차례차례 비교합니다. 그 중 가장..
버블 정렬
** 정의 1번째와 2번쨰, 2번쨰와 3번째......... 마지막 -1 번쨰와 마지막번째를 비교하는 정렬 방식입니다. ** 예시 [4, 6, 2, 9, 1] # 정렬되지 않은 배열 1단계 : [**4, 6**, 2, 9, 1] 4와 6을 비교합니다! 4 2 이므로 둘을 변경합니다! [4, **2, 6**, 9, 1] 이렇게요! 3단계 : [4, 2, 6, 9, 1] 6과 9를 비교합니다! 6 1 이므로 둘을 변경합니다! [4, 2, 6, **1, 9]** 이렇게요! 자, 그러면 이제 한 바퀴를 돌렸죠?..
합병 정렬
** 개요 ** 설명 크게 작은 단위로 나누어서, 위로 올라오며 합치는 방식이라고 생각하시면 됩니다. 예시 ) [1, 2, 3, 5] # 정렬된 배열 A [4, 6, 7, 8] # 정렬된 배열 B [] # 두 집합을 합칠 빈 배열 C ↓ 1단계 : [**1**, 2, 3, 5] ↓ [**4**, 6, 7, 8] 1과 4를 비교합니다! 1 < 4 이므로 1을 C 에 넣습니다. C:[1] ↓ 2단계 : [1, **2**, 3, 5] ↓ [**4**, 6, 7, 8] 2와 4를 비교합니다! 2 < 4 이므로 2를 C 에 넣습니다. C:[1, 2] ↓ 3단계 : [1, 2, **3**, 5] ↓ [**4**, 6, 7, 8] 3과 4를 비교합니다! 3 < 4 이므로 3을 C 에 넣습니다. C:[1, 2, 3] ..
