aeightchill

다익스트라 알고리즘하나의 시작점에서 다른 모든 노드까지 가장 짧은 거리(최단 경로)를 찾는 알고리즘여러 도시(노드)가 도로(간선)로 연결되어 있을 때, 특정 도시에서 다른 도시로 가장 빠르게 가는 방법을 찾을 수 있다. 특징음(-)의 간선이 없을 때 정상적으로 동작한다.각 노드까지의 현재까지 확인된 최단 거리를 1차원 리스트에 저장하고, 계속 갱신하면서 더 짧은 경로를 찾는다.* DP의 일종이라고 할 수 있는데 작은 문제의 해(특정 노드까지의 최단 거리 구하기)를 이용해 큰 문제를 푸는 방식을 따르기 때문 작동 방식출발 노드를 설정한다.최단 거리 리스트를 초기화한다.시작점은 거리 0, 나머지는 무한대로 설정한다.방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.해당 노드를 거쳐 다른..

이진 탐색검색 간격을 반으로 반복적으로 나누어 정렬된 배열로 사용하는 알고리즘대상 요소와 검색 공간의 중간 값을 비교하여 검색 간격을 절반으로 줄임.  ✍🏻  동작 예시index0123456789 -5-2012456710Low   Middle    High-5-2012456710     Low Middle High-5-2012456710        LowMiddleHigh   이진 검색 알고리즘 적용 조건데이터 구조를 정렬데이터 구조의 모든 요소에 액세스하려면 일정 시간 소요   작동 방식배열의 중간 요소를 Key와 비교한다. (Key는 찾고자 하는 요소)키를 찾으면 프로세스 종료키를 찾지 못한 경우 다음 공간으로 탐색할 배열의 절반을 선택한다.키가 중간 요소보다 작으면  →   중간을 기준으로 왼쪽..

깊이 우선 탐색 (Depth-First Search, DFS)루트 노드 혹은 임의 노드에서 다음 브랜치로 넘어가기 전에 해당 브랜치를 모두 탐색하는 방법 (스택 or 재귀함수를 통해 구현) 가능한 한 깊이 내려가면서 탐색을 진행한다.특정 경로를 찾거나, 그래프의 모든 노드를 방문하는 데 유용하다. def dfs(graph, v, visited): visited[v] = True for i in graph[v]: if not visited[i]: dfs(graph, i, visited)visited = [False] * ndfs(graph, 1, visited)      너비 우선 탐색 (Breadth-First Search, BFS)루트 노드 또는 임의 노드에서 인접한 노드부터 먼저 탐색하는 방법 ..

