목록분류 전체보기 (296)
The Way
백준 온라인 저지(BOJ) 13623번 문제https://www.acmicpc.net/problem/13623 1. 문제 요약A, B, C 3명이서 0 아님 1을 말하는데, 혼자만 다른 숫자를 말할 때 이긴다이긴 사람을 출력, 이긴 사람이 없으면 * 출력 2. 알고리즘if문이 가장 빠른 듯 3. 코드 #include using namespace std; int main() { int a, b, c; cin >> a >> b >> c; if (a == 1 && b == 0 && c == 0) printf("A\n"); else if (a == 0 && b == 1 && c == 1) printf("A\n"); else if (a == 0 && b == 1 && c == 0) printf("B\n"); el..
백준 온라인 저지(BOJ) 9664번 문제https://www.acmicpc.net/problem/9664 1. 문제 요약재산(금메달)을 N명의 딸들이 분배막내 딸이 최대 1 차이가 나도록 나눈 뒤 그 중 적은 것을 가져가는데(예를 들어서 14개였고 3명이면 5/5/4로 나누고 4를 가져감)가져간 이후 남은 개수를 보고 가능한 원래 개수의 최댓값/최솟값을 맞추기 (cunning daughter인데 왜 적은 거를 가져가는지 잘 모르겠다.. cunning의 뜻은 '교활한'인데..) 2. 알고리즘원래 개수는 하나로 결정되거나 1 차이가 나게 된다남은게 똑같이 분배되지 않을 경우 (ex 5/5/4)으로 남았으면 적은 것을 가져갔으므로 작은 값을 더해준게 원래 값남은게 똑같이 분배될 경우 (ex 5/5/5) 막내..
백준 온라인 저지(BOJ) 4881번 문제https://www.acmicpc.net/problem/4881 1. 문제 요약각 자리수를 제곱하여 더하여 만들어지는 수열이 있다.초기 숫자 두 개가 주어질 때, 같은 숫자가 나올 때까지의 수열의 길이의 합이 가장 작을 때 그 합은 얼마인가? 2. 알고리즘문제에서 두 개의 사이클이 소개되었다.하나는 89, 145, 42, 20, 4, 16, 37, 58이고 하나는 1이다.따로 계산을 해보면 알겠지만 이 두 개의 사이클이 유일한 사이클이다. 따라서 수열이 저 사이클에 포함될 때 까지 계산해준 뒤,서로 다른 사이클이면 불가능같은 사이클일 경우, 첫 도착지점이 같으면 공통 부분을 소거해주고첫 도착지점이 다를 경우 (ex 89, 37처럼 될 경우) 짧은 방향으로 사이클..
백준 온라인 저지(BOJ) 2606번 문제https://www.acmicpc.net/problem/2606 1. 문제 요약컴퓨터 간 연결 정보들이 주어질 때,1번 컴퓨터를 통해 바이러스에 감염되는 컴퓨터의 수를 구하기 2. 알고리즘간단한 형태의 탐색 문제이다.마지막에 합을 더해줄 때 1번 컴퓨터는 제외하고 더해줘야 한다는 점에 주의.여러 효율적인 방법이 있겠지만... 역시 속도가 생명.. 3. 코드 #include #include #include using namespace std; int main() { vector connect[100]; int inf[100] = { 0 }; int N, M; scanf("%d %d", &N, &M); int t1, t2; for (int i = 0; i < M; ..
백준 온라인 저지(BOJ) 2178번 문제https://www.acmicpc.net/problem/2178 1. 문제 요약미로의 첫 블럭에서 지정된 블럭까지 가는 데 최소 소요 칸 수 구하기 2. 알고리즘가장 기본적인 BFS 문제이다.최종 구하려는 블럭의 depth값을 출력하면 된다.큐에 저장해줄 때는 i * 100 + j의 값을 사용하였다. 3. 코드 #include #include int main() { char maze[100][100]; int depth[100][100]; int N, M; scanf("%d %d", &N, &M); for (int i = 0; i < N; ++i) scanf("%s", maze[i]); int d = 1; maze[0][0] = '0'; depth[0][0] =..
백준 온라인 저지(BOJ) 11722번 문제https://www.acmicpc.net/problem/11722 1. 문제 요약수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열의 길이를 구하기. 2. 알고리즘다이나믹 프로그래밍을 사용하여 $O(n^2)$의 시간에 구하는 방법은 생각해보았다. 감소하는 부분 수열이 예를 들어서 {30, 20, 10}일 때, 이는 30 + {20, 10}이라서 길이가 2 + 1이 된 것이라 생각하자.맨 뒤는 길이 1로 저장하고,그 이후는 그 성분을 포함시켰을 때 감소하는 수열이 되는 값들의 길이를 훑고, 그 최댓값에 1을 더한 뒤 저장하면 되겠다.말로 설명하기 약간 어려워서 보충 {10, 30, 10, 20, 20, 10} 1 2 1 (20보다 작은 값 10) 2 2 1 (..
백준 온라인 저지(BOJ) 11399번 문제https://www.acmicpc.net/problem/11399 1. 문제 요약ATM 1대와 그를 이용하려는 N명의 사람이 있다.사람들 각각의 사용시간이 주어질 때, ATM을 이용하는 순서에 따라 소요시간의 합이 달라지게 된다.소요시간의 합의 최솟값을 구하여라. 2. 알고리즘만약 3명이라고 치자.처음 사용하는 사람은 a분, 두번째는 b분, 세번째는 c분 소요된다고 했을 때총 소요시간은 $(a) + (a+b) + (a+b+c) = 3a + 2b + c$이다.앞의 상수 3, 2, 1...은 고정이므로 곱해지는 숫자인 a, b, c가 내림차순이어야 최소가 된다. 짜기 귀찮아서 걍 algorithm에 있는 sorting 씀 3. 코드 #include #include..
$f(x) = a_0 + a_1 x + a_2 x^2 + ... + a_n x^n$이라는 다항식이 있을 때, 이 값은 선형 시간에 계산할 수 있다. 간단한 변환을 거치면 쉽게 알아차릴 수 있는데, $f(x) = a_0 + x(a_1 + x(a_2 + ... + x(a_n + 0)))$으로 변환 가능하기 때문이다. 코드는 다음과 같다. 길이 n+1의 배열은 $a_0,\;a_1,\;a_2,...,a_n$이 저장되어있는 배열이라고 하자 int poly(int x, int* arr, int n) { // n은 배열의 길이 (최고차항+1) int r = 0; for (int i = n; i > 0; --i) { r += arr[i]; r *= x; } r += arr[0]; return r; }
어떠한 알고리즘의 시간 복잡도를 구하기 위해서는 (특히 분할 정복 알고리즘의 경우) 점화식을 풀게 될 때가 많다.가령, 병합 정렬의 알고리즘 복잡도를 구하기 위해서는 다음과 같은 점화식을 풀어야 한다. $$T(n) = \begin{cases}\Theta(1)\;(n=1)\\2T(n/2) + \Theta(n)\;(n>1) \end{cases}$$ 재귀 트리를 작성한다면 직관적으로 복잡도가 $\Theta(n\log n)$임을 알 수 있지만, 마스터 정리를 이용하면 일반적인 경우의 풀이가 쉬워진다. 1. 마스터 정리$T(n) = aT(n/b) + f(n)$형태의 점화식이 있을 때, i) $f(n) = O(n^{\log_b a - \epsilon})$이면 $T(n) = \Theta(n^{\log_b a})$ii..