본문 바로가기

Algorithm/Study

Algorithm/Study 2021. 9. 24. 그래프 이론 : 위상 정렬 알고리즘 위상 정렬 알고리즘 PRE. 진입차수 : 특정한 노드로 들어오는 간선의 개수 위상 정렬 알고리즘 개념 - 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것' - 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용한다. - ex. 선수 과목을 고려한 학습 순서 설정 - 시간 복잡도 : O(V +E) // 차례대로 모든 노드 확인하고, 해당 노드에서 출발하는 간선을 차례대로 제거. (노드, 간선 둘다 확인) - 과정 1) 진입차수가 0인 노드를 큐에 넣는다. 2) 큐가 빌 때까지 다음의 과정을 반복한다. 2-1) 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. 2-2) 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. (모든 원소를 방문하기 전에 큐..
Algorithm/Study 2021. 9. 24. 그래프 이론 : 크루스칼 알고리즘 크루스칼 알고리즘 PRE. 신장 트리 : 하나의 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 크루스칼 알고리즘 개념 : 최소한의 비용으로 신장 트리를 찾을 때 사용하는 대표적인 최소 신장 트리 알고리즘 : N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있게 도로를 설치하는 경우 - 그리디 알고리즘, 서로소 판별 알고리즘(사이클) - 최종적으로 신장 트리에 포함되는 간선 개수 = 노드 개수 - 1 - 항상 최적의 해 - 시간 복잡도 : O(ElogE) (E : 간선 개수) // 간선 정렬 작업. 서로소집합 알고리즘은 정렬 알고리즘 보다 시간복잡도 작음. - 과정 1) 모든 간선에 대하여 간선 데이터를 비용에 따라 오름차순으로 정렬..
Algorithm/Study 2021. 9. 24. 그래프 이론 : 서로소 집합을 활용한 사이클 판별 서로소 집합을 활용한 사이클 판별 - 무방향 그래프 내에서의 사이클을 판별할 때 사용 - 방향 그래프는 dfs를 이용하여 판별 - 동작 과정 1. 각 간선을 확인하며 두 노드의 루트 노드를 확인한다. 1-1. 루트 노드가 서로 다르다면 두 노드에 대하여 union 연산을 수행한다. 1-2. 루트 노드가 서로 같다면 사이클이 발생한 것이다. 2. 그래프에 포함되어 있는 모든 간선에 대하여 1번 과정을 반복한다. (union 연산 : a가 속한 집합, b가 속한 집합 중 루트 원소 값이 더 작은 것으로 부모를 통일하는 연산) - 코드 # 특정 원소가 속한 집합을 찾기 def find_parent(parent, x): # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출 if parent[x] ..
Algorithm/Study 2021. 9. 24. 최단 경로 알고리즘 : 플로이드 워셜 플로이드 워셜 알고리즘 개념 - 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용하는 알고리즘 (↔ 다익스트라 알고리즘 : 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우에 사용하는 알고리즘) - 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다. - 2차원 리스트에 최단 거리 정보를 저장한다. - 시간 복잡도 : O(N^3) - 다이나믹 프로그래밍이다. (점화식 사용) Dab = min(Dab, Dak + Dkb) A에서 B로 가는 최소 비용과 A에서 K를 거쳐 B로 가는 비용을 비교하여 더 작은 값으로 갱신한다. 구현 INF = int(1e9) # 노드 개수, 간선 개수 n = int(input()) m = int(input()) #..
Algorithm/Study 2021. 9. 24. 최단 경로 알고리즘 : 다익스트라 최단 경로 알고리즘은 그리디 알고리즘 및 다이나믹 프로그래밍 알고리즘의 한 유형으로 볼 수 있다. 다익스트라 최단 경로 알고리즘 개념 - 그래프에 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구하는 알고리즘이다. - '음의 간선'이 없을 때 사용할 수 있다. - GPS 소프트웨어 기본 알고리즘으로 채택되곤 한다. - 그리디 알고리즘으로 분류된다. (매번 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복하기 때문) - heapq(우선순위 큐) 사용 시, 시간 복잡도 : O(ElogV) (V : 노드 개수, E : 간선 개수) 최단 거리가 가장 짧은 노드를 순차 탐색이 아니라 힙 자료구조를 사용함으로써 시간복잡도를 줄인다. 힙 자료구조를 이용하면 특정 노드까..
Algorithm/Study 2021. 9. 24. 다이나믹 프로그래밍 다이나믹 프로그래밍(동적 계획법) 개념 - 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘 - 연산속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘 - 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결한다. - 다이나믹 프로그래밍 vs 분할정복(ex. 퀵 정렬) 더보기 동적 계획법의 접근 방식은 기본적으로 분할 정복 알고리즘과 비슷하다. 위에서도 설명했지만 동적 계획법을 사용하는 알고리즘 역시 주어진 문제를 부분 문제로 나누어 각 부분 문제의 답을 계산하고, 이 계산한 결과값을 이용해 원래 문제의 답을 산출하기 때문이다. 여기서 분할정복과 차이가 생기는 부분은 원래의 문제를 부분 문제로 나누는 방식에 있다. 동적 계획법의 경우 주어진 문제를 나눌 때 ..
Algorithm/Study 2021. 9. 24. 이진탐색 알고리즘 (Python) 이진 탐색 개념 - 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘이다. - 데이터가 정렬되어 있어야 사용할 수 있다. - #시작점 #끝점 #중간점 - 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다. - 시간 복잡도 : O(logN) - 연산 횟수가 매번 감소하기 때문에 입력 데이터가 매우 많거나 탐색 범위가 매우 넓을 때 사용한다. - sys 라이브러리의 readline() 함수를 이용하면 시간 초과를 피할 수 있다. import sys # 하나의 문자열 데이터 입력받기 # 한 줄 입력받고 나서 꼭 rstrip()으로 함수를 호출해야 공백문자를 제거할 수 있다. input_data = sys.stdin.readline().rstrip() print(inp..
Algorithm/Study 2021. 9. 17. 그래프 탐색 알고리즘 : BFS (Python) BFS - 개념 : 가까운 노드부터 탐색하는 너비 우선 탐색 알고리즘 (DFS는 최대한 멀리 있는 노드 우선 탐색) - 큐 자료구조 이용 (= 파이썬 deque 라이브러리) - 시간 복잡도 : O(N). (실제 수행 시간은 DFS보다 좋은 편이다. 이유 - DFS의 재귀함수 사용) - 장점 : 1) 현재 노드에서 가까운 곳부터 찾기 때문에 경로를 탐색 시 먼저 찾아지는 해답이 곧 최단경로임을 보장한다. 2) 노드의 수가 적고 깊이가 얕은 해가 존재할 때 효과적이다. - 단점 : 1) 큐를 이용해서 다음에 탐색할 노드를 저장하기 때문에 더 큰 저장공간이 필요하다. 2) 노드의 수가 늘어나면 탐색해야하는 노드 또한 많아지기 때문에 비효율적이다. - 사용예 : 최단경로, 최소신장트리 - 구현 방식 : 인접한 ..

티스토리툴바