PS/알고리즘 이론

[파이썬으로 배우는 알고리즘] 선택 정렬(Selection Sort)

선택 정렬(Selection Sort)이란? 선택 정렬은 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 그 위치에 어떤 원소를 넣을지 "선택"하는 정렬 알고리즘입니다. 선택 정렬 과정 위와 같이 정렬되어 있지 않은 배열을 선택 정렬 알고리즘을 사용하여 정렬해보겠습니다. 제일 왼쪽 인덱스 0 즉, 제일 작은 원소가 들어갈 자리를 정하고, 해당 인덱스에 어떤 원소를 넣을지 다음 원소부터 순서대로 탐색합니다. 11, 2, 4, 3 원소 중에는 2가 제일 작으므로 2의 인덱스 2를 기억합니다. 인덱스 0에 저장된 원소 10과 인덱스 2에 저장된 2를 비교하여 2가 더 작은 것을 알 수 있습니다. 2가 더 작기 때문에 두 원소를 서로 바꿔줍니다. 1회전이 끝나고 인덱스 0의 원소를 구했습니다. 그다음으로 왼..

[파이썬으로 배우는 알고리즘] 버블 정렬(Bubble Sort)

버블 정렬(Bubble Sort)이란? 서로 인접한 두 원소를 비교하고, 순서가 맞지 않으면 교체하는 방식으로 정렬하는 정렬 알고리즘입니다. 원소가 마치 거품처럼 올라오는 듯해 버블 정렬이라는 이름이 붙었다고 합니다. 버블 정렬 과정 위와 같이 정렬되어 있지 않은 배열을 버블 정렬 알고리즘을 사용하여 정렬해보겠습니다. 먼저 배열의 맨 앞부터 인접한 원소를 비교합니다. 11은 10보다 크므로 대소 관계를 만족합니다. 따라서 교체하지 않습니다. 그다음으로 인접한 11과 2를 비교합니다. 2는 11보다 작으므로 대소 관계를 만족하지 않습니다. 따라서 위와 같이 두 원소의 자리를 교체합니다. 그다음으로 인접한 11과 4를 비교합니다. 4는 11보다 작으므로 대소 관계를 만족하지 않습니다. 따라서 위와 같이 두 ..

[파이썬으로 배우는 알고리즘] 이분 탐색(Binary Search)

이분 탐색(Binary Search)이란? 이분 탐색(Binary Search)이란 탐색 범위를 절반으로 나눠가며 데이터를 탐색하는 방법입니다. 우리가 흔히 알고 있는 순차 탐색(Linear Search)은 데이터를 앞에서부터 하나씩 탐색하여 시간 복잡도가 O(N)(N은 데이터의 개수)으로 그렇게 효율적인 탐색 방법은 아닙니다. 하지만 이분 탐색은 데이터의 범위를 절반씩 계속 나눠 탐색하기 때문에 시간 복잡도가 O(logN)으로 순차 탐색보다는 훨씬 효율적인 탐색 알고리즘이라고 볼 수 있습니다. 하지만 데이터가 속해 있는 범위를 알아야 하기 때문에 정렬되어 있는 데이터에서만 이분 탐색을 사용할 수 있습니다. 그러면 이분 탐색이 어떻게 사용되는지 순차 탐색과 어떻게 다른지 과정을 보며 확인해보겠습니다. 이..

[파이썬으로 배우는 알고리즘] 위상 정렬(Topology Sort)

위상 정렬(Topology Sort)이란? 위상 정렬(Topology Sort)은 순서가 정해져 있는 작업을 수행해야 할 때 사용하는 사용할 수 있는 알고리즘입니다. 대학교 수강 과목 리스트를 예로 나타내 볼게요! 저는 컴퓨터공학과 학생이기 때문에 저의 수강 리스트를 위상 정렬로 예를 들면 위와 같이 나타낼 수 있습니다. 자료구조와 컴퓨터구조 수업을 수강하기 위해서는 프로그래밍 실습수업을 선수강해야 하고 알고리즘 수업을 수강하기 위해서는 자료구조 수업을 선수강해야 합니다. 이 과목들을 모두 수강한 후에야 비로소 최종적으로 운영체제 수업을 수강할 수 있습니다. 기억나는 대로 그냥 예시로 든 것이니 실제 선수 과목과 다를지라도 그냥 넘어가 주시면 감사하겠습니다.ㅋㅋㅋㅋ 위상 정렬의 특징 1) 위상 정렬에서는..

[파이썬으로 배우는 알고리즘] 플로이드 워셜(Floyd Warshall) 알고리즘

플로이드 워셜(Floyd Warshall) 알고리즘이란? 플로이드 워셜(Floyd Warshall) 알고리즘은 최단 경로 알고리즘이지만 그래프에서 특정한 노드에서 다른 모든 노드까지의 최단 경로를 구하는 다익스트라 알고리즘과 달리 모든 정점으로부터 모든 정점까지의 최단 경로를 구하는 알고리즘입니다. 플로이드 워셜 알고리즘은 다익스트라 알고리즘과 마찬가지로 동적 계획법을 활용한 알고리즘입니다. 2022.07.31 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 다익스트라(Dijkstra) 알고리즘 [파이썬으로 배우는 알고리즘] 다익스트라(Dijkstra) 알고리즘 다익스트라(Dijkstra) 알고리즘이란? 다익스트라(Dijkstra) 알고리즘은 최단 경로 알고리즘으로 그래프에서 특정한 노드에서..

