#include <stdio.h>
int main(void)
{
int i = 0;
int j = 0;
scanf("%d %d", &i, &j);
printf("%d", i-j);
return 0;
}| [백준] 1008번 A/B (C++) (0) | 2022.03.11 |
|---|---|
| [백준] 1003번 피보나치 함수 (파이썬) (0) | 2022.03.11 |
| [백준] 1000번 A+B (C++/파이썬) (0) | 2022.03.11 |
| [백준] 1010번 다리 놓기 (파이썬) (0) | 2022.03.08 |
| [백준 알고리즘] 1913번 달팽이 (C++) (0) | 2021.11.09 |
#include <stdio.h>
int main(void)
{
int i = 0;
int j = 0;
scanf("%d %d", &i, &j);
printf("%d", i+j);
return 0;
}
A, B = list(map(int, input().split()))
print (A+B)| [백준] 1003번 피보나치 함수 (파이썬) (0) | 2022.03.11 |
|---|---|
| [백준] 1001번 A-B (C++) (0) | 2022.03.11 |
| [백준] 1010번 다리 놓기 (파이썬) (0) | 2022.03.08 |
| [백준 알고리즘] 1913번 달팽이 (C++) (0) | 2021.11.09 |
| [백준 알고리즘] 2908번 상수 (C++) (0) | 2021.11.01 |
이 문제를 해결하는 데는 두 가지 방법이 존재함.
두 문제에 공통적으로 사용되는 요소는 조합.
조합 = 서로 다른 n개 중에 r개를 선택하는 경우의 수 의미.
${}_nC_r = {n! \over (n-r)!r!}$
1. 다이나믹 프로그래밍 적용 X
def factorial(N):
if N > 1:
return (N * factorial(N-1))
else:
return 1
T = int(input())
for _ in range(T):
N, M = list(map(int, input().split()))
print (factorial(M) // (factorial(M-N) * factorial(N)))
2. 다이나믹 프로그래밍 적용 O
T = int(input())
dp = [[0] * 30 for _ in range(30)]
for i in range(30):
for j in range(30):
if i == 1:
dp[i][j] = j
else:
if i == j:
dp[i][j] = 1
elif i < j:
dp[i][j] = dp[i-1][j-1] + dp[i][j-1]
for _ in range(T):
N, M = list(map(int, input().split()))
print (dp[N][M])
| [백준] 1001번 A-B (C++) (0) | 2022.03.11 |
|---|---|
| [백준] 1000번 A+B (C++/파이썬) (0) | 2022.03.11 |
| [백준 알고리즘] 1913번 달팽이 (C++) (0) | 2021.11.09 |
| [백준 알고리즘] 2908번 상수 (C++) (0) | 2021.11.01 |
| [알고리즘] N 계단 오르기 (0) | 2021.10.20 |
문제의 핵심은 홀수인 자연수 N이 주어지면, 1부터 $N^2$까지의 자연수를 아래와 같이 달팽이 모양으로 $N * N$의 표에 채우라는 것이다.
첫째 줄에 홀수인 자연수 N(3 ≤ N ≤ 999)이 주어진다. 둘째 줄에는 위치를 찾고자 하는 N2 이하의 자연수가 하나 주어진다.
N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 출력한다.
알고리즘을 처음 접하는 입장으로써 주위 개발자에게 조언을 구했다. 처음엔 코드를 작성하면서 변수를 생각했다. 하지만 이것은 비효율적인 방법이라고 한다. 머리로 사용할 변수들을 최대한 미리 생각하고 이후에 필요에 따라 추가/제거 하는 것이 중요하다.
1. 먼저 문제에서 바로 확인할 수 있는 변수 두 개인 홀수 자연수를 N으로 두고, 찾아야 할 값을 want로 선언하였다.
2. 찾아야 할 값 want의 2차원 좌표를 나타낼 변수를 x, y로 선언하였다.
3. 2차원 배열을 다루기 위해 사용되는 행렬을 row, col로 선언하였다.
4. 그리고 핵심이 되는 것은 dir(direction)이라는 방향을 나타내는 변수이다.
dir은 위와 같은 흐름으로 2차원 배열 변수에 값을 담기 위한 변수이다. dir을 1 또는 -1로 설정하여 row와 col에 더해줄 것이다. dir을 1로 설정하여 row에 더해줄 경우 자연스럽게 row가 증가하고, col에 더해줄 경우 col이 증가한다. 이후 dir을 -1로 설정하면 row가 감소하고, col이 감소한다. 이후 다시 dir을 1로 설정하면 row가 증가하여 최종적으로 1에 도달하는 식이다. (위 그림에 맞대어 row와 col에 dir을 더해주는 것을 시뮬레이션 해볼 것을 권한다. 이것이 문제 풀이의 핵심이다)
#include <iostream>
#include <cstring>
using namespace std;
int main(void)
{
// 1. 변수 선언부
int N = 0; // 입력 받을 홀수 자연수
int want = 0; // N^2 이하의 찾고자 하는 자연수
int x = 0, y = 0 ; // Want의 좌표를 나타낼 x, y 값
int row = -1, col = 0;; // 달팽이를 나타낼 행, 열
int dir = 1; // 방향을 나타낼 변수
cin >> N;
int copy = N;
cin >> want;
int squared = N * N; // N^2을 표현할 변수
int** arr;
arr = new int* [N]; // 2차원 배열의에서 사용할 배열의 길이(row)
for (int i = 0; i < N; i++)
{
arr[i] = new int[N]; // N = 2차원 배열에서 사용할 배열의 길이(column)
memset(arr[i], 0, sizeof(int)*N); // 0으로 배열 초기화 for security.
}
// 2. 핵심 알고리즘 동작부
while (squared > 0)
{
for (int i = 0; i < copy; i++)
{
row = row + dir;
arr[row][col] = squared;
if (squared == want)
{
x = row + 1;
y = col + 1;
}
squared = squared - 1;
}
copy = copy - 1;
for (int i = 0; i < copy; i++)
{
col = col + dir;
arr[row][col] = squared;
if (squared == want)
{
x = row + 1;
y = col + 1;
}
squared = squared - 1;
}
dir = dir * (-1);
}
// 3. 결과 출력부
for (int i = 0; i < N * N; i++)
{
int r = i / N;
int c = i % N;
cout << arr[r][c] << " ";
if ((i % N) == N - 1) cout << endl;
}
cout << x << " " << y << endl;
// 4. 2차원 배열 할당 해제부
for (int i = 0; i < N; i++)
delete[] arr[i];
delete[] arr;
return 0;
}
코드는 크게 4개의 부로 구성된다.
1. 변수 선언부
알고리즘 작성 이전에 필요로 하는 변수를 선언한 부분이다.
2. 핵심 알고리즘 동작부
배열에 값을 넣기 위한 핵심적인 알고리즘이 동작하는 부분이다.
3. 결과 출력부
$N^2$부터 1까지 달팽이 모양으로 출력하는 부분이다.
4. 2차원 배열 할당 해제부
달팽이 모양으로 값을 담기 위해 생성했던 2차원 동적 배열을 할당 해제하는 부분이다.
참고로 memset 함수는 0, -1로만 초기화 가능하다. 그 이유는 바이트 단위로 초기화가 이루어지기 때문이다.
초반에 알고리즘 풀지 못했을 때 정답 비율이 50%나 된다는 것에 가벼운 충격을 받았다. 최소한 둘에 하나는 풀 수 있다는 생각에 말이다. 아무튼 동시에 초심자로서 알고리즘적 사고를 잘 하는 사람들이 많다는 것에 내게 자극을 심어준 문제였다.
Reference
| [백준] 1000번 A+B (C++/파이썬) (0) | 2022.03.11 |
|---|---|
| [백준] 1010번 다리 놓기 (파이썬) (0) | 2022.03.08 |
| [백준 알고리즘] 2908번 상수 (C++) (0) | 2021.11.01 |
| [알고리즘] N 계단 오르기 (0) | 2021.10.20 |
| 알고리즘 시험 정리 (0) | 2020.03.04 |
알고리즘 그룹을 만드려고 하니 50문제를 풀어야만 만들 수 있다고 한다. 하필 49문제였다. 급하게 쉬운 문제 찾아본다고 풀어본 것이다.
상수는 수를 다른 사람과 다르게 거꾸로 읽는다. 예를 들어, 734와 893을 칠판에 적었다면, 상수는 이 수를 437과 398로 읽는다. 따라서, 상수는 두 수중 큰 수인 437을 큰 수라고 말할 것이다. 두 수가 주어졌을 때, 상수의 대답을 출력하는 프로그램을 작성하시오.
예시 입력
734 893
예시 출력
437
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(void)
{
string a, b;
cin >> a >> b;
if (a.size() == 3 and b.size() == 3)
{
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
if (a > b)
cout << a;
else
cout << b;
}
return 0;
}숫자를 int 형으로 받지 않고 string으로 받았다. 문자의 길이를 확인할 수 있는 size() 함수를 사용하기 위해서.
이후 문자열을 뒤집는 reverse 함수를 사용하여 문자열을 플립하였다. reverse 함수는 #include <alogrithm>를 선언하여 사용할 수 있다.
특이사항은 숫자 비교를 위해서 int 형으로 바꾸어야 할 것이라 생각했는데 그러지 않아도 동작함.
| [백준] 1010번 다리 놓기 (파이썬) (0) | 2022.03.08 |
|---|---|
| [백준 알고리즘] 1913번 달팽이 (C++) (0) | 2021.11.09 |
| [알고리즘] N 계단 오르기 (0) | 2021.10.20 |
| 알고리즘 시험 정리 (0) | 2020.03.04 |
| 쉬트라센 알고리즘 (Strassen Algorithm) (0) | 2020.03.04 |
100개의 계단이 있으며 나는 한 번에 10개의 계단을 오를 수 있는 능력을 가지고 있다.
이 때, 100개의 계단을 올라갈 수 있는 경우의 수는 몇 개인가?
문제를 보고 생각할 수 있는 가장 초기의 코드를 작성한 것이다.
stairs = 100
skill = 10
table = [0 for i in range(stairs+1)]
table[0] = 1
for i in range(1, stairs+1):
s=0
for j in range(1,skill+1):
if i-j<0:
t=0
else:
t= table[i-j]
s = s+t
table[i] = s
print (table[stairs])
2. 초기 코드를 확인 후 줄일 수 있는 부분을 확인 후, 파이썬의 강점을 살려 개선 코드를 작성한 것이다
stairs = 100
skill = 10
table = [0 for i in range(stairs+1)]
table[0] = 1
for i in range(1, stairs+1):
s=0
for j in range(1,skill+1):
t=(table[i-j],0)[i-j<0]
s = s+t
table[i] = s
print (table[stairs])
3. 개선 코드를 작성 후 하나의 함수로 만듦으로써 n 계단 오르기를 구현한 것이다.
def climbing(staris, skill):
table = [0 for i in range(stairs + 1)]
table[0] = 1
for i in range(1, stairs+1):
s=0
for j in range(1,skill+1):
t=(table[i-j],0)[i-j<0]
s = s+t
table[i] = s
return table[stairs]
r = (climbing(100,10))
print (r)
4. 함수의 최적화와 코드의 최적화를 구현한 것이며 아래의 코드는 계단 오르기 문제에 있어 가장 최적화 된 코드이다.
def climbing(n,m):
table=[0 for i in range(n+1)]
table[0]=1
for i in range(1,n+1):
s=(i-m,0)[(i-m)<0]
table[i]=sum(table[s:i])
return table[n]
a=climbing(100,10)
print (a)| [백준 알고리즘] 1913번 달팽이 (C++) (0) | 2021.11.09 |
|---|---|
| [백준 알고리즘] 2908번 상수 (C++) (0) | 2021.11.01 |
| 알고리즘 시험 정리 (0) | 2020.03.04 |
| 쉬트라센 알고리즘 (Strassen Algorithm) (0) | 2020.03.04 |
| 분할정복법과 동적프로그래밍 (0) | 2020.03.04 |
모든 $n$, $n \geq n_0$에 대해 $f(n) \le c\times g(n)$인 조건을 만족시키는 두 양의 상수 $c$와 $n_0$가 존재하기만 하면 $f(n)=O(g(n))$이다.
예를 들면 $O(n)$: 최악의 경우 $n$번까지 수행되면 프로그램을 끝낼 수 있다.
모든 $n$, $n \geq n_0$에 대해 $f(n) \geq c\times g(n)$인 조건을 만족시키는 두 양의 상수 $c$와 $n_0$가 존재하기만 하면 $f(n)=\Omega(g(n))$이다.
예를 들면 $O(n)$: 최소 $n$번은 수행되어야 프로그램을 끝낼 수 있다.
모든 $n$, $n \geq n_0$에 대해 $c_1\times g(n) \le f(n) \le c_2\times g(n)$인 조건을 만족시키는 세 양의 상수 $c_1, c_2, n_0$가 존재하기만 하면 $f(n)=\theta(g(n))$이다.
Theta의 경우 $O와\ \Omega$의 교집합이다. 즉, 차수가 같은 문제이다.
모든 $n$, $n \geq n_0$에 대해 $0 \leq f(n) \lt c \times g(n)$인 조건을 만족시키는 두 양의 상수 $c, n_0$가 존재하기만 하면 $f(n)=O(g(n))$이다.
예를 들면 $O(n)$: 최악의 경우에도 n번 미만으로 수행되면 프로그램은 끝낼 수 있다.
$\lim_{x \to \infty}$ $f(x)\over g(x)$ $=0$로 나타낼 수 있다.
Small-O와 Big-O의 차이점은 다음과 같다.
- Big-O는 실수 $c>0$ 중에서 하나만 성립해도 된다.
- Small-O는 모든 실수 $c>0$에 대해서 성립해야 한다.
- Small-O는 Big-O에서 등호를 뺀다.
추가적으로 Small-omega($\omega$)도 존재한다.
모든 $n, n \geq n_0$에 대하여 $f(n) \leq c \times g(n)$인 조건을 만족시키는 두 양의 상수 $c$와 $n_0$가 존재하기만하면 $f(n) = O(g(n))$이다.
1. $f(n) = 8n^2 + \sqrt2$
2. $g(n) = n^2$
3. 대입 => $8n^2 + \sqrt2 \leq c \times n^2$
4. $\sqrt2$는 약 1.414
5. $8n^2 + 1.414 \leq c \times n^2$
6. n = 2라 가정하면
7. $32 + 1.414 \leq c \times 4$
8. $33.414 \leq c \times 4$
9. $c \geq 9$
1. $g(x) = x^3$
2. $g_2(x) = 6x^3$
3. $x^3 \leq 5x^3+4x^2+6x \leq 6x^3$
분할정복법과 동적 프로그래밍의 공통점과 차이점
bottom-up 방식
int binomial(int n, int k)
{
for (int i=0; i<=n; i++)
{
for (int j=0; j<=k && j<=i; j++)
{
if (k==0 || n==k)
arr[i][j] = 1;
else
arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
}
}
return arr[n][k];
}
아래와 같이 행렬 A,B가 있고 두 행렬의 곱이 행렬 C로 표현한다 가정한다.
$A = \left[ \begin{array}{cc|c} a_{11} & a_{12} \\\\ a_{21} & a_{22} \end{array} \right],\ $ $B= \left[ \begin{array}{cc|c} b_{11} & b_{12} \\\\ b_{21} & b_{22} \end{array} \right],\ $ $C=\left[ \begin{array}{cc|c} c_{11} & c_{12} \\\\ c_{21} & c_{22} \end{array} \right]$
이 때, $A_{ij},B_{ij},C_{ij} \in F^{2^n-1 \times 2^n-1}$ 이다.
따라서 일반적인 행렬의 곱은 다음과 같이 표현할 수 있으며, 총 8번의 곱셈과 4번의 덧셈으로 연산된다.
$C_{11} = A_{11}B_{11} + A_{12}B_{21}$
$C_{12} = A_{11}B_{12} + A_{12}B_{22}$
$C_{21} = A_{21}B_{11} + A_{22}B_{21}$
$C_{22} = A_{21}B_{12} + A_{22}B_{22}$
슈트라센 알고리즘은 행렬의 곱셉을 더하기 연산으로 풀어 각 원소를 구할 수 있는 $M$이라는 연산 행렬로 표현한다. 행렬 $M$은 7번의 곱셈과 10번의 덧셈으로 연산으로 나타낼 수 있으며 아래와 같이 표현한다.
$M_1 = (A_{11} + A_{22})(B_{11}+B_{22})$
$M_2 = (A_{21} + A_{22})B_{11}$
$M_3 = A_{11} (B_{12}-B_{22})$
$M_4 = A_{22}(B_{21}-B_{11})$
$M_5 = (A_{11} + A_{12})B_{22}$
$M_6 = (A_{21} - A_{11})(B_{11}+B_{12})$
$M_7 = (A_{12} - A_{22})(B_{21}+B_{22})$
최종적으로 행렬 C는 행렬 M의 더하기 연산으로 이루어져 있으며 각 원소에 해당하는 방법은 다음과 같다.
$C_{11} = M_1 + M_4 - M_5 + M_7$
$C_{12} = M_3 + M_5$
$C_{21} = M_2 + M_4$
$C_{22} = M_1 - M_2 + M_3 + M_6$
#include <stdio.h>
void HanoiTowerMove(int num, char from, char by, char to)
{
if (num == 1)
printf("원반 1을 %c에서 %c로 이동 \n", from, to);
else
{
HanoiTowerMove(num - 1, from, to, by);
printf("원반 %d를 %c에서 %c로 이동 \n", num, from, to);
HanoiTowerMove(num - 1, by, from, to);
}
}
int main(void)
{
// 막대 A의 원반 5개를 막대 B를 경유하여 막대 C로 옮기기
HanoiTowerMove(5, 'A', 'B', 'C');
return 0;
}
Greedy Algorithm이 사용되는 대표적인 예제로는 "최소 수의 동전으로 거스름돈 거슬러주기" 문제가 있다.
만약 우리가 마트의 캐셔로 일을 하고 있고, 850원을 거슬러 주어야 할 때 500원 동전 1개와 100원 동전 3개와 50원 동전 1개 총 4개의 동전을 건넴으로써 최소한의 동전을 거슬러 줄 수 있다. 하지만 이렇게 하지 않고 10원짜리 동전 85개를 건네주거나 50원짜리 17개를 건네주는 방법과 같이 다양한 경우의 수가 존재하며 이와 같을 경우 반드시 최적의 해를 내는 것은 아니다.
또한 우리나라의 경우 총 4개의 동전 500원, 100원, 50원, 10원이 있다. 하지만 만약 400원 동전이 발행된다면 400원 동전 2개, 50원 동전 1개를 통해 총 3개의 동전을 거슬러 줄 수 있을 것이다. 가장 최적의 방법이지만, 기존 알고리즘에 따르면 500원 1개, 100원 3개, 50원 1개로 거슬러주게 될 것이다. 이와 같이 탐욕 알고리즘은 항상 최적의 결과를 보장하지 못한다.
[1] https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html
[2] https://janghw.tistory.com/entry/알고리즘-Greedy-Algorithm-탐욕-알고리즘
| [백준 알고리즘] 2908번 상수 (C++) (0) | 2021.11.01 |
|---|---|
| [알고리즘] N 계단 오르기 (0) | 2021.10.20 |
| 쉬트라센 알고리즘 (Strassen Algorithm) (0) | 2020.03.04 |
| 분할정복법과 동적프로그래밍 (0) | 2020.03.04 |
| 정렬 알고리즘의 장단점과 시간 복잡도 및 공간 복잡도 (2) | 2020.03.04 |
1960년대 후반 Strassen이 $O(n^3)$보다 작은 알고리즘을 제시하며 아래와 같은 규칙을 사용한다.
$P = (A_{11} + A_{22})(B_{11} + B_{22})$
$Q = (A_{21} + A_{22})B_{11}$
$R = A_{11}(B_{12}-B_{22})$
$S = A_{22}(B_{21}-B_{11})$
$T = (A_{11}+A_{12})B_{22}$
$U = (A_{21}-A_{11})(B_{11}+B_{12})$
$V = (A_{12}-A_{22})(B_{21}+B_{22})$
위의 규칙에서 사용되는 P~V까지를 통해, 덧셈만으로 A 행렬과 B 행렬의 곱인 C 행렬을 찾을 수 있다.
$C_{11} = P + S - T + V$
$C_{12} = R + T$
$C_{21} = Q + S$
$C_{22} = P + R -Q +U$
구체적으로 다시 설명을 하면 다음과 같다.
아래와 같이 행렬 A,B가 있고 두 행렬의 곱이 행렬 C로 표현한다 가정한다.
$A = \left[ \begin{array}{cc|c} a_{11} & a_{12} \\\\ a_{21} & a_{22} \end{array} \right],\ $ $B= \left[ \begin{array}{cc|c} b_{11} & b_{12} \\\\ b_{21} & b_{22} \end{array} \right],\ $ $C=\left[ \begin{array}{cc|c} c_{11} & c_{12} \\\\ c_{21} & c_{22} \end{array} \right]$
이 때, $A_{ij},B_{ij},C_{ij} \in F^{2^n-1 \times 2^n-1}$ 이다.
따라서 일반적인 행렬의 곱은 다음과 같이 표현할 수 있으며, 총 8번의 곱셈과 4번의 덧셈으로 연산된다.
$C_{11} = A_{11}B_{11} + A_{12}B_{21}$
$C_{12} = A_{11}B_{12} + A_{12}B_{22}$
$C_{21} = A_{21}B_{11} + A_{22}B_{21}$
$C_{22} = A_{21}B_{12} + A_{22}B_{22}$
슈트라센 알고리즘은 행렬의 곱셉을 더하기 연산으로 풀어 각 원소를 구할 수 있는 $M$이라는 연산 행렬로 표현한다. 행렬 $M$은 7번의 곱셈과 10번의 덧셈으로 연산으로 나타낼 수 있으며 아래와 같이 표현한다.
$M_1 = (A_{11} + A_{22})(B_{11}+B_{22})$
$M_2 = (A_{21} + A_{22})B_{11}$
$M_3 = A_{11} (B_{12}-B_{22})$
$M_4 = A_{22}(B_{21}-B_{11})$
$M_5 = (A_{11} + A_{12})B_{22}$
$M_6 = (A_{21} - A_{11})(B_{11}+B_{12})$
$M_7 = (A_{12} - A_{22})(B_{21}+B_{22})$
최종적으로 행렬 C는 행렬 M의 더하기 연산으로 이루어져 있으며 각 원소에 해당하는 방법은 다음과 같다.
$C_{11} = M_1 + M_4 - M_5 + M_7$
$C_{12} = M_3 + M_5$
$C_{21} = M_2 + M_4$
$C_{22} = M_1 - M_2 + M_3 + M_6$
[1] https://loveisaround.tistory.com/entry/알고리즘-스트라센-strassen
[2] https://09ri.tistory.com/30
| [알고리즘] N 계단 오르기 (0) | 2021.10.20 |
|---|---|
| 알고리즘 시험 정리 (0) | 2020.03.04 |
| 분할정복법과 동적프로그래밍 (0) | 2020.03.04 |
| 정렬 알고리즘의 장단점과 시간 복잡도 및 공간 복잡도 (2) | 2020.03.04 |
| P NP 문제 (0) | 2020.03.04 |
이항계수는 분할 정복과 동적 프로그래밍에서 차이점을 서술하기 위해 자주 사용된다.
또한 이항계수란 $n$개의 원소에서 $r$개의 원소를 선택하는 방법의 수를 나타내며 재귀 프로그래밍의 기초가 된다.
이항계수는 수학에서 $_nC_r$로 나타낼 수 있으며, 이항계수 프로그래밍의 해결 방법은 $_nC_r =\ _{n-1}C_{r-1}\ +\ _{n-1}C_r$의 공식으로 이루어진다.
위 공식을 재귀적으로 구현할 경우 다음과 같다.
int binomial(int n, int k) {
if (n == k || k == 0)
return 1;
else
return binomial(n - 1, k) + binomial(n - 1, k - 1);
}
만약 binomical(5,2)를 계산하면 아래와 같이 동일한 문제들을 중복으로 풀게되어, 부분문제의 중복 문제가 발생한다. 즉, 알고리즘의 효율이 떨어지게 된다.
위와 같이 중복 계산으로 인해 효율이 떨어지는 것을 보완하기 위해서는, 하위 문제를 이용하여 최종 결과의 해를 도출하는 동적 프로그래밍 방법으로 접근하여 해결할 수 있다. 이전 계산 결과 값을 메모이제이션을 이용하여 풀면 다음과 같이 작성할 수 있다.
int binomial(int n, int k) {
if (n == k || k == 0)
return 1;
else if (arr[n][k] > -1) /* 배열 arr이 -1로 초기화되어 있다고 가정 */
return arr[n][k];
else {
arr[n][k] = binomial(n-1, k) + binomial(n-1, k-1);
return arr[n][k];
}
}* 메모이제이션(Memoization) : 이차원 배열에 인덱스에 해당하는 중복 조합을 저장 후, 만약 해당 인덱스에 값이 존재할경우(캐싱되었을 경우) 앞서 계산했다고 판단하여 해당 값을 반환함으로써 중복 계산을 줄여주는 기술. 즉, 동일 계산의 반복 수행을 제거한다.
Bottom-up 방식으로 해결할 경우 다음과 같이 작성할 수 있다.
int binomial(int n, int k) {
for (int i=0; i<=n; i++) {
for (int j=0; j<=k && j<=i; j++) {
if (k==0 || n==k)
arr[i][j] = 1;
else
arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
}
}
return arr[n][k];
}
[1] https://makefortune2.tistory.com/109
[2] https://kimch3617.tistory.com/entry/알고리즘-분할정복법-Divide-and-Conquer
[3] https://jackpot53.tistory.com/130
[4] https://shoark7.github.io/programming/algorithm/3-ways-to-get-binomial-coefficients
[5] https://new93helloworld.tistory.com/91
| 알고리즘 시험 정리 (0) | 2020.03.04 |
|---|---|
| 쉬트라센 알고리즘 (Strassen Algorithm) (0) | 2020.03.04 |
| 정렬 알고리즘의 장단점과 시간 복잡도 및 공간 복잡도 (2) | 2020.03.04 |
| P NP 문제 (0) | 2020.03.04 |
| 최소 비용 신장 트리(Minimum Spanning Tree) (0) | 2020.03.04 |
| Sorting Algorithm | 공간 복잡도 | 시간 복잡도 | |||
| 최선 | 최악 | 최선 | 평균 | 최악 | |
| Bubble Sort | $O(1)$ | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ |
| Heap Sort | $O(1)$ | $O(n\times log\ n)$ | $O(N\times log\ n)$ | $O(n\times log\ n)$ | $O(n\times log\ n)$ |
| Insertion Sort | $O(1)$ | $O(n)$ | $O(n)$ | $O(n^2)$ | $O(n^2)$ |
| Merge Sort | $O(1)$ | $O(n\times log\ n)$ | $O(n\times log\ n)$ | $O(n\times log\ n)$ | $O(n\times log\ n)$ |
| Quick Sort | $O(log \ n)$ | $O(n\times log\ n)$ | $O(n\times log\ n)$ | $O(n\times log\ n)$ | $O(n^2)$ |
| Selection Sort | $O(1)$ | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ |
| Shell Sort | $O(1)$ | $O(n)$ | |||
| Sorting | 장점 | 단점 |
| 버블 정렬 | 인접한 두 개의 데이터를 비교하기에 구현이 쉬우며 정밀 비교 가능 | 원소의 갯수가 많아지면 비교 연산이 많아져서 성능이 저하 |
| 선택 정렬 | 정렬을 위한 교환 횟수가 적어 내림차순된 데이터를 오름차순할 때 효율이 좋음 | 정렬 비교 횟수가 많고, 정렬된 상태서 소수의 자료가 추가되면 재정렬 시 최악의 처리 속도를 보임 |
| 삽입 정렬 | 버블정렬의 비교횟수를 줄이기 위해 고안된 방법이며, 크기가 적은 데이터 집합을 정렬하는 알고리즘을 작성할 때 효율이 좋음 | 데이터의 상태와 크기에 따라 성능 편차가 큰 정렬 방법 |
| 힙 정렬 | 추가적인 메모리를 필요로하지 않으면서 항상 시간 복잡도 $O(N\times logN)$ 를 가짐 | 실제 시간을 측정 시 퀵정렬보다 느림. 즉, 데이터의 상태에 따라서 다른 정렬들에 비해 느린편. 안정성을 보장받지 못함 |
| 병합 정렬 | 퀵 정렬과 달리 기준값을 설정하는 과정없이 무조건 절반으로 분할하기에 기준값에 따라 성능이 달라지는 경우가 없음 | 병합정렬은 임시배열에 원본맵을 계속해서 옮겨주며 정렬을 하는 방식이기에 추가적인 메모리가 필요 |
| 퀵 정렬 | 기준값(Pivot)에 의한 분할을 통해 구현하는 정렬 방법으로, 분할 과정에서 $logN$이라는 시간이 소요되며, 전체적으로 $N\times logN$으로 준수 | 최악의 기준값을 선택할 경우 $O(N^2)$라는 시간복잡도를 가짐 |
| 기수 정렬 | $O(N)$이라는 시간복잡도를 가지는 정렬방법으로 매우 빠른 속도를 가짐 | 버킷이라는 데이터 전체 크기와 기수 테이블의 크기만큼의 추가적인 메모리가 할당돼야 함 |
[1] https://tctt.tistory.com/47
[2] https://yabmoons.tistory.com/250
[3] https://hsp1116.tistory.com/33
[4] https://yaraba.tistory.com/79
| 쉬트라센 알고리즘 (Strassen Algorithm) (0) | 2020.03.04 |
|---|---|
| 분할정복법과 동적프로그래밍 (0) | 2020.03.04 |
| P NP 문제 (0) | 2020.03.04 |
| 최소 비용 신장 트리(Minimum Spanning Tree) (0) | 2020.03.04 |
| 시간 복잡도 정리 (0) | 2020.03.04 |