🎯PS/Algorithm

[Algorithm/Python] 위상 정렬(Topology Sort)란?

들어가며본 포스팅에서는 위상 정렬에 대해 소개합니다.📌 위상 정렬이란?위상 정렬(Topology Sort)이란 방향 그래프의 모든 노드를 방향성을 모두 지키며 순서대로 나열하는 것을 의미합니다. 특정한 노드로 들어오는 간선의 개수를 진입차수라 합니다. 1️⃣ 진입차수가 0인 노드를 큐에 담습니다. 2️⃣ 큐가 비어있을 때까지 다음의 과정을 반복합니다. - 1 ) 큐에 담긴 노드를 꺼내어 해당 노드에서 출발하는 모든 간선을 그래프에서 제거합니다. - 2 ) 진입차수가 0인 노드를 큐에 담습니다. 모든 원소를 방문하지 않았는데 큐가 비었다는 것은 사이클이 발생했다는 것을 의미합니다. 큐에 담기는 노드가 2개 이상인 경우, 위상 정렬된 후의 결과가 여러 개일 수 있습니다. 1. 진입차수가 0인 노드 1을 큐에..

[Algorithm/Python] 크루스칼 알고리즘이란? || 최소 신장 트리

들어가며본 포스팅에서는 신장 트리에 대해 그리고 최소 신장 트리 알고리즘인 크루스칼 알고리즘에 대해 소개합니다. 📌 신장 트리란?신장 트리(Spanning Tree)란 하나의 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 말합니다.예를 들어 위와 같은 그래프가 존재한다고 할 때, 아래의 경우는 신장 트리인지를 확인해보겠습니다. 이 그래프는 노드 1을 포함하고 있지 않기 때문에 신장 트리에 해당하지 않습니다. 이 그래프는 모든 노드를 포함하고 있지만, 사이클이 존재하므로 신장 트리에 해당하지 않습니다. 이 그래프는 모든 노드를 포함하고 있으며, 사이클이 존재하지 않으므로 신장 트리에 해당합니다. 신장 트리의 노드 개수와 간선의 관계를 보면, 노드의 개수가 5개일 때, 간선..

[Algorithm/Python] 서로소 집합(Disjoint Sets) 알고리즘이란?

들어가며본 포스팅에서는 서로소 집합과 구현 방식에 대해 소개합니다.📌 서로소 집합이란?서로소 집합(Disjoint Sets)란 공통 원소가 없는 두 집합을 의미합니다. 예를 들어 {1, 2}와 {3, 4}는 서로소 관계이지만, {1, 2}와 {2, 3}은 서로소 관계가 아닙니다. 서로소 집합 자료구조는 union과 find라는 2개의 연산이 이루어집니다. union(합집합)이란, 하나의 집합으로 합치는 연산을 의미하며, find(찾기) 연산은 특정 원소가 어느 집합에 속하였는지를 찾아내는 연산입니다. 1️⃣ union(합집합) 연산을 통해, 서로 연결된 두 개의 노드를 확인합니다. - 1 ) 노드 A와 노드 B의 루트 노드인 A'와 B'를 찾습니다. - 2 ) 루트 노드 A'를 루트 노드 B'의 부모 노..

[Algorithm/Python] 플로이드 워셜 알고리즘이란?

