본문 바로가기

분류 전체보기

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) 노드의 수가 늘어나면 탐색해야하는 노드 또한 많아지기 때문에 비효율적이다. - 사용예 : 최단경로, 최소신장트리 - 구현 방식 : 인접한 ..
Algorithm/Study 2021. 9. 17. 그래프 탐색 알고리즘 : DFS (Python) DFS - 개념 : 그래프에서 깊은 부분을 우선적으로 탐색하는 깊이 우선 탐색 알고리즘이다. - 스택 자료구조 이용 (= 파이썬 리스트. 재귀 함수를 이용했을 때 구현이 간결) - 시간 복잡도 : O(N) - 인접리스트로 구현시 - 장점 : 1) BFS에 비해 저장공간의 필요성이 적다. 2) 찾아야 하는 노드가 깊은 단계에 있을 수록, 그 노드가 왼쪽에 있을 수록 BFS보다 유리하다. - 단점 : 1) 목표 노드가 없는 경로에 깊이 빠질 수 있다. 2) 최단 경로가 보장되지 않는다. - 사용예 : 위상정렬, 사이클 탐지 - 구현 # DFS def dfs(graph, v, visited): visited[v] = True # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]:..
Algorithm/Study 2021. 9. 17. 그래프 탐색 알고리즘 : 인접 행렬과 인접 리스트 (Python) 인접 행렬 - 개념 : 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식 - 모든 관계를 저장하므로 노드의 개수가 많을 수록 메모리가 낭비된다. - 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 빠르다. - 구현 INF = 999999999 # 9 자리수 # 2차원 리스트를 이용해 인접 행렬 표현 graph = [ ''' [노드0과 노드0 간선 비용, 노드0과 노드1 간선 비용, 노드0과 노드2 간선 비용] [노드1과 노드0 간선 비용, 노드1과 노드1 간선 비용, 노드1과 노드2 간선 비용] [노드2와 노드0 간선 비용, 노드2와 노드1 간선 비용, 노드2와 노드2 간선 비용] ''' [0, 7, 5], [7, 0, INF], [5, INF, 0] ] print(graph) 인접 리스..
Algorithm/Study 2021. 9. 17. 그리디 알고리즘 (Python) 그리디 알고리즘 위 그림처럼 그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 특정 문제를 만났을 때 단순히 현재 상황에서 가장 좋아보이는 것만을 선택해도 문제를 풀 수 있느지를 파악할 수 있어야 한다. 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시할 때 대체로 그리디 알고리즘과 정렬 알고리즘을 함께 사용할 수 있다. 거스름돈 문제 500원, 100원, 50원, 10원짜리 동전히 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다. 1) 아이디어 : 가장 큰 화폐 단위부터 돈을 거슬러 ..

티스토리툴바