[파이썬으로 배우는 알고리즘] 다익스트라(Dijkstra) 알고리즘

다익스트라(Dijkstra) 알고리즘이란? 다익스트라(Dijkstra) 알고리즘은 최단 경로 알고리즘으로 그래프에서 특정한 노드에서 다른 모든 노드까지의 최단 경로를 구하는 알고리즘입니다. 그리디 알고리즘 기반에 동적 계획법을 활용한 알고리즘이며 그래프에서 양수 가중치만 있을 때 사용할 수 있습니다. 그러면 과정을 그림과 함께 보면서 다익스트라 알고리즘이 어떻게 동작하는지 알아보도록 할게요! 2022.07.04 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 그래프(Graph) [파이썬으로 배우는 자료구조] 그래프(Graph) 그래프(Graph)란? 그래프는 노드(정점)와 간선으로 이루어진 집합으로 표현되는 자료구조입니다. 위 그래프에서 A, B, C는 노드이고, 이 노드를 연결한 선이 간선입니다..

[파이썬으로 배우는 알고리즘] 프림(Prim) 알고리즘

프림(Prim) 알고리즘 2022.07.28 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 최소 신장 트리(MST) [파이썬으로 배우는 알고리즘] 최소 신장 트리(MST) 신장 트리 신장 트리(Spanning Tree)란 그래프 내의 모든 노드를 포함하면서 사이클(Cycle)이 없는 부분 그래프를 의미합니다. 이때 모든 노드를 포함하면서 사이클이 없다는 조건은 트리의 성립 조건 c4u-rdav.tistory.com 만약 최소 신장 트리의 개념과 프림 알고리즘의 개념을 잘 모르신다면 위의 포스팅한 글을 보고 간단한 개념을 알고 오시는 게 좋을 것 같습니다! 프림 알고리즘은 크루스칼 알고리즘과 더불어 그리디 알고리즘을 기반으로 최소 신장 트리를 구하는 대표적인 알고리즘입니다. 오늘은 프림 알고..

[파이썬으로 배우는 알고리즘] 크루스칼(Kruskal) 알고리즘

크루스칼(Kruskal) 알고리즘이란? 2022.07.28 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 최소 신장 트리(MST) [파이썬으로 배우는 알고리즘] 최소 신장 트리(MST) 신장 트리 신장 트리(Spanning Tree)란 그래프 내의 모든 노드를 포함하면서 사이클(Cycle)이 없는 부분 그래프를 의미합니다. 이때 모든 노드를 포함하면서 사이클이 없다는 조건은 트리의 성립 조건 c4u-rdav.tistory.com 만약 최소 신장 트리의 개념과 크루스칼 알고리즘의 개념을 모르신다면 위의 포스팅한 글을 보고 간단한 개념을 알고 오시는 게 좋을 것 같습니다! 그리디 알고리즘을 기반으로 최소 신장 트리를 구하는 대표적인 알고리즘이라고 했는데 오늘은 크루스칼 알고리즘을 사용해서 최소..

[파이썬으로 배우는 알고리즘] 최소 신장 트리(MST)

신장 트리 신장 트리(Spanning Tree)란 그래프 내의 모든 노드를 포함하면서 사이클(Cycle)이 없는 부분 그래프를 의미합니다. 이때 모든 노드를 포함하면서 사이클이 없다는 조건은 트리의 성립 조건이기도 하기 때문에 트리라고 불립니다. 2022.07.04 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 그래프(Graph) [파이썬으로 배우는 자료구조] 그래프(Graph) 그래프(Graph)란? 그래프는 노드(정점)와 간선으로 이루어진 집합으로 표현되는 자료구조입니다. 위 그래프에서 A, B, C는 노드이고, 이 노드를 연결한 선이 간선입니다. 두 노드가 연결되어 있 c4u-rdav.tistory.com 2022.07.08 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 트리(Tr..

[파이썬으로 배우는 알고리즘] Union-Find 알고리즘

Union-Find의 개념 Union-Find 알고리즘을 알기 위해서는 Disjoint Set의 개념부터 알고 가야 합니다. Disjoint Set이란? Disjoint Set이란 상호배타적인 집합으로 서로 중복되지 않는 부분 집합들로 나눠진 원소들의 데이터를 처리하기 위한 자료구조입니다. 그렇다면 이런 자료구조는 왜 필요할까요? 만약 어떤 그래프에서 한 노드와 또 다른 노드의 연결 여부를 파악한다고 해보겠습니다. 이럴 경우 완전 탐색 알고리즘인 DFS와 BFS 알고리즘으로 파악할 수 있겠죠? 하지만 할 때마다 이런 탐색을 한다고 하면 한 번의 탐색당 O(N)라는 시간 복잡도를 갖게 되고, 이는 매우 비효율적인 탐색이 될 수 있습니다. 이를 해결하기 위해서 Disjoint Set을 사용해 연결된 노드끼리..