분할정복

[python] 백준 - 1780. 종이의 개수

🤔문제 해결 S2 | 분할정복 첫번째에 있는 코드가 더 정답인거 같다( 둘다 통과했지만 ) 첫번째 코드는 항상 9개의 조각으로 잘라서 진행한다. - 이게 문제랑 더 맞는거 같다. 하지만 두번째 코드는 (처음 풀어서 통과하고 다시보니 이상함) 9개의 조각이 아니다. 종이가 들어오면 3x3으로 다 잘라버린다. 그래도 통과한다. 이게 되네?? 내가 문제를 잘 이해하지 못한건지... 내가 짠 코드를 이해하지 못한건지 잘 모르겠다. 💻소스 코드 from itertools import chain # 2차원 리스트를 1차원리스트로 바꿔주는 친구 def bt(paper): global a, b, c nn = len(paper) if len(set(chain.from_iterable(paper))) == 1: if pa..

[python] 백준 - 1992. 쿼드트리

🤔문제 해결 1. 분할정복 | S1 2. 재귀함수를 이용했다 3. 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 를 차례로 쪼개서 모두 1이나 0으로 이루어져 있는지 확인하고 4. 아닐 경우 다시 쪼개서 확인한다. 💨 맨 처음 배열이 모두 1인지 0인지 확인을 안해서 잠시 고민을 했던 문제!!! 답이 0이나 1이 될 수 있다 문제를 이해하는 것은 쉬우나 재귀함수를 사용했기 때문에 답을 출력하는게 힘들 수 있다. 맨 처음 함수에 들어왔다는 것은 하나의 묶음을 생성해야 하기 때문에 괄호를 사용해서 적절히 묶어준다.( 시작할 때 끝날 때) 💻소스 코드 from itertools import chain # 2중 리스트를 단일 리스트로 바꾸기 위해서 chain 함수 사용했음 def compression(lst)..

[python] 백준 - 1074. Z

🤔문제 해결 1. 재귀,분할정복 | S1 2. 모두 쪼개려고 하는경우 메모리초과 혹은 시간초과가 발생한다. 3. 내가 찾고자하는 행과 열이 포함된 박스만 찾아서 재귀함수를 실행시킨다. 4. 여기서 각 박스의 첫 숫자를 구한다. (1) 예를 들어 사이즈가 8인 박스의 첫숫자는 0이다. 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 박스를 쪼개면 (2) 각 박스의 첫 숫자는 0, 16, 32, 46 이다. (3) 왼쪽 위 박스는 그대로, 오른쪽 위 박스는 첫숫자에 (size//2)**2*1 값을 더해준다. (4) 왼쪽 아래 박스는 첫숫자에 (size//2)**2*2 값을, 오른쪽 아래 박스는 첫숫자에 (size//2)**2*3 값을 더해준다. 5. 박스의 크기가 2가 되면 찾고자 하는 행과 열을 찾..