The Way

백준 온라인 저지(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..

http://sites.math.rutgers.edu/~ajl213/CLRS/CLRS.html에 누군가가 친절하게 모든 문제와 예제를 풀어놓았다.간혹 틀린 답이 있으니 주의할 것. ex) Problem 3-3에서$n2^n$이 $e^n$보다 증가속도가 빠르다고 하였는데,$\lim_{n \to \infty} \frac{n2^n}{e^n} = 0$이다

$a^n (mod m)$를 구하는 문제는 RSA 암호 등에서 사용되며 그 중요성이 크다. 단순히 곱해주는 방법이 가장 기본적이겠지만, 분할 정복을 사용하면 더 효율적으로 구하는 것이 가능하다. 보통 오래 걸리는 큰 숫자에서는 mod를 사용하지만, 나머지가 아닌 진짜 수를 원한다면 코드에서 mod 부분을 없애면 된다. 1. 기본적인 방법 숫자를 곱하며 mod 해주는 것을 n회 반복한다. 시간 복잡도는 $O(n)$이다. int pow1(int base, int index, int mod = 10) { long long r = 1; for (int i = 0; i < index; ++i) { r *= base; r %= mod; } return r; } 2. 분할 정복 $a^{2n} = (a^n)^2$이라는 ..

백준 온라인 저지(BOJ) 1009번 문제https://www.acmicpc.net/problem/1009 1. 문제 요약1번~10번의 이름을 가진 컴퓨터로 차례대로 분산 처리를 할 때, 마지막 데이터가 처리되는 컴퓨터의 번호는? 2. 알고리즘말은 복잡하지만, $a^b$의 일의 자리 수를 출력하는 문제이다.시간을 단축시키는 방법은 여기를 참고하자. 0일 경우 10으로 출력해야 한다. 3. 코드 #include int pow(int base, int index, int mod = 10) { int r = 1; while (index != 0) { if (index & 1 != 0) r = (r * base) % mod; base = (base * base) % mod; index >>= 1; } retur..

음원을 들으며, 과연 내가 들은 음원의 수익은 어떻게 분배되고 있을까 궁금한 사람들이 많을 것이다. 내가 현재 사용하는 스트리밍은 '멜론 프리클럽'인데,모바일 기준으로 DCF 파일 무제한 다운로드 가능, 음악 스트리밍 무제한 가능이며 한 달 11,400원이다.내가 지불하는 11,400원이라는 돈은 어떻게 분배되고 있는 것인지 궁금해 알아보는 시간을 가졌다. 스트리밍 기준으로 알아보고자 하니, 다운로드는 관심있는 사람이 알아보길 바란다. 1. 음원 전송 사용료2016년 2월자로, 문화체육관광부에서 지정한 곡당 사용료는월정액 스트리밍 기준 7원, 종량제 스트리밍 기준 14원이다. 이 중 권리자가 60%, 사업자가 40%를 가져간다고 하였다.사업자는 음원 서비스 업체로, 멜론, 네이버뮤직 등이 해당된다.즉, ..