Data Structure & Algorithm
-
플로이드워셜(Floyd–Warshall) 알고리즘Data Structure & Algorithm 2021. 5. 12. 16:32
플로이드워셜 알고리즘은 각 정점에서 다른 모든 정점까지의 최단경로를 구할 수 있는 알고리즘이다. 기본적인 아이디어는 노드 A에서 노드 B로 이동에 필요한 비용과 노드 T를 경유하는 즉 노드 A -> 노드 T -> 노드 B 순으로 이동했을 때의 비용을 비교하여 노드 T를 경유한 경우의 비용이 작으면 A -> B 이동 비용을 작은 값으로 변경하는 것이다. 플로이드워셜 알고리즘의 점화식 cost(A, B)를 노드 A에서 노드 B로 이동하는 비용 이라 하고 T를 경유하는 노드라 할 때 cost(A, B) = min(cost(A, B), cost(A, T) + cost(T, B)) 플로이드워셜 알고리즘의 시간복잡도 노드의 개수를 N이라 할 때, 1 ~ N 노드는 모두 경유 노드가 될 수 있다. 경유 노드를 제외한..
-
다익스트라(Dijkstra) 알고리즘Data Structure & Algorithm 2021. 5. 6. 16:36
N개의 정점과 M개 간선으로 이뤄진 그래프가 있다고 하자. 이때 N개의 정점 중 하나를 시작점으로 하여 나머지 N - 1개의 정점들까지의 최단거리 경로를 구하는 알고리즘 중 하나가 다익스트라 알고리즘이다. (참고: 간선 가중치가 없는 그래프의 최단거리 경로는 BFS를 통해 구할 수 있다.) 다익스트라 알고리즘은 간선에 가중치가 있는 방향 그래프에서 최단거리 경로를 구하기 위해 사용한다. 따라서 만약 방향 그래프가 아니라면 하나의 간선에 대해 양방향으로 이어지는 방향 그래프로 변환해야 한다. 즉, 무방향 그래프로 데이터가 주어지는 경우 그래프를 인접 리스트 형태로 만들어줄 필요가 있다. 이후 가중치의 표현은 w(A, B)라 하자. 의미는 정점 A에서 정점 B로 이동하는 가중치이다. 단, 가중치가 음수인 간..
-
구현 예제1: n * n 리스트에 나선형으로 값 채우기Data Structure & Algorithm 2021. 4. 6. 09:24
N x N size의 2차원 리스트가 있습니다. 시작 인덱스는 (0, 0)이며 그 값은 1입니다. 처음 진행 방향은 오른쪽이며 진행 방향을 따라 나선형으로 돌면서 값을 1씩 증가시키며 각 인덱스를 채운 리스트를 만들어주세요. 입력) 4 출력) [[1, 2, 3, 4],[12, 13, 14, 5],[11, 16, 17, 6],[10, 9, 8, 7]] 위를 구현한 소스코드는 다음과 같습니다. import sys n = int(sys.stdin.readline().rstrip()) spiral_list = [[0] * n for _ in range(n)] # limit points of each direction lp_left_side = 0 lp_right_side = n - 1 lp_up_side = 1..
-
동적 계획법 예제2: Longest Common Subsequence 문제Data Structure & Algorithm 2021. 4. 1. 16:50
먼저 문자열의 sub sequence는 문자열에 속한 각 문자의 순서를 유지한 채 만들 수 있는 부분집합입니다. 예를 들어 'AB'라는 문자열이 있는 경우 빈 문자열 ''와 'A', 'B', 'AB'가 모두 seb sequence가 됩니다. 'BA'는 순서가 바뀌었으므로 sub sequence가 되지 않습니다. 두 문자열 X, Y가 있을 때 문자열 간에 공통된 sub sequence 중 가장 긴 sequence의 길이를 구해보도록 합시다. X, Y의 길이가 길어짐에 따라 X의 sub sequence를 뽑아내서 다시 Y의 sub sequence들과 비교하도록 하는 brute force 방식으로 접근하기에는 연산량이 너무나 많아집니다. 이런 경우 보통 동적 계획법을 통해 해결 가능한 문제가 아닌지 의심해야 ..
-
동적계획법 예제1: 정수 리스트(배열)의 최대 부분합 구하기Data Structure & Algorithm 2021. 4. 1. 12:38
다음과 같이 정수 리스트가 주어졌다고 합시다. [-2, -3, 4, -1, -2, 1, 5, -3] 이 때 연속된 부분 리스트의 합 가운데 최대 값은 어떻게 구해야 할까요? 가장 먼저 생각해볼 수 있는 방법은 모든 부분배열을 만들어 그 합을 구한 뒤 가장 큰 값을 구하는 것이 되겠습니다. def maximum_sub_sum_bruteforce(data): max_sub_sum = int() for e in data: if e max_sub_sum: max_sub_sum = sub_sum re..
-
동적 계획법 (Dynamic Programming)Data Structure & Algorithm 2021. 2. 15. 13:06
동적 계획법(Dynamic programming)이란 최적의 하위 구조를 가진 문제를 처리하는 중에 반복되는 연산을 최소화하여 효율적인 알고리즘을 작성할 수 있도록 하는 프로그래밍 기법입니다. 1. 동적 계획법 유형의 문제인지 확인 문제 해결을 위해 완전 탐색 알고리즘을 적용했을 때 비효율적인 경우 내부적으로 동작하는 일련의 반복되는 연산 중 중복되는 동일 연산이 있는지 확인합니다. 만약 중복되는 연산이 있다면 연산 결과를 메모리에 임시로 저장하고 이후 동일 연산은 메모리 내에 미리 계산된 값을 사용하도록 코딩하여 효율적인 코드를 작성합니다. 중복되는 연산이라 함은 n항의 값을 구하기 위해 n-1항 이하의 연산 결과가 반복적으로 사용되는 것을 말합니다. 예를 들어 f(n) = f(n-1) + 1 또는 f..
-
알고리즘의 효율성을 표현하는 Big-O 표기법Data Structure & Algorithm 2021. 2. 12. 09:27
Big-O표기법을 사용하여 알고리즘의 복잡도를 표현할 수 있습니다. 현대에 들어 컴퓨팅 파워가 올라가고 탑재되는 메모리량이 비약적으로 늘어남에 따라 공간 복잡도 보다 시간 복잡도를 줄이는데 비중을 두는 것이 일반적입니다. 따라서 이하 복잡도는 시간 복잡도만 다루도록 하겠습니다. Big-O는 데이터 증가량에 따른 알고리즘의 성능을 예측하기 위한 표기법이므로 상수항은 모두 무시하게 됩니다. (e.g) O(2n + 1) -> O(n), O(3000n² + 10000000) -> O(n²) 대표적인 복잡도와 sample code 1. O(1) - 상수시간 data = [1, 2, 3, 4, 5] def function(n): return n[0] == 1 function(data) 데이터량과 상관없이 항상 일정..
-
이진 탐색(Binary Search)Data Structure & Algorithm 2021. 2. 7. 09:21
정렬되어 있는 데이터에서 특정 데이터가 존재하는지 확인하는 알고리즘입니다. [아이디어] 데이터의 중간 인덱스에 해당하는 값과 찾고자 하는 값을 비교합니다. 중간 인덱스의 값과 찾는 값이 일치하면 데이터가 존재하는 것입니다. 찾고자 하는 값이 중간 인덱스의 값보다 작은 경우는 탐색 범위를 시작인덱스 ~ 중간인덱스 - 1 로 좁혀 다시 탐색을 진행합니다. 찾고자 하는 값이 중간 인덱스의 값보다 큰 경우는 탐색 범위를 중간인덱스 + 1 ~ 끝인덱스로 좁혀 다시 탐색을 진행합니다. 탐색 범위가 인덱스 하나로 좁혀졌으나 해당 인덱스의 값이 찾는 값과 다른 경우는 전체 데이터에서 찾는 값이 없다는 것을 의미합니다. 탐색할 인덱스가 하나 밖에 없는 상태에서 찾는 데이터가 hit하지 않으면 중간 인덱스의 값은 찾고자 ..