728x90 divide and conquer 썸네일형 리스트형 [백준알고리즘] 10830번: 행렬 제곱 -Python [백준알고리즘] 10830번: 행렬 제곱 -Python https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 빠른 모듈로 거듭제곱을 개념을 이용해 행렬 곱셈을 수행했다. 분할 정복의 개념을 사용했고 아래와 같은 방식에 각 원소마다 모듈로를 해주는 것으로 수행했다. A^11 = A^10 * A^10 * A^1 A^8 = A^4 * A^4 코드 내용은 거의 같으나 @iknoom1107 님의 코드를 보니 for문으로 작성했던 부분을 sum()을 이용해 원소의 값을 구해.. 더보기 [백준알고리즘] 2261번: 가장 가까운 두 점 -Python [백준알고리즘] 2261번: 가장 가까운 두 점 -Python https://www.acmicpc.net/problem/2261 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 같은 점이 여러 번 주어질 수도 있다. www.acmicpc.net 진짜 어이없는 문제다. 문제를 푼 코드가 별 차이 없어 보이는데 내 거만 왜 통과를 안 하는지... 코드는 아래 블로그의 코드를 거의 참조해서 겨우 통과했는데... 이전에 통과하지 못한 코드도 별 차이 없는데 안된다.. 게다가 내가 짠 코드는 PyPy에서만 통과를 한다. ㅡㅡ 대체 무슨 차이인지 모.. 더보기 [백준알고리즘] 11729번: 하노이 탑 이동 순서 -Python [백준알고리즘] 11729번: 하노이 탑 이동 순서 -Python https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5 www.acmicpc.net 오랜만에 하노이탑 문제를 푼 것 같다. 분할 정복 문제.. 더보기 [백준알고리즘] 2630번: 색종이만들기 -Python [백준알고리즘] 2630번: 색종이만들기 -Python https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다. www.acmicpc.net 학교 공부하느라 정신이 없다ㅏ.. 머리 식힐 겸 간단한 거 하나 풀었다. 이 문제는 분할 정복 문제이다. 분할 정복과 동적 계획법은 비슷하지만 다른 개념이다. 간단하게 한 번 살펴보자면, 일단 둘 다 반복과 재.. 더보기 이전 1 다음