계수 정렬 (Counting Sort)계수 정렬은 비교하지 않는 정렬 알고리즘으로 데이터의 개수를 세서 정렬하는 방식. 정렬하려는 데이터의 범위를 인덱스로 갖는 빈 배열을 생성한다.데이터 범위가 0 ~ 99까지라면 크기가 100인 빈 배열을 생성한다.정렬하려는 배열을 순회하면서 데이터에 해당하는 인덱스의 값을 1씩 증가한다. 제약 조건데이터의 범위가 0 또는 양의 정수여야 한다. 예시배열 [8, 3, 9, 2, 3, 4, 0, 5]를 계수 정렬하는 과정. 정렬하려는 배열 : 83923405계수 배열 :1012110011인덱스 ↑0123456789최종 배열 : 02334589 시간 복잡도  :  O(n + k)   * 데이터의 개수 : n , 데이터의 최댓값 : k  (데이터의 최댓값이 무한대에 수렴하면 ..

기수 정렬 (Radix Sort)기수 정렬은 비교하지 않는 정렬 알고리즘으로 낮은 자릿수부터 정렬을 수행. 숫자별로 버킷(bucket)이라는 queue를 생성정렬하려는 숫자들의 각 자릿수에 해당하는 숫자를 각각의 버킷에 넣어 정렬이를 자릿수만큼 반복한다.   단점버킷을 구성하기 위한 추가 메모리가 필요정렬할 수 있는 데이터 타입이 한정적 예시숫자 배열 [73, 21, 56, 13, 16, 35, 41, 69]를 기수 정렬을 이용해 오름차순으로 정렬하는 과정7321561316354169버킷          0123456789 버킷 4121 1373 351656  690123456789  2141731335561669버킷 1613213541566973  0123456789  1316213541566973 시..

병합 정렬 (Merge Sort)병합 정렬은 재귀를 이용하는 분할 정복 알고리즘. 분할  →   배열을 쪼개는 것.정복  →   분할한 배열을 정렬하면서 하나로 합병하는 것.   작동 방식정렬하려는 배열을 크기가 0 또는 1이 될 때까지 절반씩 분할.분할된 배열은 다시 하나의 배열로 합쳐지면서 정렬.예시배열 [8, 3, 2, 1, 7, 6, 4, 5]가 있을 때 다음과 같은 과정으로 정렬한다. (오름차순)분할8 3 2 1 7 6 4 58 3 2 1  |  7 6 4 58 3  |  2 1  |  7 6  |  4 58  |  3  |  2  |  1  |  7  |  6  |  4  |  5정렬6 7  |  4 5  |  _ _ _ _6 7  |  _ 5  |  4 _ _ _6 7  |  _ _  |  ..

퀵 정렬 (Quick Sort)퀵 정렬은 피봇보다 작은 값으로 구성된 배열과 피봇보다 큰 값으로 구성된 배열로 분할해 정렬하는 알고리즘.   작동 방식변수 : low low배열의 첫 번째 요소에서 시작피봇보다 작으면 오른쪽으로 한 칸 이동피봇보다 크면 이동 Xhigh배열의 마지막 요소에서 시작피봇보다 크면 왼쪽으로 한 칸 이동피봇보다 작으면 이동 Xlow와 high 둘 다 이동하지 않을 때 두 변수가 가리키는 값을 교환예시배열 [4, 3, 2, 6, 7, 1, 5]가 있을 때 다음과 같은 과정으로 분할한다.분할은 배열의 크기가 1이하가 될 때까지 반복해서 수행한다.1.4326715 pivotlow    high2.4326715 pivotlow    high3.4326715 pivot low  high(이..

삽입 정렬 (Insertion Sort)삽입 정렬은 배열을 앞에서부터 순회하면서 정렬된 부분의 적절한 위치에 값을 삽입하는 방식으로 정렬하는 알고리즘.   작동 방식인덱스 i에 있는 a를 정렬할 차례일 때, 인덱스 0부터 i-1까지는 이미 정렬된 상태배열의 정렬된 부분에서 a보다 작거나 같은 수와 a보다 큰 수 사이에 a를 삽입한다.예시배열 [5, 3, 8, 1, 2]가 있을 때 다음과 같은 과정으로 정렬된다.5 3 8 1 23 5 8 1 23 5 8 1 21 3 5 8 21 2 3 5 8시간 복잡도 : O(n^2)    * 1 + 2 + ... + (n-2) + (n-1) = n(n-1) / 2   def insertion_sort(arr): n = len(arr) for i in range..

선택 정렬 (Selection Sort)선택 정렬은 배열을 순회하면서 배열의 앞에서부터 차례대로 각 인덱스에 들어갈 값을 선택해 위치시키며 정렬하는 알고리즘   작동 방식인덱스 i에 들어갈 값은 인덱스 i부터 N(마지막 인덱스)까지 중 최소값이 된다.예시배열 [5, 3, 8, 1, 2]가 있을 때 다음과 같은 과정으로 정렬된다.5 3 8 1 21 3 8 5 21 2 8 5 31 2 3 5 81 2 3 5 8시간 복잡도 : O(n^2)        * (n-1) + (n-2) + ... + 2 + 1 = n(n-1) / 2   def selection_sort(arr): for i in range(len(arr)): min_idx = i for j in range(i+1, l..

버블 정렬 (Bubble Sort)버블 정렬은 선택 정렬과 유사한 알고리즘으로 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘. 버블 정렬하면 배열의 뒤에서부터 정렬된다.배열의 첫 번째 요소부터 n번째 요소까지 오름차순으로 버블 정렬을 수행하면 해당 범위의 최댓값이 n번째에 위치하게 된다.  배열의 n번째 요소를 정렬하는데 n-1번을 비교하므로 배열의 모든 요소를 정렬하려면 (n-1) + (n-2) + ... + 2 + 1 = n(n-1) / 2 만큼 연산을 수행한다. 시간 복잡도 : O(n^2)  def bubble_sort(arr): for i in range(len(arr)): for j in range(len(arr) - i - 1)..