알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 분할 정복으로 푸는 문제였습니다. 예시로 주어진 삼각형을 같은 모양을 기준으로 계속 나눴습니다. 계속 나누다보면 작은 삼각형 모양이 나오는데, 그것이 기준 모양입니다. 해당 모양을 통해 삼각형이 이루어진 것을 확인할 수 있습니다. 해당 삼각형을 좌표로 생각한 뒤, 각 중심의 좌표를 확인해봤습니다. (해당 그림을 통해 확인해볼 수 있습니다.) 해당 좌표를 통해, 삼각형이 3분류로 어떻게 나눠지는지 확인할 수 있습니다. 이를 공식으로 ..

문제 링크입니다. https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 행렬 제곱을 분할 정복을 통해 푸는 문제입니다. 이 문제를 풀기 위해서는 행렬의 제곱을 할 수 있어야 합니다. 행렬 제곱이 어떻게 계산되는지 2 * 2 / 3 * 3 행렬을 통해 확인해보겠습니다. 2 * 2 / 3 * 3 행렬의 곱셈을 통해, 앞 행렬은 [X][Y] 중 X부분이 바뀌고, 뒤 행렬은 Y부분이 바뀌는 것을 알 수 있습니다. 이를 통해 행렬의 곱셈을 구현할 수 있습니다. matrix..

문제 링크입니다. https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 분할정복을 이용한 거듭제곱을 활용해 푸는 문제였습니다. A를 B번 제곱을 그냥하게 되면 long long 범위도 벗어나기 때문에 다른 방법이 필요합니다. 또한 B의 범위가 21억이기에, 시간 초과가 생길 수도 있습니다. 이때 사용하는 방법이 분할 정복을 활용한 거듭제곱입니다. 먼저 제곱을 하는 코드를 만들어 보겠습니다. int ans = 1; for(int i = 1; i A >> B >> C; solve(); return 0; } 질문 및 조..

문제 링크입니다. https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 재귀를 사용하는 문제였습니다. 답이 나오는 과정입니다. 1. map을 한번 확인해본다 1-1. map이 0이나 1로만 모두 차있다면 해당 값을 출력합니다. 1-2. 위의 경우가 아니라면 map을 4개로 나눈뒤 (를 출력합니다. 2. 4개로 나뉜 map을 다시 확인해봅니다. 3. 1~2과정을 반복한뒤, 확인이 끝날때마다 )을 출력합니다. 1. map을 확인하는 과정 v..