안녕

문제)

다들 이항 계수 아시죠? \(\binom{n}{k} = \frac{n!}{k!(n-k)!}\)입니다. 이때 n!를 계산하기 매우 힘드므로, 재귀 관계식을 이용하여 다음과 같이 정리할 수 있습니다. \(\binom{n}{k}=\left\{\begin{matrix} \binom{n-1}{k-1}+\binom{n-1}{k} & 0

1. 동적 계획법이란? DP (Dynamic Programming)는 코딩 테스트의 절반 이상을 차지하는 알고리즘이라 봐도 무방합니다. DP는 분할 정복과 매우 유사합니다. 하지만 분할 정복은 top-down 방식을 이용하고, DP는 bottom-up 방식을 이용합니다. 가장 작은 instance의 답을 먼저 구하여 저장하고, 필요하면 꺼내 쓰는 '동적 계획'입니다. 여기서 계획이란 문제 해결을 위한 배열(테이블)을 구축한다는 뜻입니다. DP 알고리즘의 개발 절차는 다음과 같습니다. 문제의 instance의 해답을 구하는 재귀 관계식을 세운다. (top-down approach, Divide and Conquer 방식) 작은 instance부터 해결하는 bottom-up 방법으로 전체 instance에 ..

Description 우리 교재의 Chapter 2, Exercise 42번 (p. 94)을 풀어보자.이 문제는 분할정복의 대표적인 문제로, 트로미노 타일링 문제로 널리 알려져있다.단, 이 실습과제에서 트로미노 타일의 번호는 트로미노를 놓는 순서로 정한다.예를 들어, 다음과 같은 트로미노 퍼즐은 아래와 같은 순서로 트로미노를 놓는다. Input 첫 번째 줄에 n, row, col이 주어진다.n은 n*n 트로미노 퍼즐 보드의 크기이다. (2의 거듭제곱 수라고 가정해도 된다.)row, col은 구멍의 행과 열이다. 0 <= row, col <= (n - 1) Output 트로미노를 놓는 순서대로 타일에 번호를 부여한 보드를 출력한다.구멍 타일의 번호는 0으로 한다. Sample Input 1..

가능하다면 다음 두 가지 경우에 대해서는 분할 정복을 피해야 합니다. instance of size N is divide into two or more instances each almost size n. 크기가 n인 사례가 거의 n에 가까운 두 개 이상의 사례로 분할될 때 이렇게 분할하면 지수 시간 알고리즘이 나옵니다. instance of size N is divied into almost n instances of size n/c, where c is a constant 4개로 쪼갰는데, 다시 4번의 재귀할 때, 혹은 2개로 쪼갰는데, 2번 재귀할 때 이렇게 분할하면 \(n^{\Theta(nlgn)}\)의 알고리즘이 나옵니다. 만약 피보나치수열을 재귀적인 방법 즉, 분할 정복을 이용해서 문제를 해결..

만약에 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..