deulee의 개발 노트

문제 크기가 N•N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하는 것이다. 입력 첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000) 그 다음줄 부터 N개의 줄에 행렬의 각 원소가 주어진다. 예제 입력 2 5 1 2 3 4 예제 출력 69 558 337 406 문제 해결 어디서 힌트를 얻을 수 있을까? '제곱'이라는 키워드에 중점을 둬서 이 문제를 풀어야 한다. 거듭 제곱 문제를 풀 때 제곱의 수를 반으로 줄여서 곱하는 것은 똑같은 결과를 가져다 주는 것을 알 수 있다. N^B = N^(B/2) * N^(B/2) 이렇게 계속 반으로 줄이다 보면 더 이상 줄이지 못하는 기저 사례가 나오게 되고 처리해 주면 된다. 만약 홀수가..

알고리즘/문제 2023. 6. 10. 00:14

문제 전위 순회하는 이진 트리가 주어진다. 이를 통해 후위 순회한 결과를 출력한다. 입력 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 10^6보다 작은 양의 정수이다. 노드의 수는 10,000개 이하이다. 예제 입력 50 30 24 5 28 45 98 52 60 예제 출력 5 28 24 45 30 60 52 98 50 문제 해결 어디서 힌트를 얻을 수 있을까? 전위 순회라는 말에서 우리는 이것을 분할 정복으로 문제를 풀 수 있다는 것을 눈치챌 수 있다. 전위 순회는 (루트)(왼쪽 자식)(오른쪽 자식) 순으로 출력하는 순회 방법으로 맨 처음 출력되는 것이 루트라는 것을 알 수 있다. 또한, 이는 이진 트리이기 때문에 루트를 기준으로 왼쪽은 더 작은 값 오른쪽은 더 큰 값이라는 것을 알 ..

알고리즘/문제 2023. 6. 4. 23:30

문제 N이 주어졌을 때 첫째 줄부터 N번째 줄까지 별을 출력한다. 이때 규칙에 따라 출력해야 한다. 입력 첫째 줄에 N이 주어진다. N은 항상 3•2^k 수이다. (0 ≤ k ≤ 10) 예제 입력 24 예제 출력 * * * ***** * * * * * * ***** ***** * * * * * * ***** ***** * * * * * * * * * * * * ***** ***** ***** ***** * * * * * * ***** ***** * * * * * * * * * * * * ***** ***** ***** ***** * * * * * * * * * * * * ***** ***** ***** ***** * * * * * * * * * * * * * * * * * * * * * * * * ***..

알고리즘/문제 2023. 5. 30. 14:36

문제 N개의 정점을 갖는 이진 트리의 정점에 1부터 N까지의 번호가 중복 없이 매겨져 있다. 이때 중위 순환과 후위 순환이 주어졌을 때, 선위 순환을 구하는 프로그램을 작성해라. 입력 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 줄에 중위 순환을 나타내는 N개의 자연수가 주어진다. 그다음 줄에 후위 순환을 나타내는 N개의 자연수가 주어진다. 예제 입력 3 1 2 3 1 3 2 예제 출력 2 1 3 문제 해결 어디서 힌트를 얻을 수 있을까? 우선 중위 순환과 후위 순환이 어떻게 이루어지는지 알 필요가 있다. 중위 순환 : (왼쪽)(루트)(오른쪽) 후위 순환 : (왼쪽)(오른쪽)(루트) 위를 보면 알겠지만 후위 순환으로 출력하게 될 경우 루트는 가장 마지막에 존재한다. 이를 통해 루트를 ..

알고리즘/문제 2023. 5. 26. 00:04

문제 자연수 A를 B번 곱하는 거듭제곱을 구하는 문제이다. 이때 구하려는 수가 커지는 것을 방지해 C를 나눈 나머지를 구하는 프로그램을 작성한다. A^B 입력 A, B, C가 차례대로 주어진다. 입력 예제 10 11 12 예제 출력 4 문제 해결 어디서 힌트를 얻을 수 있을까? 문제에서는 A를 B번 곱한 수를 구하는 것이라고 했다. 이 말을 다르게 생각하면 A는 B의 거듭제곱이 되는 것이다. 거듭제곱은 수열의 빠른 합과 같은 맥락으로 풀 수 있다. 즉, B를 계속 반으로 나눈 값으로 문제를 푸는 것이다. 이렇게 된다면 문제는 다음과 같이 정의할 수 있다. A^(B/2) * A^(B/2) ↓ K = A^(B/2) ↓ K * K 위와 같이 바꿀 수 있는 것이다. 그러면 홀수의 경우는 어떨까? 홀수의 경우에는..

알고리즘/문제 2023. 5. 22. 00:18