분류 전체보기

[파이썬으로 배우는 알고리즘] 다익스트라(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을 사용해 연결된 노드끼리..

[백준(BOJ)] #11000- 강의실 배정 (파이썬, Python3)

문제 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 문제 풀이 이 문제는 그리디 알고리즘과 우선순위 큐를 이용해서 해결할 수 있습니다. 2022.07.18 - [알고리즘/개념] - [파이썬으로 배우는 알고리즘] 그리디(Greedy) 알고리즘 [파이썬으로 배우는 알고리즘] 그리디(Greedy) 알고리즘 그리디(Greedy) 알고리즘이란? Greedy는 '탐욕스러운'이라는 뜻을 가진 단어로 탐욕 알고리즘이라고도 불리며 말 그대로 선택의 순간마다 당장 좋은 것만 고르는 방법을 의미합니다. 순간의..

[파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming)

동적 계획법(Dynamic Programming)이란? 동적 계획법(Dynamic Programming), 다이나믹 프로그래밍, DP라고 불리는 이 알고리즘은 무엇일까요?? 동적 프로그래밍? 저는 이 말을 처음 접했을 때 의미에 대해 생각을 해봤는데 알고 보니까 이름하고는 별 상관이 없더라구요..ㅋㅋㅋㅋㅋ 동적 계획법은 어떤 문제를 여러개의 작은 문제로 나눠 해결하고 그 결과를 저장을 했다가 큰 문제를 풀 때 사용하는 문제 풀이 기법입니다! 즉, 한 번 푼 문제는 다시 풀지 않게 되는 것이죠. 분할 정복 알고리즘과 비슷하다고 생각하실 수도 있는데 해결한 문제를 반복적으로 해결하는 분할 정복과는 달리 동적 계획법은 이미 푼 문제는 기억하여 다시 풀지 않기 때문에 부분 문제가 중복된다면 더욱 효율적이라고 볼..

[파이썬으로 배우는 알고리즘] 분할정복(Divide & Conquer)과 병합/퀵정렬

분할정복(Divide & Conquer) 알고리즘이란? 문제 해결에 있어서 어떤 문제를 더이상 쪼갤 수 없을 때까지 분할한 후 (Divide) 하위 문제들을 해결하고 (Conquer) 합치면서(Combine) 문제의 답을 도출하는 알고리즘을 분할정복(Divide & Conquer) 알고리즘이라고 합니다. 설명만으로는 잘 이해가 안 갈 수도 있으니 대표적인 분할정복 문제인 병합정렬(Merge Sort)과 퀵정렬(Quick Sort)을 예시로 직접 풀어보면서 설명하도록 하겠습니다! 병합정렬(Merge Sort) 병합정렬 개념 1) 정렬할 리스트를 더 이상 나눌 수 없을 때까지 2개의 부분 리스트로 분할(Divide) 2) 더이상 나눌 수 없는 부분 리스트를 다시 합치면서 정렬 수행(Conquer, Combi..