Divide and Conquer

문제 링크 https://www.acmicpc.net/problem/1780 문제 해설 Idea Divide and Conquer 2차원 배열의 요소를 완전탐색하면서 동일한 값으로 구성되지 않을 경우, 행렬을 9등분하여 재귀적 호출 수행 처음 시도에서는 행렬을 매번 슬라이싱하면서 전달하여 시간 초과가 발생 행렬의 시작 인덱스 번호를 전달하고 길이만큼 참조하는 방식으로 시간 복잡도 개선 Data Size N: 1 <= int <= 3^7 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 import sys input = sys....

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/68936 문제 해설 Idea Divide and Conquer 2차원 배열을 4등분씩 나눠 재귀함수를 호출하고 동일한 값으로 채워져 있는지 판단하여 값의 개수 증가 2^n 형태의 정수에 대해 NumPy를 활용해 행렬 인덱싱을 간단히 구현 Time Complexity O(N^2 Log N^2) = 20,000,000 Data Size arr: [[int(1)]], shape(2^n, 2^n) 1 <= 2^n <= 1024 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 import numpy as np def quad_comp(n, arr, answer): values = np....