안녕

만약에 8개의 원소를 가지고 있는 리스트를 정렬해야 한다고 가정해봅시다. 이때도 \(\Theta(nlgn)\)인 merge sort가 \(\Theta(n^2)\)인 exchange sort보다 좋을까요? 아마 작은 분할일 때는 오히려 exchange sort가 좋지 않을까요? merge sort가 더 좋다고 말하는 것은 n이 무한대로 갈 때의 얘기입니다. 오히려 n이 작으면 작을수록 다른 알고리즘이 더 좋을 때가 있습니다. 이때 나오는 것이 Threshold, 임계값입니다. 1. 임계값이란? 분할 정복 알고리즘이 A이고, 대체 알고리즘이 B라고 합시다. 계속해서 분할하다 보면 어느 순간부터 B가 더 좋아질 때가 있습니다. 바로 위의 sorting이 예시입니다. 이때, 대체 알고리즘이 더 좋아지는 시점이 ..

만약 하드웨어의 저장 공간을 넘어서는 숫자들의 연산을 해야 한다면 어떻게 해야 할까요? 이 경우에 유일한 대안은 소프트웨어적으로 숫자들을 표현하고 처리해야 합니다. 방법은 숫자들을 하나씩 쪼개서 배열에 넣는 방법이 있습니다. 이때 배열에는 역순으로 넣어야 합니다. 1. 알고리즘 및 코드 우선 긴 숫자를 쪼개 봅시다. \(u\,=\,x\times10^m+y\) \(v\,=\,w\times10^m+z\) 일 때, \(uv\, =\, \left (x \times 10^m + y \right )\left ( w\times10^m+z \right )\) 이고, 이는 \(xw\times10^{2m}+(xz+wy)\times10^m+yz\) 입니다. 이것을 통해 쉽게 계산할 수 있습니다. Problem : 큰 정수의..

from os import sep import sys input = sys.stdin.readline count = 0 def mmult(n, a, b, c): # 단순 행렬 곱셈 for i in range(n): for j in range(n): for k in range(n): c[i][k] += a[i][j] * b[j][k] # += 해줘야함. 그냥 =를 하면 마지막으로 들어가는 값으로만 치환됨 def partition(n, a, a11, a12, a21, a22): # 행렬 분할 for i in range(n): for j in range(n): a11[i][j] = a[i][j] a12[i][j] = a[i][j + n] a21[i][j] = a[i + n][j] a22[i][j] = a[i ..

1. 행렬 곱셈에 대한 간단한 소개 예전의 글에서 구한 행렬 곱셈의 시간 복잡도는 \(T(n)\,=\,n^3\)이었습니다. 왜냐? 두 개의 행렬에 대해 A의 행, B의 열을 곱해야하기 때문입니다. A의 n개의 행에 대해서 B는 \(n^2\)번을 곱해야하기 때문입니다. 하지만 Strassen씨는 시간 복잡도가 \(n^3\)보다 더 빠른 알고리즘을 개발했습니다. 2. Strassen's Algorithm에 대한 소개 행렬 A) \(\begin{bmatrix}a_{11}&a_{12} \\a_{21}&a_{22} \\\end{bmatrix}\) 행렬 B) \(\begin{bmatrix}b_{11}&b_{12} \\b_{21}&b_{22} \\\end{bmatrix}\) 행렬 C) \(\begin{bmatrix}..

1. 알고리즘 및 코드 Problem : 오름차순으로 주어진 리스트를 정렬 Input : 양의 정수 n, 리스트 S Output : 오름차순으로 정렬된 리스트 S 알고리즘) 1. pivot을 기준으로 나눈다. 2. 나눈 pivot의 왼쪽, 오른쪽을 재귀적으로 다시 적용한다. 3. 리스트를 더 이상 나눌 수 없을 때까지 반복한다. (원소가 1개 이하로 남았을 때) 생각의 흐름) pivot은 리스트의 맨 앞을 넣는다. pivot을 기준으로 나누면 되는데, j에 low 위치를 넣고, i를 low + 1의 위치부터 high까지 넣는다. 그러면 for문으로 i를 돌리고, 이때 S[i]가 pivot보다 작으면 j에 1을 더하고, i 위치와 j 위치를 swap한다. 쭉 반복하면 결국 최종적으로 j의 위치가 pivot..

