Computer-Sience/Algorithm5 [Algorithm] 다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘 다익스트라 알고리즘은 1959년 네덜란드의 컴퓨터 과학자 에츠허르 다익스트라가 개발한 최단 경로 탐색 알고리즘이다. 이 알고리즘은 그래프에서 한 정점에서 다른 모든 정점까지의 최단 거리를 구하는 데 사용되며, 실 생활에 사용되는 예시로는 최단 거리 알고리즘답게 내비게이션 시스템, 네트워크 라우팅 등과 같은 곳에 사용된다. 위 예제는 1번 노드(a)에서 5번 노드(b)로 가는 최단 거리를 구하는 과정을 나타낸 것이다. 기준이 되는 노드에서 방문하지 않은 각 노드 간의 거리를 계산하고, 이를 통하여 가장 낮은 거리로 계산되는 각 노도의 경로를 모두 계산하게 되는 것이다. 예제 아래는 heapq를 활용하여, 위의 예제를 다익스트라 알고리즘을 코드로 구현한 것이다. import hea.. 2024. 11. 27. [Algorithm] 시간 복잡도 (Time Complexity) 1. 시간 복잡도 및 표기법 시간 복잡도는 특정 코드가 있을 때, 해당 코드에서 특정한 입력이 주어졌을 때, 얼마나 많은 연산을 하는지에 대한 개념을 나타낸 것이다. 알고리즘마다 특정 값에 대한 참조, 연산이 많을수록 당연히 복잡도가 다르고, 때에 따라서는 비효율적인 알고리즘이 될 수 있기에 우수한 성능을 낼 수 있는 알고리즘을 구현하기 위해서는 시간 복잡도를 정확하게 이해하고 알고리즘을 설계할 필요가 있다. 시간 복잡도를 표기하는 방법에는 아래의 3가지가 존재한다. 1) 빅 오(Big O) 표기법 빅 오(Big O) 표기법은 알고리즘의 실행 시간을 최악의 경우의 시간 복잡도로 나타내는 데 사용된다. 어떤 알고리즘의 시간 복잡도가 O(f(n))이라면, 해당 알고리즘의 실행 시간은 입력 크기 n이 증가함에.. 2023. 8. 19. [Algorithm] DFS / BFS 알고리즘 공부를 하다 보면 DFS와 BFS라는 단어를 자주 접하게 되는데, 이는 트리 구조(또는 그래프)의 탐색과 관련된 알고리즘이다. 1. 깊이 우선 탐색 : DFS (Depth-First Search) 깊이 우선 탐색은 미로를 탐색할 때 벽을 따라 한 방향으로 끝까지 간 후 더 갈 수 없을 때 분기점으로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법으로 볼 수 있다. 모든 노드의 방문을 확인하고자 할 때 해당 탐색 방식을 채택하며, 기본적으로 BFS 방식보다 조금 더 느릴 수 있다. (Back-Tracking 과정으로 분기점 방문을 위해 노드를 거슬러 올라가는 과정이 존재) * DFS 특징 : 재귀적으로 호출하는 순환 알고리즘의 형태이다. 전위 순회(Pre-Order Traversals)를 포함한.. 2023. 4. 19. [Algorithm] Sorting Algorithm(정렬 알고리즘) - Non Comparison 이전에 정렬 알고리즘에 대한 글을 작성했었는데 이는 상호 원소의 크기를 비교해가며 정렬을 하는 알고리즘이였다. [Algorithm] Sorting Algorithm(정렬 알고리즘) - Comparison 프로그래밍을 할 때 배열은 라이브러리를 통하여 손쉽게 정렬할 수 있다. 하지만 정렬은 다양하게 수행할 수 있고 그 알고리즘에 따라 장단점이 존재한다. 아래는 통상적으로 비교를 통한 정렬 ssnotebook.tistory.com 그리고 비교를 통한 정렬 알고리즘은 시간 복잡도가 최대 O(n log n)~O(n^2)를 가진다는 것을 알 수 있었다. 하지만 비교를 통한 정렬 알고리즘이 아닌 특수한 방식을 통한 정렬 알고리즘이 존재하는데, 이는 특정 조건을 충족하면 비교를 통한 알고리즘보다 빠르게 정렬을 할 수.. 2023. 2. 4. [Algorithm] Sorting Algorithm(정렬 알고리즘) - Comparison 프로그래밍을 할 때 배열은 라이브러리를 통하여 손쉽게 정렬할 수 있다. 하지만 정렬은 다양한 기법을 통해 수행할 수 있고 그 알고리즘에 따라 장단점이 존재한다. 아래는 통상적으로 원소의 크기를 비교하여 정렬을 할 때 사용하는 목록이다. 1. Bubble Sort(거품 정렬) : 배열에서 인접한 두 개의 원소를 비교하며 우열을 가린 뒤 서로 위치를 바꾸어 주는 방식이다. 거품 정렬을 통해 배열을 한 번 검사하면 필연적으로 가장 큰 수가 배열의 맨 끝으로 이동하게 되고 정렬이 완성될 때까지 반복한다. 두 개 원소의 위치만 계속 바꾸는 정렬이기 때문에 공간 복잡도는 O(1)을 가지지만, n개의 원소의 배열을 전부 정렬하는데 n번을 순회할 수 있기 때문에 시간 복잡도는 O(n^2)를 가진다. 2. Selecti.. 2023. 1. 3. 이전 1 다음