들어가며 본 포스팅은 플로이드 워셜 알고리즘에 대해 소개합니다. 📌 플로이드 워셜 알고리즘 플로이드 워셜(Floyd-Warshall) 알고리즘이란, 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용하는 알고리즘입니다. 기존에 소개된 다익스트라 알고리즘에서의 최단 거리 테이블에서 거리가 가장 짧은 노드를 탐색해야 했던 과정을 생략할 수 있다는 점이 차이점입니다. 모든 노드가 다른 노드로 가는 최단 거리의 정보를 2차원 리스트에 담아 저장합니다. 노드의 개수 N만큼 점화식에 맞게 2차원 리스트를 갱신하므로 다이나믹 프로그래밍으로 볼 수 있습니다. ☑️ 시간 복잡도 모든 최단 경로를 2차원 리스트에 담아 처리하므로 매번 $O(N^2)$의 시간이 소요되며, 노드의 개수 N만큼 $O(N..

[Algorithm/Python] 다익스트라 최단 경로 알고리즘이란? || dijkstra

들어가며 본 포스팅에서는 다익스트라 최단 경로 알고리즘에 대해 소개합니다. 📌 다익스트라 최단 경로 알고리즘이란? 다익스트라 최단 경로 알고리즘이란, 가장 짧은 경로를 찾기 위한 알고리즘으로, 음의 간선(0보다 작은 값을 가진 간선)이 없을 때에 적용할 수 있는 알고리즘입니다. 1️⃣ 출발 노드를 설정합니다. 2️⃣ 최단 거리 테이블 초기화(무한으로 설정)합니다. 3️⃣ 방문하지 않은 노드 중에 최단 거리 테이블에서 최단 거리가 가장 짧은 노드를 선택합니다. 4️⃣ 선택한 노드를 거쳐 다른 노드로 가는 거리를 계산합니다. 5️⃣ 계산된 거리가 최단 거리 테이블의 거리보다 짧을 경우, 갱신합니다. 6️⃣ 위의 3️⃣4️⃣5️⃣를 반복합니다. 가장 최단 거리의 노드를 선택하여 주변 간선을 확인합니다. 더 짧..

[Algorithm/Python] 이진 탐색(Binary Search)란?

들어가며 본 포스팅에서는 순차 탐색(Sequential Search)과 이진 탐색(Binary Search)에 대해 소개합니다. 📌 순차 탐색이란? 순차 탐색(Sequential Search)이란, 특정 데이터를 찾기 위해 앞에서부터 차례대로 값을 비교해나가는 탐색 방식입니다. 1️⃣ 가장 첫 번째 데이터를, 찾고자하는 데이터(타겟)과 비교합니다. 2️⃣ 값이 서로 일치하지 않는다면, 다음 데이터로 이동하여 비교합니다. 3️⃣ 이를 반복하며 일치할 때, 탐색을 종료합니다. ✅[ CODE ] def sequential_search(n, target, arr): for i in range(n): if arr[i] == target: return i + 1 i + 1 번째의 데이터가 타겟과 동일하다는 결과를 ..

[Algorithm/Python] 계수 정렬(Count Sort)이란?? || Sort

📌 계수 정렬(Count Sort)계수 정렬이란, 리스트의 원소의 개수를 세어, 개수만큼 출력하여 정렬하는 방식이다. 예를 들어 arr = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] 를 정렬해본다고 하자면, 각 원소별로 몇 개가 존재하는지 수를 센 후, 인덱스 0을 시작으로 각 개수만큼 수를 출력해내어 정렬하는 방식이다.위의 그림처럼, 리스트의 데이터에 해당하는 인덱스의 값을 1씩 추가하여 해당 원소가 몇 개인지 수를 세어준다. 따라서, 인덱스 0부터 차례대로 세어진 수만큼 반복 출력해주면 정렬된 리스트를 확인해볼 수 있다. ✅[ CODE ]arr = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] def count(arr): ma..

[Algorithm/Python] 퀵 정렬(Quick Sort)이란? || Sort

📌 퀵 정렬(Quick Sort)퀵 정렬(Quick Sort)이란 기준 데이터인 피벗(pivot)을 정하고, 피벗보다 큰 데이터와 작은 데이터의 위치를 변경하는 정렬 방식이다. 피벗이 설정되어 리스트가 분할되는 방법에 따라 여러 퀵 정렬이 구분된다고 하는데, 호어 분할 방식에 따른 코드 구현을 진행해보았다. 호어 분할 방식에는 리스트에서 첫 번째 데이터를 피벗으로 설정한다는 규칙이 있다. 1️⃣ 리스트의 첫 번째 데이터를 피벗으로 설정한 후, 리스트의 왼쪽에서 오른쪽으로 이동하며 피벗보다 큰 데이터를 찾는다. 또한, 리스트의 오른쪽에서 왼쪽으로 이동하며 피벗보다 작은 데이터를 찾는다. 2️⃣ 큰 데이터와 작은 데이터의 위치를 서로 바꾼다. 3️⃣ 이와 같은 과정을 반복하되, 큰 데이터의 위치와 작은 데이..

[Algorithm/Python] 삽입 정렬(Insertion Sort)이란? || Sort

📌 삽입 정렬(Insertion Sort)삽입 정렬은 순차적으로 데이터를 확인하며, 적절한 위치에 삽입해주는 정렬 방식이다. 그림을 보면, 인덱스 1번째 수부터 시작하여 차례대로 각자 적절한 위치에 삽입해주는 것을 확인해볼 수 있다. 적절한 위치인 곳을 찾는 방법은, 빨간 박스로된 수를 기준으로 왼쪽으로 한 칸씩 이동하며 값을 비교한다. 빨간 박스의 수보다 작은 수를 만나게 되는 순간, 바로 그 위치에 삽입해주면 된다. ✅ [ CODE ]arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(1, len(arr)): idx = i for j in range(i, -1, -1): if arr[i] < arr[j]: idx = j val = arr[i] arr[idx +..

[Algorithm/Python] 선택 정렬(Selection Sort)이란? || Sort

📌 선택 정렬(Selection Sort)그림을 보면, 파란색으로 칠해진 수들 중 가장 작은 수를 골라, 빨간색으로 칠해진 수와 바뀌는 것을 확인해볼 수 있다. 이처럼, 선택 정렬은 가장 작은 수를 차례대로 선택하여 정렬하는 방식이다. ✅ CODEarr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(arr)): for j in range(i + 1, len(arr)): if arr[i] > arr[j]: temp = arr[i] arr[i] = arr[j] arr[j] = temp print(arr)매번, 작은 수가 나올 때마다 위치를 바꿔주어 주도록 구현을 해보았는데, 작은 수가 나올 때마다 바꿔주는 것이 조금 비효율 적인 것 같다는 생각이 들었다. ✅ C..