The Way

1. 개요Big-O 표기법은 보통 시간 복잡도 혹은 공간 복잡도를 나타내기 위해 주로 사용한다.많은 알고리즘들의 성능을 평가할 때 많이 등장하게 될 것인데, 그 중 한 예시로 정렬에서 다음과 같은 것을 접해보았을 것이다. ex) 정렬 알고리즘의 시간복잡도병합 정렬, 힙 정렬: $O(n\log{n})$삽입 정렬, 선택 정렬: $O(n^2)$ 위 표기의 의미는 간단하게 다음과 같이 이해하기 바란다. /*n개의 원소를 정렬할 때,병합 정렬과 힙 정렬을 하는 데에 걸리는 시간은 $n\log{n}$에 비례하여 증가하고,삽입 정렬과 선택 정렬을 하는 데에 걸리는 시간은 $n^2$에 비례하여 증가한다.*/ 2. 복잡도의 순위 & 낮은 복잡도의 중요성보통 점근 표기법을 할 때는 앞에 붙은 계수는 무시하며, 높은 복잡도..

1. 조합 순열과 조합 시간에 배운 것은 다들 기억하고 있을 것이다. 조합은 보통 다음과 같이 기억하고 있을 것이라고 생각한다. $$_n C_k = \frac{n!}{k!(n-k)!}$$ 이 방법이 조합의 수를 가장 빠르게 구해낼 수 있는 방법이다. 하지만 이번에는 조금 다른 재귀적 성질을 이용해보자. 조합에는 위 식 말고도 다른 재귀적 성질이 하나 존재한다. $_n C_0 = 1$, $_n C_n = 1$$_n C_k = _{n-1}C_{k-1} + _{n-1}C_k$ 척 보면 감이 오겠지만, 위 둘은 base case이고 아래는 재귀적 성질이다. 2. 코드 써있는 그대로 작성하면 된다. int c(int n, int k) { if (k == 0 || n == k) return 1; return c(n..

백준 온라인 저지(BOJ) 2444번 문제https://www.acmicpc.net/problem/2444 1. 문제 요약예제와 같이 별을 찍자. 이 때 입력은 5이다. * *** ***** ******* ********* ******* ***** *** * 2. 알고리즘생략 3. 코드 #include using namespace std; int main() { int N; scanf("%d", &N); for (int i = 0; i < N; i++) { for (int j = 0; j < N - i - 1; j++) printf(" "); for (int j = 0; j < 2 * i + 1; j++) printf("*"); printf("\n"); } for (int i = 1; i < N; i++..