앞선 시간에 merge sort에 대해 설명 드렸습니다. 이번에는 in-place 정렬로 merge sort하는 법을 보여드리겠습니다. 1. 코드 n = int(input()) S = list(map(int, input().split())) def mergesort(low, high): # 두 개로 분할함 if low < high: mid = (low + high) // 2 mergesort(low, mid) mergesort(mid+1, high) merge(low, mid, high) def merge(low, mid, high): # 병합함 i = low; j = mid + 1; U = list() while i

1. Merge Sort의 알고리즘 및 코드 Problem : n개의 원소를 가지고 있는 정렬되지 않은 리스트 S를 오름차순으로 정렬 input : n과 정렬되지 않은 리스트 S output : 정렬된 리스트 S Merge Sort의 알고리즘) 1. 배열을 반으로 분할한다. 2. 분할한 배열을 정렬한다 (배열에 원소가 2개 이상이면 merge sort를 재귀 호출하여 정렬한다) 3. 분할한 배열을 합병하여 정렬한다. 그러면 결국엔 정렬은 배열에 원소가 1개 일 때 일어나겠죠? 근데 원소가 하나밖에 없으면 정렬할 필요가 없습니다. 따라서 merge sort는 배열의 원소가 하나가 될 때까지 쪼개고, 쪼개진 그 배열을 정렬하면서 합병하는 알고리즘이라 볼 수 있겠습니다. 그러면 한 번 코드로 작성해보겠습니다...

1. Binary Search의 알고리즘 및 코드 분할 정복의 기본은 재귀이기 때문에 반복문이 아닌 재귀를 통해서 binary search를 하겠습니다. 반복문을 통한 binary search는 앞 글을 참고해주세요. Problem : 원소가 n개인 (오름차순)정렬된 리스트 S안에 검색하려는 수 x가 있는가? input : 양의 정수 n, 정렬된 리스트 S, 검색키 x output : x의 위치, 만약 없다면 -1를 반환 알고리즘 구상) 1) x와 S의 중간 값과 비교해 같다면 그대로 끝 2) 만약 다르다면 두 가지 방법을 이용한다. 2.1) x가 S의 중간 값보다 작다면 중간 위치를 기준으로 왼쪽 리스트를 탐색한다. 2.2) x가 S의 중간 값보다 크다면 중간 위치를 기준으로 오른쪽 리스트를 탐색한다...

1. 분할 정복이란? 분할 정복은 이름에서 볼 수 있듯이 말 그대로 분할 정복입니다. 분할 정복의 접근법) 1. divides an instance of a problem into two or more smaller instances. 2. if they are too large to be sorved, they can be divided into still smaller instances 3. if solutions to them can be obtained readily, these smaller solutions can be combined into original solution 즉, 문제를 두 개 이상의 instance로 쪼갠다. 그래도 instance가 여전히 크면 또 쪼갠다. 만약 분할한 i..

앞 글들에서 피보나치 수열의 문제를 풀어봤었습니다. 1. 재귀를 이용한 피보나치 수열 이렇게 재귀를 이용해서 풀면 너무 많은 중복 계산이 일어나서 성능이 안 좋습니다. 따라서 이미 해결한 문제는 메모리에 저장해서 나중에 필요할 때 뽑아서 쓰기로 했었습니다. 2. 반복문을 이용한 피보나치 수열 반복문을 이용하여 재귀를 쓰지 않고, 이미 계산한 값에 대해서 리스트에 저장했습니다. 이를 메모이제이션 기법이라고 합니다. 아래는 1번과 2번의 코드입니다. n = int(input()) def fib1(n): if n 0.004057884216308594# 2번 >>> 0.0016162395477294922# 3번 두 배보다 더 빠른 시간 차이가 나네요 참고로 1번에 10,000을 넣으면 아마 평생 걸려도 못 찾으..