algorithm/개념
-
[Python] 위상정렬algorithm/개념 2023. 6. 16. 19:49
🔎 위상 정렬 이란? 사이클이 없는 방향 그래프 (DAG) 의 방향에 맞게 모든 노드를 순서대로 나열하는 것 진입 차수 : 특정한 노드로 들어오는 edge 의 수 진출 차수 : 특정한 노드에서 나가는 edge 의 수 작동 순서 1. 진입 차수가 0인 모든 노드를 큐에 넣는다. 2. 큐가 빌 때 까지 다음을 반복한다 큐에 우너소를 꺼내 해당 노드에서 나가는 간선 제거 새롭게 진입 차수가 0이 된 노드를 큐에 삽입 큐에 들어온 순서 = 위상 정렬 결과 📋 example) 📜 code from collections import deque # 노드의 개수와 간선의 개수를 입력 받기 v, e = map(int, input().split()) # 모든 노드에 대한 진입차수는 0으로 초기화 indegree = [0]..
-
[Python] 크루스칼 알고리즘 / MST / 최소 신장 트리algorithm/개념 2023. 6. 16. 18:47
🔎 크루스칼 알고리즘이란? 대표적인 최소 신장 트리 알고리즘이다. 그리디 알고리즘으로 분류된다. 신장트리란? 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프이다. 최소신장트리란? 하나의 그래프에서 많은 신장트리 중에 최소한의 비용으로 구성된 신장트리이다. 동작 과정 1. 간선 데이터를 비용에 따라 오름차순 정렬 2. 간선을 하나씩 확인하면서 현재의 간선이 사이클을 발생시키는지 확인 사이클 발생 O > 최소 신장 트리에 포함 X 사이클 발생 X > 최소 신장 트리에 포함 O 3. 모든 간선에 대하여 2를 반복 cost 가 낮은 edge 부터 차례대로 사이클이 발생하는지 확인합니다. 이때 union-find 가 활용되는데 아래 게시물을 참고해주세요. 2023.06.16 - [algori..
-
[Python] Union - Find 유니온 파인드/서로소 집합algorithm/개념 2023. 6. 16. 17:32
🔎 Union Find (서로소 집합) 란? 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 1. 합집합 (Union) : 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 Union (A,B) : A와 B를 하나의 집합으로 합치는 연산 1) A와 Bdml 루트 노트 A', B' 를 각각 찾는다. 2) A'를 B'의 부모 노드로 설정 모든 합집합 연산을 찾을 때까지 위 과정을 반복한다. 2. 찾기 (Find) : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 📋 example) Union(1,4) Union(2,3) Union(2,4) Union(5,6) 을 해보자 - 유니온 파인드는 루트 노드에 즉시 접근할 수 없고 부모 테이블을 계속 확인해서 거슬러 올라가야 ..
-
[자료구조] 우선순위 큐와 힙 / 최소 힙 / 최대 힙 / heap /algorithm/개념 2023. 3. 31. 00:21
우선순위 큐 Queue 자료구조는 먼저 집어 넣은 데이터가 먼저 나오는 선입선출 FIFO(First In First Out) 구조로 저장 우선순위큐(priority queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터 먼저 나온다. 힙 (Heap) 이란? Heap은 우선순위큐(priority queue)의 구현과 일치 Heap은 완전이진트리 구조 최소 힙 : 각 node에 저장된 값은 child node들에 저장된 값보다 작거나 같다 최대 힙 : 각 node에 저장된 값은 child node들에 저장된 값보다 크거나 같다 파이썬 힙 함수 heapq.heappush(heap, item) : item을 heap에 추가 heapq.heappop(heap) : heap에서 가장 작은 원소를 pop + 리..
-
[알고리즘] 완전탐색 / itertools / 순열 중복순열 조합 중복조합algorithm/개념 2022. 3. 12. 17:37
itertools 모듈 순열 permutations(list, r=None) 중복순열 product(list, repeat=1) 조합 combinations(list, r) 중복조합 combinations_with_replacement(list, r) # 순열 : permutations(list, r=None) from itertools import permutations random_list=['A','B','C'] resultA=permutations(random_list) resultB=permutations(random_list,2) print(list(resultA)) print(list(resultB)) 결과>> [('A', 'B', 'C'), ('A', 'C', 'B'), ('B', 'A',..