컴공생의 다이어리

다익스트라(Dijkstra) 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘 특정한 노드에서 출발해 연결되어 있는 다른 모든 노드로 가는 최단 경로를 구하기 위한 알고리즘 0보다 작은 값을 가지는 음의 간선이 없어야 정상적으로 동작 보통 우선 순위 큐를 구현하기 위해 사용되는 heapq 라이브러리를 활용해서 구현 GPS 소프트웨어의 기본 알고리즘으로 채택 과정 출발 노드를 설정 출발 노드를 기준으로 각 노드의 최소 비용을 저장 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신 위의 3번 ~ 4번 과정을 반복 동작 단계에 대한 예시는 아래 게시물이 잘 정리되어 있으니 참고하면 좋을 것 같다! [알고리즘] 다익스트..

선형 탐색(Linear Search) 선형 탐색은 일렬로 된 자료를 왼쪽부터 오른쪽으로 차례대로 탐색하는 알고리즘이다. 순차 탐색(Sequential Search)이라고도 한다. 파이썬 코드 def linear_search(arr, search): # for문 사용 for i in range(len(arr)): if arr[i] == search: return True return False linear_search([3, 110, 8, 13, 2], 5) # False 반환 linear_search([3, 110, 8, 13, 2], 13) # True 반환 혹은 def linear_search(arr, search): # while문 사용 i = 0 while i < len(arr): if arr[i..

이진 탐색(Binary Search) 이진 탐색은 정렬된 리스트에 적용할 수 있는 간단한 고속 탐색 기법이며 이분 탐색이라고도 불린다. 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 사람들이 숫자를 맞춰가는 업다운 게임과 같은 방식이다. 참고 : 업다운 게임 - 무한도전 니가 가라 하와이편 탐색 과정 이진 탐색은 데이터가 정렬되어있는 상태에서 진행된다. 시작점과 끝점 사이에 중간점을 정함 (만일, 중간점이 실수라면 소수점 이하를 버림) 중간점에 해당하는 값과 찾고자 하는 값을 비교 찾고자 하는 값이 중간점에 해당하는 값보다 작다면 중간점을 기준으로 왼쪽 부분을, 찾고자 하는 값이 중간점에 해당하는 값보다 크다면 중간점을 기준으로 오른쪽 부분에 해당하는 데이터 범위를 가..

병합 정렬(Merge Sort) 병합 정렬은 분할 정복 알고리즘의 하나로 합병 정렬이라고도 한다. 불안정 정렬인 퀵 정렬과 달리, 병합 정렬은 안정 정렬에 속한다. 전체 데이터를 가장 작은 단위로 분할한 후 분할한 데이터를 다시 병합하면서 정렬하는 재귀용법을 활용한 정렬 알고리즘이다. 퀵 정렬과 비교했을 때, 차이점은 아래와 같다. 퀵 정렬 - 각 요소를 피벗과 비교하여 요소를 정렬 - 피벗을 통해 정렬(partition) → 영역을 쪼갬(quick sort) 병합 정렬 - 배열을 하나의 요소가 남을 때까지 두 개의 하위 배열 (n / 2)로 반복하여 나눔 - 영역을 쪼갤 수 있을 만큼 쪼갬(merge sort) → 정렬(merge) 정렬 과정 분할(Divide) 단계 리스트를 절반으로 나누어 비슷한 크..

퀵 정렬(Quick Sort) 퀵 정렬은 분할 정복 알고리즘의 하나로 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 알고리즘이다. 합병 정렬(Merge Sort)과 달리 퀵 정렬은 리스트를 비균등하게 분할한다. 퀵 정렬은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교정렬에 속한다. 하나의 리스트를 피벗(pivot)을 기준으로 피벗보다 작은 데이터와 큰 데이터를 두 개의 부분 리스트로 나눈 다음, 각 부분 리스트에 대해 다시 재귀적으로 수행하여 정렬하는 방법이다. 정렬 과정 배열 가운데서 하나의 원소를 선택(→ 이 원소가 피벗) 피벗을 기준으로 피벗보다 작은 원소들은 피벗 앞(왼쪽)으로 오고, 피벗보다 큰 원소들은 피벗 뒤(오른쪽)로 이동 피벗을 제외하고 나뉘게 된 두 배열은 앞 ..