Algorithm/Algorithm Theory
-
[Algorithm] 분할 정복 알고리즘 (Divide and Conquer)Algorithm/Algorithm Theory 2022. 5. 9. 21:22
분할 정복 크고 방대한 문제를 작은 문제 단위로 나눈 다음 그것을 다시 합쳐서 해결하는 알고리즘이다. 이 알고리즘은 3가지 단계를 가진다. Divide : 문제를 더이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눈다. Conquer : 작은 단위의 문제를 해결한다. Combine : 해결한 문제의 결과를 통합하여 답을 얻는다. 대표적인 예로 quick sort나 병합정렬이 있다. 병합 정렬 https://miraekwak.tistory.com/73?category=922962 [Algorithm] 정렬 알고리즘 & Python3 코드 & 시간복잡도 정리 1. 병합 정렬 분할 정복 방식을 이용한 알고리즘으로 말 그대로 배열을 분할 후 정렬하면서 병합하는 방식이다. 배열의 원소를 절반씩 잘라..
-
[Algorithm] 동적계획법(Dynamic Programming)Algorithm/Algorithm Theory 2022. 4. 7. 21:43
Dynamic Programming 동적 계획법은 문제를 해결할 때 하나의 문제를 여러개의 작은 문제로 나누어서 작은 문제의 결과를 기억해두었다가 이를 사용하여 큰 문제를 해결하는 것이다. 재귀처럼 반복적으로 작은 문제들에 접근할 경우 이를 구하기 위해서 오랜 시간이 걸리기 때문에 비효율적이다. 따라서 이러한 반복적인 접근을 피하기 위해 메모리제이션, 기억해두는 방법을 사용하게 되는 것이다. 대표적인 예로 피보나치 수열이 있다. int fibo(n): if n
-
[Algorithm] 백트랙킹(BackTracking)Algorithm/Algorithm Theory 2022. 3. 31. 01:51
백트랙킹 백트랙킹은 가능한 모든 방법을 탐색한다. 즉, 현재 상태에서 가능한 모든 후보를 따라 후보를 다시 탐색하면서 해를 찾아나가다가 해가 아니라고 판단되면 다시 되돌아가 다른 후보를 탐색하여 해를 찾아가는 방식이다. 이는 최적화 문제와 결정문제를 푸는 방법이 된다. 위의 상황을 트리에 적용해보면 트리 탐색 알고리즘이라고 생각할 수 있다. 트리 탐색 알고리즘은 방식에 따라서 깊이 우선 탐색(Deep First Search, DFS), 너비 우선 탐색(Breadth First Search, BFS)으로 나눌 수 있다. 백트랙킹은 모든 경우의 수를 고려해야하기에 DFS로 구현한다. 더보기 DFS(Deep First Search) 트리의 root에서 바닥에 도달할 때까지 한 쪽에서 시작하여 가능한 모든 경로..
-
[Algorithm] 정렬 알고리즘 & Python3 코드 & 시간복잡도 정리Algorithm/Algorithm Theory 2022. 3. 26. 00:23
1. 병합 정렬 분할 정복 방식을 이용한 알고리즘으로 말 그대로 배열을 분할 후 정렬하면서 병합하는 방식이다. 배열의 원소를 절반씩 잘라 계속해서 나눈 후 => 분할 배열의 원소의 개수가 1개가 되면 이웃한 배열의 원소와 크기를 비교하여 정렬하면서 합치기 => 병합 다음과 같이 그림으로 나타낼 수 있다. 분할을 하게되면 분할되는 깊이가 N log N에 비례하고 배열을 합치는 과정을 생각하면 최대 배열의 개수는 N개, 즉 원소의 개수만큼 생기게 되어 N에 비례한다. 따라서 병합정렬의 시간 복잡도는 O(N log N) 이다 Python3 Code def merge_sort(numbers): if len(numbers) = right[r]: numbers[i] = right[r] r += 1 else: num..