소피it블로그

자료 출처: https://youtu.be/cswJ1h-How0 알고리즘 천민에게 한 줄기의 빛 같은 동빈님의 강의를 요약해서 정리하고 있다. 열심히 정리하고 학습한 후에는 오직 문제풀이 맹연습뿐.... 알고리즘 양반까지는 힘들더라도 중인까지는 올라가보도록 노력을 거듭해보자 홧팅홧팅 1. 소수 판별 알고리즘 약수의 성질을 이용하면 더 쉽게 풀 수 있다. 약수의 성질이란? 모든 양수는 가운데 약수를 기준으로 대칭이라는 것 따라서 특정 자연수의 모든 약수를 찾을 때, 가운데 약수(제곱근)까지만 확인하면 됨 시간 복잡도: O(N^1/2) 2. 소수 판별 알고리즘 파이썬 구현 import math def is_prime_number(n): for i in range(2, int(math.sqrt(n)) + 1)..

자료 출처: https://youtu.be/aOhhNFTIeFI 1. 위상 정렬 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 알고리즘 진입 차수(Indegree): 특정 노드로 들어오는 간선의 개수 진출 차수(Outdegree): 특정 노드에서 나가는 간선의 개수 2. 큐를 이용하는 위상 정렬 알고리즘 진입 차수가 0인 모든 노드를 큐에 담는다. 큐가 빌 때까지 다음을 반복한다: 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거함 새롭게 진입 차수가 0이 된 노드를 큐에 넣음 결과적으로는, 각 노드가 큐에 들어온 순서와 위상 정렬을 수행한 결과가 동일하다. 위상 정렬에는 여러 가지 답이 존재할 수 있다. 모든 원소를 방문하기 전에 큐가 빈다면? 사이클..

자료 출처: https://youtu.be/aOhhNFTIeFI 1. 신장 트리 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 2. 최소 신장 트리 최소한의 비용으로 구성되는 신장 트리 3. 크루스칼 알고리즘 대표적인 최소 신장 트리 알고리즘으로, 그리디 알고리즘으로 분류된다. 간선 데이터를 비용에 따라 오름차순으로 정렬한다. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다. 사이클이 발생한 경우: 최소 신장 트리에 포함시키지 않음 사이클이 발생하지 않은 경우: 최소 신장 트리에 포함시킴 위의 과정을 모든 간선에 대하여 반복한다. 최소 신장 트리에 포함된 간선의 비용을 모두 더한 값이 최종 비용이다. 4. 파이썬 구현 # 특정 원소가 속한 집합 찾기 def fi..

자료 출처: https://youtu.be/aOhhNFTIeFI 1. 서로소 집합 자료구조 공통 원소가 없는 두 집합으로, Union Find 자료구조라고도 한다. 합집합(Union): 두 개의 원소가 포함된 집합을 하나의 집합으로 합침 찾기(Find): 특정 원소가 속한 집합이 어느 집합인지 알려줌 2. 여러 개의 합치기 연산 합집합(Union) 연산을 확인하고 서로 연결된 두 노드 A, B를 확인한다. A, B의 루트 노드인 A', B'를 각각 찾는다. A'를 B'의 부모 노드로 설정한다. 모든 합집합 연산이 처리될 때까지 위의 과정을 반복한다. 3. 무방향 그래프 내에서 사이클을 판별하기 위한 용도 (방향 그래프에서는 DFS를 이용) 각 간선을 하나씩 확인하며 두 노드의 루트 노드를 확인한다 루트 ..