PS

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

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

[백준(BOJ)] #1197- 최소 스패닝 트리 (파이썬, Python3)

문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 문제 풀이 이 문제는 최소 신장 트리의 가중치를 구하는 문제로 크루스칼 알고리즘을 적용하여 풀었습니다. 2022.07.29 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 크루스칼(Kruskal) 알고리즘 [파이썬으로 배우는 알고리즘] 크루스칼(Kruskal) 알고리즘 크루스칼(Kruskal) 알고리즘이란? 2022.07.28 - [..

[파이썬으로 배우는 알고리즘] 플로이드 워셜(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..

[백준(BOJ)] #1463- 1로 만들기 (파이썬, Python3)

문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 풀이 이 문제는 동적 계획법을 사용하여 풀 수 있습니다. 2022.07.22 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming) [파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming) 동적 계획법(Dynamic Programming)이란? 동적 계획법(Dynamic Programming), 다이나믹 프로그래밍, DP라고 불리는 이 알고리즘은 무엇일까요?? 동적 프로그래밍? 저는 이 말을 처음 접했을 때 의미에 대해 생..

[백준(BOJ)] #1717- 집합의 표현 (파이썬, Python3)

문제 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 문제 풀이 이 문제는 다른 거 할 거 없이 Union-Find 알고리즘만 적용하면 되는 문제입니다. 2022.07.24 - [알고리즘/개념] - [파이썬으로 배우는 알고리즘] Union-Find 알고리즘 [파이썬으로 배우는 알고리즘] Union-Find 알고리즘 Union-Find의 개념 Union-Find 알고리즘을 알기 위해서는 Disjoint S..

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

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