Dev/Algorithm
Merge Sort (병합정렬)
Merge Sort (병합정렬) 병합정렬은 대표적인 분할 정복 알고리즘(Divide and conquer algorithm)입니다. 정렬되지 않은 리스트를 하나의 원소만 포함하는 n개의 리스트로 분할한 후 부분 리스트가 하나만 남을 때까지 반복해서 병합하여 정렬합니다. N개의 크기의 배열을 logN의 단계로 정렬을 수행해 NlogN의 시간복잡도를 가집니다. Merge Sort 정렬 과정 초기상태: [3 5 6 1 2 4 0 7] 하나의 큰 리스트를 하나의 원소만 포함하는 8개의 리스트로 분할합니다.[3 5 6 1] [2 4 0 7][3] [5] [6] [1] [2] [4] [0] [7] [3 5] [6 1] [2 4] [0 7] [3 5 6 1 2 4 0 7] 하나의 리스트가 남을때까지 병합하면서 정렬합..
다익스트라(Dijkstra) 알고리즘
다익스트라(Dijkstra) 알고리즘 다익스트라(Dijkstra) 알고리즘은 한 정점에서 다른 모든 정점으로 가는 최단경로를 구하는 알고리즘입니다. 다익스트라 알고리즘은 첫 정점을 기준으로 연결되어 있는 정점을 추가해가면서 최단거리를 갱신하는 DP(Dynamic Programming)문제입니다. 정점을 잇기 전까지는 시작점을 제외한 모든 정점은 무한대입니다. 다익스트라 알고리즘 동작 출발 정점을 선택합니다. 출발 정점에 연결되어있는 각 정점의 최단거리를 갱신합니다. 방문하지 않은 정점 중 가장 거리가 짧은 정점을 선택합니다. 선택한 정점에 연결되어 있는 각 정점의 최단거리를 갱신합니다. 3~4번을 반복합니다. 예시 n = 노드갯수 k = 시작노드 [소스노드, 타겟노드, 거리] [ [1,2,6], [1,3..
Heap Sort (힙정렬)
Heap Sort (힙정렬) 힙 정렬은 비교기반 정렬 알고리즘으로 선택정렬의 향상된 버전으로 볼 수 있습니다. 선택정렬과 유사하게 정렬된 영역과 정렬되지 않은 영역으로 나누고 정렬되지 않은 영역의 가장 큰 요소를 추출한 후 정렬된 영역에 삽입합니다. 선택정렬과 다른 점은 힙 정렬은 정렬되지 않은 영역의 선형탐색에 시간을 낭비하지 않습니다. 잘 구현된 퀵 정렬보다는 실행속도가 다소 느리며 O(nlogn)의 시간복잡도를 가집니다. Heap Sort 정렬과정 정렬해야 할 요소들로 최대 힙 트리 를 구성합니다. (내림차순으로 정렬은 최소 힙 트리) 최대 힙: 완전 트리이면서 모든 노드가 자식들보다 큰 트리 최소 힙: 완전 트리이면서 모든 노드가 자식들보다 작은 트리 가장 큰 수(루트에 위치)를 힙에서 꺼내 배열..
Insertion Sort (삽입정렬)
Insertion Sort (삽입정렬) 삽입정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬하는 알고리즘입니다. O(n^2)의 시간복잡도를 가지지만 선택정렬, 버블정렬 알고리즘에 비해 빠릅니다. 삽입을 할 때 데이터를 하나씩 밀어야 하기 때문에 배열이 길어질수록 효율이 떨어집니다. Insertion Sort 정렬과정 초기상태: (5 3 4 2 1 7 6) (5 3 4 2 1 7 6) (5 3 4 2 1 7 6) (3 5 4 2 1 7 6) (3 4 5 2 1 7 6) (2 3 4 5 1 7 6) (1 2 3 4 5 7 6) (1 2 3 4 5 7 6) (1 2 3 4 5 6 7) Insertion Sort 코드 (Python) de..
Selection Sort (선택정렬)
Selection Sort (선택정렬) 선택정렬은 정렬되지 않은 부분에서 가장 최소의 값을 찾아 시작부분에 배치하여 정렬하는 알고리즘입니다. O(n^2)의 시간복잡도를 가지며 알고리즘이 단순하여 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있습니다. Selection Sort 정렬과정 주어진 배열에 최소 값을 찾습니다. 그 값을 맨 처음에 위치한 값과 교체합니다. 맨 처음 위치를 제외한 나머지 배열을 같은 방법으로 정렬합니다. 초기상태: (5 3 4 2 1 7 6) Array 최솟값 (5 3 4 2 1 7 6) 1 (1 3 4 2 5 7 6) 2 (1 2 4 3 5 7 6) 3 (1 2 3 4 5 7 6) 4 (1 2 3 4 5 7 6) 5 (1 2 3 4 5 7 6) 6 (1 2 3 4 5 6 7..
Bubble Sort (버블정렬)
Bubble Sort (버블정렬) 버블소트는 인접한 요소들을 비교하여 정렬하는 알고리즘입니다. 인접한 두개의 요소들을 비교하여 크기가 순서대로 되어있지 않으면 서로 변경합니다. O(n^2)의 시간복잡도를 가지지만 코드가 단순하여 자주 사용됩니다. Bubble Sort 정렬과정 초기상태: (5 3 4 2 1) 1회전(3 5 4 2 1) -> (3 4 5 2 1) : 5 > 4, 교환(3 4 2 5 1) -> (3 4 2 1 5) : 5 > 1, 교환 결과: (3 4 2 1 5) (3 4 5 2 1) -> (3 4 2 5 1) : 5 > 2, 교환 (5 3 4 2 1) -> (3 5 4 2 1) : 5 > 3, 교환 2회전(3 4 2 1 5) -> (3 2 4 1 5) : 4 > 2, 교환결과: (3 2 1..