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++..

백준 온라인 저지(BOJ) 2443번 문제https://www.acmicpc.net/problem/2443 1. 문제 요약첫째 줄에 별 2*N-1개, 둘째 줄에 별 2*N-3개, ... N번째 줄에 별 1개 찍기2442번과 마찬가지로 별은 가운데를 기준으로 대칭이어야 하며, 별 뒤에는 공백이 없어야 하는듯? 2. 알고리즘for문 안의 수들의 살짝 복잡한데, 더 간단하게 쓰는 법이 있겠지만 일단 빨리 푸느라 대충 씀. 3. 코드 #include using namespace std; int main() { int N; scanf("%d", &N); for (int i = 0; i < N; i++) { for (int j = 0; j < i; j++) printf(" "); for (int j = 0; j <..

백준 온라인 저지(BOJ) 2442번 문제 https://www.acmicpc.net/problem/2442 1. 문제 요약 첫째 줄에 별 1개, 둘째 줄에 별 3개, ... N번째 줄에 별 2*N-1개 찍기 별은 가운데를 기준으로 대칭이어야 하며, 별 뒤에는 공백이 없어야 하는듯? 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 ..

백준 온라인 저지(BOJ) 2441번 문제 https://www.acmicpc.net/problem/2441 1. 문제 요약 첫째 줄에 별 N개, 둘째 줄에 별 N-1개, ... N번째 줄에 별 1개 찍기 (오른쪽 정렬로) 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 < i; j++) printf(" "); for (int j = 0; j < N - i; j++) printf("*"); printf("\n"); } return 0; }

백준 온라인 저지(BOJ) 2440번 문제 https://www.acmicpc.net/problem/2440 1. 문제 요약 첫째 줄에 별 N개, 둘째 줄에 별 N-1개, ... N번째 줄에 별 1개 찍기 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 ; j++) printf("*"); printf("\n"); } return 0; }

백준 온라인 저지(BOJ) 2439번 문제 https://www.acmicpc.net/problem/2439 1. 문제 요약 첫째 줄에 별 1개, 둘째 줄에 별 2개, ... N번째 줄에 별 N개 찍기 (오른쪽 정렬로) 2. 알고리즘 빈 공간에 개수에 맞추어 공백을 삽입하자. 3. 코드 #include using namespace std; int main() { int N; scanf("%d", &N); for (int i = 1; i

백준 온라인 저지(BOJ) 1076번 문제https://www.acmicpc.net/problem/1076 1. 문제 요약10종류의 색깔마다 값, 곱이 정해져있다.3개의 색깔을 보고 저항의 값을 출력해야 하는데,첫 번째 색은 십의 자리, 두 번째는 일의 자리, 세 번째는 곱을 나타낸다. 2. 알고리즘글자를 읽어 비교해야 하므로, string이나 cstring을 사용하면 편리하다.C++이므로 string을 사용하도록 하자.읽은 값을 길이 3짜리 배열에 저장하고, 값을 계산해서 출력한다.가장 큰 경우는 white, white, white인 경우인데 이 경우 값이 990억이므로 int 대신 long long을 사용하면 수월하다. 3. 코드 #include #include using namespace std; ..

백준 온라인 저지(BOJ) 1075번 문제https://www.acmicpc.net/problem/1075 1. 문제 요약두 수 N과 F가 주어진다.N의 앞 두자리는 그대로 두고, 뒷 두자리를 바꾸어 N이 F로 나누어 떨어지게 만들자. 답이 여러 개이면 N을 가장 작게 하자.(100 > F; N /= 100; N *= 100; while (N % F != 0) N++; N %= 100; if (N < 10) cout