코테 여름방학 챌린지 2주차 - 재귀함수, 분할 정복

재귀함수란?
함수의 일종이고, 함수 내에서 자기 자신을 호출하는 함수이다.

1. 1부터 n까지 더하는 함수

def sum_n(x): 
	#base case 
	if x ==1: 
    	return 1 

	return sum_n(x-1) + x
	
print(sum_n(4))

• 종료 조건이 필수임. -> 재귀함수, 자기자신만 호출하는 함수만 있으면 영원히 끝나지 않아서 base case가 필요함.
• 종료 조건은 가장 작은 값으로 마지막 부분이 어딘지를 생각하면 됨.

4779. 칸토어 집합 -> 재귀함수

말로 정리하기
문제 요약: 길이가 3^n인 -로 이루어진 문자열을 만든다.
3등분을 하여 가운데에 공백이 생기도록한다.
양쪽 구간에 대해 반복한다.
base case: n=0일때, -하나 출력하는것이 base case이다.
#재귀 #base case 처리 #end = "" 문자열 출력 형식 제어

#1. 바로 출력하기

#1. 입력 n을 받아 길이 3^n인 문자열 생성 
import sys
input = sys.stdin.readline


#함수 
def canto(x):
	#base case 
	if x==0: 
		print("-", end = "")
		return 

	#recursive case 
	canto(x-1)
	print(" " * (3**(x-1)), end = "")
	canto(x-1)

#입력 받기 
while True: 
	try: 
		N = int(input())
		canto(N)
		print()

	except: 
		break 

#2.문자열을 리스트로 저장하고 공백으로 바꾸는 방법

• 길이가 3^n인 문자열을 만들고 중간에 공백을 만들어야 하니 리스트를 써야겠다.
• 재귀는 양옆은 그대로 처리하고 가운데만 바꾸는 구조네
• start: 현재 처리 시작 인덱스, length: 재귀 처리 길이를 알아야겠네.
  =>재귀를 두번 호출해야한다는 것을 알면 print만 제대로 하면 됨.

2630. 색종이 만들기 - 분할 정복

코딩하기 전 3단계로 나눠서 풀기
1. 문제 이해 -> 말로 정리하기

• 주어진 nxn 크기의 2차원 배열이 있고, 같은 색인지 확인
• 같은 색이면, 그 색깔 종이의 개수를 1 증가
  다른 색이면 4등분 해서 같은 과정 반복한다.

*여기서 어떻게 4등분을 할까 ?
좌표 x, y, 한변의 길이 size를 입력으로 받는다고 하면,

h = size //2 
#왼쪽 위 
solve(x, y, h)
#오른쪽 위 
solve(x,y+h, h)
#왼쪽 아래 
solve(x+h, y, h)
#오른쪽 아래 
solve(x+h, y+h, h)

2. 구조 설계
#1. 입력 받아서 paper에 저장

#2. 함수 정의 : solve(x,y,size)
-> x,y는 현재 정사각형의 왼쪽 위 좌표/ size는 한변의 길이

#3. base case:
해당 구간의 모든 값이 같은 색 -> white +=1 or blue +=1

#4. 그렇지 않으면-> size //2 4개의 구간에 대해 재귀 호출

#5. 마지막 w,b 출력

3. 코드 초안 작성

import sys 
input = sys.stdin.readline 

N  = int(input()) 
paper = [list(map(int, input().split())) for _ in range(N)]

#함수 정의 
w, b = 0,0 
def solve(y, x, size): 
	global w, b 
    color = paper[y][x]
    for i in range(y, y+size): 
    	for j in range(x, x+size): 
        	if color != paper[i][j]: #다르면 
            	m = size // 2 
                solve(y, x, m)
                solve(y+size, x, m )
                solve(y, x+size, m)
                solve(y+size, x+size, m)
                return 
   	if color ==1: 
    	b += 1
    else: 
    	w += 1
    return 
solve(0,0,N)
print(w)
print(b)