본문 바로가기

분할정복9

[분할정복/DP] 백준 15624 피보나치 수 7 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 15624번: 피보나치 수 7 첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다. www.acmicpc.net 2. 문제 풀이 짧은 시간 제한(1초) 내에 피보나치 수를 구해야 합니다. 2022.05.14 - [Algorithm] - [분할정복/DQ] 백준 11444 피보나치 수 6 - 파이썬(Python) 이를 위해서는 분할정복 또는 DP를 이용해야 합니다. 여기서는 피보나치 6에서 사용했던 분할 정복을 이용했습니다. 해당 방식에 대한 설명과 코드는 위 링크에 기재되어 있습니다. 3. 코드 # 입력 N = int(input()) matrix = [[1, 1], [1, 0]] # 행렬 곱셈 def mul_matrix(mat.. 2022. 7. 27.
[분할정복/DQ] 백준 11444 피보나치 수 6 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 2. 문제 풀이 n번째 피보나치 수를 구하는 문제입니다. 본래 피보나치 수열은 동적계획법 DP를 이용해서 효율적으로 구할 수 있지만, 이 문제에서는 최대 n이 1,000,000,000,000,000,000입니다. 아주 큰 수의 피보나치를 빠르게 구하기 위해서는 분할정복을 이용한 '행렬의 거듭제곱'을 사용해야 합니다. 피보나치 규칙을 행렬로 나타내면 아래와 같습니다. 2022.05.10 - [Algorithm] - [분할정복/DQ] 백준 10830 행렬 제곱 - 파이썬(Python) 결국 행렬의.. 2022. 5. 14.
[분할정복/DQ] 백준 10830 행렬 제곱 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 2. 문제 풀이 행렬 A의 B 거듭제곱을 구하는 문제입니다. 행렬의 곱셈은 위와 같이 행과 열의 곱으로 이루어집니다. 반복문으로 구현하려면 무려 3중 for문을 써야 합니다. (O(n^3)) 따라서 계속 A를 곱하는 방법으로는 당연히 시간초과가 납니다. 2022.05.08 - [Algorithm] - [분할정복/재귀] 백준 1629 곱셉 - 파이썬(Python) 그 대신 A^B제곱을 A가 될 때까지 둘로 나눈다음, 다시 곱해주면 .. 2022. 5. 10.
[분할정복/재귀] 백준 1629 곱셈 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 2. 문제 풀이 효율적으로 거듭제곱을 구하는 문제입니다. 단순히 A**B를 하면 시간 초과가 납니다. 2022.01.29 - [Algorithm] - [Algorithm] 분할정복(DQ, Divide-and-Conquer), 각개격파 알고리즘 [Algorithm] 분할정복(DQ, Divide-and-Conquer), 각개격파 알고리즘 각개격파(各個擊破): 적을 하나하나 따로 떼어 무찌름 유독 외세의 침략을 많이 받았던 우리 민족의 대표적인 전술은 '매복'과 '각개격파'였습니다. .. 2022. 5. 8.
[분할정복/DQ] 백준 1992 쿼드트리 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 2. 문제 풀이 영상 압축방법인 쿼드 트리를 구현하는 문제입니다. 2022.01.29 - [Algorithm] - [Algorithm] 분할정복(DQ, Divide-and-Conquer), 각개격파 알고리즘 [Algorithm] 분할정복(DQ, Divide-and-Conquer), 각개격파 알고리즘 각개격파(各個擊破): 적을 하나하나 따로 떼어 무찌름 유독 외세의 침략을 많이 받았던 우리 민족의 대표적.. 2022. 3. 7.
[분할정복/DQ] 백준 1074 Z - Python [ Contents ] 1. 문제 (링크 참조) 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 2. 문제 풀이 위와 같이 Z 모양으로 이동하는 규칙이 있습니다. 이 때, 2^N * 2^N크기의 r행 c열의 순서를 구하는 문제입니다. 2022.01.29 - [Algorithm] - [Algorithm] 분할정복(DQ, Divide-and-Conquer), 각개격파 알고리즘 [Algorithm] 분할정복(DQ, Divide-and-Conquer), 각개격파 알고리즘 각개격파(各個擊破): 적을 하나하나 .. 2022. 2. 25.
[분할정복/DQ] 백준 1780 종이의 개수 - Python [ Contents ] 1. 문제 (링크 참조) 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 2. 문제 풀이 -1, 0, 1로만 이루어진 종이의 개수를 세는 문제입니다. 혼합되어 있으면, 9등분하여 다시 판별합니다. 2022.01.29 - [Algorithm] - [Algorithm] 분할정복(DQ, Divide-and-Conquer), 각개격파 알고리즘 [Algorithm] 분할정복(DQ, Divide-and-Conquer), 각개격파 알고리즘 각개격파(各個擊破): 적을 하나하나 따로 떼어 무.. 2022. 2. 16.
[분할정복/DQ] 백준 2630 색종이 만들기 - Python [ Contents ] 1. 문제 (링크 참조) 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 2. 문제 풀이 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 문제입니다. 정사각형의 색종이에 하얀색과 파란색이 섞여 있을 경우, 분리될 때까지 4분할을 합니다. 입력으로 주어지는 색종이의 크기는 2, 4, 8, 16, 32, 64, 128 중 하나입니다. 2022.01.29 - [Algorithm] - [Algorithm] 분할정복(DQ, Divide-and-Conquer), 각.. 2022. 1. 29.
[Algorithm] 분할정복(DQ, Divide-and-Conquer), 각개격파 알고리즘 각개격파(各個擊破): 적을 하나하나 따로 떼어 무찌름 유독 외세의 침략을 많이 받았던 우리 민족의 대표적인 전술은 '매복'과 '각개격파'였습니다. 70%가 산악지형인 점을 이용해서, 산개된 적들을 각각 무찔렀습니다. 이런 각개격파 전술은 '알고리즘 문제'에서도 유효합니다. 사람 사는 세상의 이치는 만물이 통하니까요. [ Contents ] 1. 분할 정복 알고리즘 분할 정복(Divide-and-Conquer, DQ): 주어진 문제의 입력을 분할하여 해결하는 방식 알고리즘 문제도 분할해서 풀면, 쉽게 해결되는 경우가 많습니다. 예를 들어, 방대한 데이터(100GB)를 오름차순으로 정렬하는 문제는 그대로 해결할 수 없습니다. 한 번에 정렬을 하려면, 데이터베이스의 모든 데이터를 메인 메모리(RAM)에 올려야.. 2022. 1. 29.

티스토리툴바