https://www.acmicpc.net/problem/5095 5095번: Matrix Powers The input consists of a number of problems. Each problem starts with a line holding three numbers (N, M, and P) separated by single spaces. 1 ≤ N ≤ 100 is the size (N by N) of the matrix to be processed. 1 ≤ M ≤ 32000 is the modulo base and 1 ≤ www.acmicpc.net 10830 행렬제곱 문제와 똑같은 문제다. 알고리즘 포스팅에서 분할정복을 주제로 한 포스팅이 있었는데, 마지막 부분에 분할정복 연습문제로 분할..

https://www.acmicpc.net/problem/22953 22953번: 도도의 음식 준비 첫째 줄에 요리사의 수 $N$ ($1 \le N \le 10$), 만들어야 할 음식의 개수 $K$ ($1 \le K \le 1\,000\,000$), 격려해줄 수 있는 횟수 $C$ ($0 \le C \le 5$)가 주어진다. 둘째 줄에 길이가 $N$인 정수 수열 $A$가 주어 www.acmicpc.net 다른 골드4의 매개변수 탐색보다 많이 까다로운 문제다. 값의 범위가 작기 때문에 브루트 포스를 의심하는 것이 첫 번째 단계다. 도도가 요리사에게 격려를 해줄 수 있는 모든 경우의 수를 나이브하게 따져도 10의 6승이고, 각각의 경우에 매개변수 탐색은 log2(10^6 * 10^6) 이므로 시간적으로 10의..

https://www.acmicpc.net/problem/22940 22940번: 선형 연립 방정식 하나 이상의 미지수에 대해 최고차항의 차수가 1을 넘지 않는 방정식을 선형 방정식이라 한다. 족, 다음과 같은 식을 의미한다. A1x1 + A2x2 + ... + Anxn = B 선형 연립 방정식이란 유한개의 선형 방 www.acmicpc.net 다른 풀이가 당연히 있겠지만, 컴퓨터공학을 전공한다면 Gauss - Jordan 소거법을 사용할 듯 하다. 선형대수학에서 배운 기본 행 연산을 통해 계수행렬을 RREF(Reduced Row Echelon Form)으로 만들는 과정을 그대로 구현하면 된다. 이 문제에서는 주어지는 행렬이 최대 6 by 6이고, 계수들도 모두 10까지의 자연수로만 이루어져 있는데 과정..

https://www.acmicpc.net/problem/27650 27650번: 마법박스 다음을 표준 출력 스트림(stdout)으로 한 줄에 출력하여, $i$ 이하의 $2$ 이상의 양의 정수가 마법박스에 모두 들어있는지 질의할 수 있다. 질의에 대한 답변은 모두 들어있다면 $1$, 그렇지 않다면 $0 www.acmicpc.net 인터렉티브 문제로 채점 방식이 특이하다. "?"를 출력하여 문제에게 질문해야하고, 문제가 답을 주면 범위를 줄여서 물어보고... 그러다가 "!"로 답을 출력해야한다. 이 문제에서는 질문할 수 있는 횟수가 20번이므로 스무고개라고 생각하면 된다. 처음으로 이런 유형을 풀어봤고 문제랑 대화하는 느낌이 들어서 재밌었다. 마법박스에 들어있는 수 중에서 가장 작은 정수를 찾으면 되는데,..

DP: 한 문제를 해결하기 위해 문제를 부분 문제로 분할하여 해결하고 부분문제들의 해를 바탕으로 큰 문제를 해결하는 문제해결기법. 정의를 딱 보자마자 생각나는 생각이 분할정복이랑 비슷하다라는 생각이 든다. 하지만 내용은 문제를 나눈다는 사실을 제외하고는 비슷한 문제해결방법이 아니다. 심지어 문제를 나누는 것도 분할정복은 큰 문제라는 덩어리를 여러부분으로 쪼개는 느낌이고, DP는 큰 문제의 이전 단계의 경우를 생각하는 걸 문제를 나눈다고 한다. 분할정복: 큰 덩어리 문제를 작은 덩어리로 쪼개서 해결한 뒤에 합치는 방식으로 문제를 해결 DP : 큰 문제를 작은 부분 문제로 나누고 작은 부분 문제의 해을 저장하여 중복 계산을 피하거나, 작은 부분문제의 최적해로 점화식을 세워 큰 문제를 해결 DP는 문제 유형을..

● 분할정복(Divide and Conquer) 한번에 해결하기에 불가능하거나 매우 오래걸리는 문제를 작은 문제로 나눠서(분할) 해결하고 다시 결합하여(정복) 문제를 해결하는 방식 **앞서 포스팅 했던 이분탐색 또한 분할정복을 사용한 알고리즘 Merge sort(병합정렬) 분할정복을 이용한 정렬방법으로 O(NlogN)의 시간복잡도를 가지며 버블정렬, 삽입정렬, 선택정렬 보다 실행시간이 빠르다. (파이썬에 내장되있는 sort함수도 병합정렬) 병합정렬을 통해서 분할정복이 어떤식으로 이루어지는지 알아보자. 정렬을 하기 위해 임의의 무작위 배열 arr = [3, 25, 1, 75, 42, 100, 63, 38] 이 있다고 하자. 이 배열의 Divide 과정은 아래그림과 같다. 배열의 중간을 기준으로 더 이상 나..