GCD (최대공약수) 를 구하는 유클리드 알고리즘은 아래 게시글에서 볼 수 있다. 2022.12.09 - [ALGORITHM/알고리즘 알아보기] - [Algorithm] 유클리드 호제법 (최대 공약수, 최소 공배수) [Algorithm] 유클리드 호제법 (최대 공약수, 최소 공배수) 최대 공약수 숫자 a,b가 주어졌을 때, 공통되는 약수 중 최대 값을 의미한다. 구하는 방법 a,b 각각의 약수를 구해서 공통되는 약수 중 가장 큰 값을 찾는 방법 찾지 않아도 되는 약수들까지 구해 cheon2308.tistory.com 이번에는, 여기서 확장된 확장 유클리드 알고리즘에 대해서 알아보자. 확장 유클리드 알고리즘을 알기 전에 배주 항등식 (Bezout's Identity)를 먼저 알아야 한다. 확장 유클리드 호..

플로이드-워셜 (Floyd-warshall) 알고리즘은 앞서 알아본 다익스트라, 벨만-포드와 같이 그래프에서 최단 거리를 구하는 알고리즘이다. 모든 노드 간에 최단 경로를 탐색 음수 가중치 에지가 있어도 수행할 수 있음 동적 계획법(dp)의 원리를 이용해 알고리즘에 접근한다. 노드 수 -> V일 때 O(V^3)의 시간 복잡도를 가진다. 핵심 이론 A노드에서 B노드까지 최단 경로를 구했다고 가정했을 때, 최단 경로 위에 K 노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로이다. 즉, 전체 경로의 최단 경로는 부분 경로의 최단 경로의 조합으로 이루어진다. 위와 같은 원리로 아래와 같은 점화식을 도출할 수 있다. D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]) 구현..

LCS (Longest Common Subsequence) 란? 2개 이상의 문자열에서 공통으로 나타나는 부분 문자열 중 가장 긴 문자열을 의미 대표적으로 DNA의 공통 염기서열을 찾아 데이터를 압축하거나 무선 서명을 통해 휴대폰에서 사용자를 인증할 때 사용 풀이 방법 분할정복이 아닌 DP를 이용하여 풀이해준다. 1. Top-down 방법 (재귀적 풀이) 문자열 X, Y 가 X = [x1, x2, x3, .... , xm], Y = [y1, y2, y3, ... , yn] 일 때, 아래와 같은 과정을 반복한다. LCS(X, Y): #수열 X와 Y의 최장 공통 부분 수열(LCS)의 길이 m, n = len(X), len(Y) if m == 0 or n == 0: return 0 else: if X[-1] ..

최대 공약수 숫자 a,b가 주어졌을 때, 공통되는 약수 중 최대 값을 의미한다. 구하는 방법 a,b 각각의 약수를 구해서 공통되는 약수 중 가장 큰 값을 찾는 방법 찾지 않아도 되는 약수들까지 구해야하기 때문에 비효율적이다. 유클리드 호제법 숫자 a,b가 있을 때, a를 b로 나눈 나머지와 b의 최대 공약수는 a와 b의 최대 공약수가 같다는 것을 의미한다. 따라서, a를 b로 계속 나누어서 b에 a로 나눈 나머지를 대입시켜서 b가 0이 될 때까지 반복을 하면, 남는 a의 값이 바로 최대 공약수이다. def gcd(a, b): while b > 0: a, b = b, a % b return a 최소 공배수 서로 다른 수 a,b의 배수 중에서 공통되는 배수 중 가장 작은 값을 의미 최소 공배수는 a,b의 곱..

최단 경로를 구하는 알고리즘에는 다익스트라 (dijkstra algorithm) 벨만-포드 (Bellman-Ford algorithm) 플로이드 워셜 ( 아직 공부 x ) 이 존재한다. 다익스트라 참고 - 2022.09.23 - [ALGORITHM/알고리즘 알아보기] - [알고리즘] 다익스트라 알고리즘 다익스트라 알고리즘은 그리디(greedy)를 기반으로 우선순위 큐를 사용하여 최단 경로를 사용하는데 그리디가 기반이기 때문에 간선의 가중치가 음수 인 것이 존재하면 안 된다. 위와 같은 경로에서 A->D로 이동하는 최소 비용을 고려할 때, 다익스트라 알고리즘의 경우 근시안적 관점을 유지하기 때문에, 가중치가 감소하는 것을 고려하지 않고 B에서 D로 가는 경로를 선택하게 되기 때문이다. 벨만 - 포드 알고리..

투 포인터란? 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘 시작점과 끝점 - 2개의 점으로 접근할 데이터의 범위를 표현 할 수 있다. 동작 과정 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)를 가리키도록 한다. 현재 부분 합이 M과 같다면 카운트 한다. 현재 부분 합이 M보다 작다면 end를 1 증가시킨다. 현재 부분 합이 M보다 크거나 같다면 start를 1 증가시킨다. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다. 예제 # 데이터의 개수 N n = 5 # 찾고자 하는 부분합 M m = 5 # 전체 수열 data = [1, 2, 3, 2, 5] count = 0 interval_sum = 0 end = 0 # start를 차..

이분 탐색(Binary Search) 문제들 중 최적화를 위해 결정 문제로 바꿔서 푸는 매개 변수 탐색 문제가 있다. 앞에서 많이 살펴 봤지만 이분 탐색에 대해 간단히 복습해보자. 목차 이분 탐색 LOWER, UPPER BOUND 매개변수 탐색 1. 이분 탐색 정렬된 배열에서 사용 가능한 알고리즘 시작, 끝, 중간점을 이용해 탐색 범위를 절반씩 좁혀가며 탐색한다. target data와 middle data 값을 반복적으로 비교하여 원하는 데이터를 찾는다. 예 - 4를 찾는 과정 # 참고 https://velog.io/@guswns3371/%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%EB%A7%A4%EA%B0%9C-%EB%B3%80%EC%88%98-%ED%83%90%EC%83%8..

목차 최소 신장 트리 Prim 알고리즘 KRUSKAL 알고리즘 1. 최소 신장 트리(Minimum Spanning Tree) 그래프에서 최소 비용 문제 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리 두 정점 사이의 최소 비용의 경로 찾기 신장 트리 n개의 정점으로 이루어진 무방향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 최소 신장 트리 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리 간선의 가중치의 합이 최소여야 한다. 사이클이 포함되어서는 안된다. 사용 사례 통신망, 도로망, 유통망에서 길이, 구축 비용, 전송 시간 등을 최소로 구축하려는 경우 표현 그래프 간선들의 배열 인접 리스트 부모 자식 관계와 가중치에 대한 배열 트리 2...

다익스트라(dijkstra) 알고리즘은 일상생활에서, 지하철, 내비게이션 등 여러 분야에서 사용되는 알고리즘이다. 활용 예시를 보면 알 수 있듯이 최단 경로 알고리즘인 다익스트라 알고리즘을 알아보자. # 다익스트라 알고리즘 하나의 시작 정점에서 모든 다른 정점까지의 최단 경로를 찾는 알고리즘 자료 구조로는 그래프(graph) 사용 노드와 가중치를 가진 간선을 이용하여 실제 거리를 표시한다. 초기에 우선순위 큐를 사용하지 않은 다익스트라 알고리즘 O(V^2)의 시간 복잡도 우선순위 큐로 인한 개선으로 O(E log V) - V, E = 노드와 간선의 수 삽입 삭제, 최소 값 추출 - O(logV) 기본적으로 다익스트라는 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 사용 => 다이나믹 ..