재귀함수 활용하기

1. 문제

 

https://programmers.co.kr/learn/courses/30/lessons/68936

코딩테스트 연습 - 쿼드압축 후 개수 세기

 

0과 1로 이루어진 $2^n \times 2^n$ 크기의 2차원 정수 배열 arr이 있습니다.

 

당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다.

 

구체적인 방식은 다음과 같습니다.

 

1. 당신이 압축하고자 하는 특정 영역을 S라고 합니다.

 

2. 만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.

 

3. 그렇지 않다면 S를 정확히 4개의 균일한 정사각형 영역(입출력 예를 참고)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다.

 

arr이 매개변수로 주어집니다. 위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로 남는 0의 개수와 1의 개수를 배열에 담아서 return하도록 solution 함수를 완성하세요

 

2. 제한사항

 

arr의 행의 개수는 1 이상 1024 이하이며, 2의 거듭 제곱수 형태를 하고 있습니다. 즉, arr의 행의 개수는 1,2,4,8,...,1024 중 하나입니다.

 

arr의 각 행의 길이는 arr의 행의 개수와 같습니다. 즉 arr은 정사각형 배열입니다.

 

arr의 각 행에 있는 모든 값은 0 또는 1입니다.

 

3. 입출력 예시

 

그림1. 입출력 예시

그림2. 입출력 예시 설명

 

4. 나의 풀이

 

예시 설명을 보면 

 

1) 배열을 입력으로 주고

 

2) 전부 1인지 0인지 확인해서 압축이 가능한지 검사

 

3-1) 압축이 가능하다면 압축하고 return

 

3-2) 압축이 불가능하다면 균일한 크기의 4개 영역으로 자르고 1)로 돌아감

 

위와 같은 알고리즘을 따른다

 

전부 1인지 0인지 확인해서 압축이 가능한지 검사하는 함수를 먼저 작성함

 

def total_inspection(arr):
        
        one_ind = False
        
        zero_ind = False
        
        one_arr = sum(arr,[])
        
        if 1 in one_arr:
            
            one_ind = True
        
        if 0 in one_arr:
            
            zero_ind = True
        
        return zero_ind,one_ind

 

전부 1이라는 것을 나타내는 one_ind, 전부 0이라는 것을 나타내는 zero_ind

 

2차원 배열 arr을 입력으로 받아 sum(arr,[])을 통해 1차원 배열로 변경하고

 

1차원 배열 one_arr에 1이 있으면 one_ind=True라 하고 0이 있으면 zero_ind=True라고 함

 

그래서 one_ind만 True이면 전부 1만 있다는 의미이고 zero_ind만 True이면 전부 0만 있다는 의미가 됨

 

one_ind와 zero_ind가 모두 True이면 4개 영역으로 split해야함

def split_arr(arr,length):
        
        s1 = []
        
        s2 = []
        
        s3 = []
        
        s4 = []
        
        s1_s2 = arr[:length//2]
        
        s3_s4 = arr[length//2:]
        
        for row1,row2 in zip(s1_s2,s3_s4):
            
            s1.append(row1[:length//2])
            
            s2.append(row1[length//2:])
            
            s3.append(row2[:length//2])
            
            s4.append(row2[length//2:])

        return [s1,s2,s3,s4]

 

one_ind와 zero_ind가 모두 True인 배열 arr과 정사각형 배열이니까 길이 구하기도 len(arr)로 쉬운데 arr의 길이인 length를 받는다

 

4개 영역을 줄 s1,s2,s3,s4로 빈 리스트를 만들고

 

s1_s2 = arr[:length//2]로 절반의 row를 가져와 s1_s2라 하고 나머지 절반의 row인 arr[length//2:]를 s3_s4로 가져온다

 

그 다음 각 row에서 절반씩 자르면 column이 절반이 되니까

 

zip을 이용한 for문으로 s1_s2와 s3_s4에서 row1,row2를 가져온 다음에

 

길이의 절반인 length//2씩 indexing해서 column의 절반씩을 s1,s2와 s3,s4 각각에 할당

 

for문 전부 돌면 s1,s2,s3,s4 4개 영역으로 나뉘면서 return

 

zero_count = 0
    
one_count = 0

def recursive_solve(arr):

    global zero_count, one_count

    zero_ind,one_ind = total_inspection(arr)

 

다음 재귀적인 풀이를 위해서 재귀함수를 작성하는 단계

 

0의 개수와 1의 개수를 세서 zero_count와 one_count에 저장을 할거임

 

zero_count=0, one_count=0으로 초기화하고

 

전역변수로 설정하기 위해서 global 문을 사용함

 

-----------------------------------------------------------------------------------------------------------------------------

근데 이렇게만 전역변수를 설정하면 error가 남

 

사용자 정의 함수 def안에서 전역변수 설정할 때는

 

def 함수 밖에서 global로 전역변수를 명시하고, def함수 안에서 해당 전역변수를 사용하겠다고 global로 명시해줘야함

 

그림3. 전역변수 사용 예시

위 그림에서 recursive_solve() 안에 zero_count와 one_count를 사용하기 위해 

 

recursive_solve() 밖에서 zero_count와 one_count를 global로 명시하고

 

recursive_solve()에서 사용하겠다는 의미로 global로 명시해줌

 

--------------------------------------------------------------------------------------------------------------------------

그리고 배열 arr을 받아서 전부 0인지 1인지 검사해서 zero_ind와 one_ind를 가져옴

 

if zero_ind and one_ind:
            
            if len(arr) == 2:
                
                arr = sum(arr,[])
                
                for e in arr:
                    
                    if e == 1:
                        
                        one_count += 1
                    
                    else:
                        
                        zero_count += 1

 

다음에 zero_ind와 one_ind가 모두 True인 경우는 압축이 불가능해서 split을 해야함

 

split하기 이전에 더 이상 split을 안해도 되는 타이밍을 알 수 있는데

 

1과 0이 모두 존재한다는 True인 상태에서 arr이 $2 \times 2$ 배열일 때는 더 이상 split할 필요도 없이 

 

그냥 1차원 배열로 바꾼 다음에 1의 개수와 0의 개수를 세면 됨

 

그런데 $2 \times 2$배열이 아닌 경우에는 split을 해야하는데

 

else:
            
                arr1,arr2,arr3,arr4 = split_arr(arr,len(arr))
                
                recursive_solve(arr1)

                recursive_solve(arr2)

                recursive_solve(arr3)

                recursive_solve(arr4)

 

현재 arr과 arr의 길이인 len(arr)을 split_arr 함수에 넣어서 4개의 arr인 arr1,arr2,arr3,arr4를 받아옴

 

그런 다음에 이 4개의 arr1,arr2,arr3,arr4를 전부 다시 recursive_solve에 집어넣어서

 

동시에 재귀함수가 돌아가게 만든다

 

else:
            
            if zero_ind:
                
                zero_count += 1
            
            else:
                
                one_count += 1

 

그런데 arr을 넣었을 때 zero_ind와 one_ind가 모두 True가 아니고 하나만 True인 경우가 있을 수 있다

 

그런 경우는 하나의 수로 압축을 하므로 zero_ind=True이면 zero_count에 1을 더해주고

 

one_ind=True이면 one_count에 1을 더함

 

recursive_solve(arr)
                
return [zero_count,one_count]

 

그러면 이제 만든 재귀함수에 arr을 넣으면 zero_count와 one_count를 세서 최종 zero_count와 one_count가 생길거임

 

-----------------------------------------------------------------------------------------------------------------------------

재귀함수가 사실 조금만 생각하면 어려운게 아님

 

그림4. 재귀함수 예시1

 

첫번째 케이스에서 arr을 넣으면 압축이 안되니까 arr1과 arr2, arr3,arr4로 분할되고 다시 recursive_solve()에 각각 들어감

 

프로그램은 위에서 아래로 수행되니까 recursive_solve(arr1), recursive_solve(arr2), recursive_solve(arr3), recursive_solve(arr4)가 각각 차례대로 수행이 될거임

 

함수들이 수행이 되면서 최종 압축 상태인 $2 \times 2$ 배열까지 만들어지면서 zero_count와 one_count 값을 구해나갈거임

 

여기서 zero_count와 one_count를 인수로 받지 않고 편하게 사용하고자 전역변수로 설정했음

 

recursive_solve(arr1)이 먼저 수행되면서 $2 \times 2$ 배열이니까 1의 개수와 0의 개수를 세서 zero_count=1 one_count=3을 구하게 될거임

 

다음에 recursive_solve(arr2)가 수행이 될건데 zero_ind=True, one_ind=False가 되어 zero_count에만 1이 더해져서 zero_count=2, one_count=3이 될거임

 

다음으로 recursive_solve(arr3)이 수행이 되면서 $2 \times 2$ 배열이니까 1의 개수와 0의 개수를 세서 zero_count=3, one_count=6으로 더해질거임

 

마지막으로 recursive_solve(arr4)가 수행이 되면서 $2 \times 2$ 배열이니까 1의 개수와 0의 개수를 세서 zero_count=4, one_count=9로 최종적으로 구해지게 됨

 

최종적으로 구해진 zero_count와 one_count가 정답이니까 이들을 리스트로 묶어서 return함

 

-----------------------------------------------------------------------------------------------------------------------------------

 

두번째 예시를 살펴보면

 

그림5. 재귀함수 예시2

 

recursive_solve(arr)을 풀어야하는데 압축이 안되니까 4개 영역 arr1,arr2,arr3,arr4로 분할이 되고

 

recursive_solve(arr1), recursive_solve(arr2), recursive_solve(arr3), recursive_solve(arr4)를 차례대로 수행을 한다

 

recursive_solve(arr1)을 먼저 푸는데 압축이 안되니까 다시 4개의 부분문제

 

recursive_solve(arr1'), recursive_solve(arr2'), recursive_solve(arr3'), recursive_solve(arr4')으로 분할이 된다

 

각각은 이제 $2 \times 2$배열이니까 답을 낼 수 있는 상태가 되고

 

각각에서 1과 0의 개수를 세는데 전역변수니까 모든 경우에서 이전에 구해진 정답이 저장이 된다

 

이렇게 큰 문제를 작은 문제로 분할해가면서 최종 답을 구해낼때까지 분할해서 최종적으로 답을 전부 합쳐나가는 방식으로 풀어낸다

 

-----------------------------------------------------------------------------------------------------------------------------------

5. 다른 풀이

 

좋아요를 많이 받으면서 합리적인 풀이

 

전체적인 느낌은 나랑 비슷한데 시간이 훨씬 빠르다

 

def solution(arr):
    
    answer = [0, 0]

    def check(size, x, y):
        
        if size == 1:
            
            answer[arr[y][x]] += 1
            
            return
        
        else:
            
            first = arr[y][x]

            for dy in range(size):
                
                for dx in range(size):
                    
                    if first != arr[y + dy][x + dx]:
                        
                        check(size // 2, x, y)
                        check(size // 2, x + size // 2, y)
                        check(size // 2, x, y + size // 2)
                        check(size // 2, x + size // 2, y + size // 2)
                        
                        return
            
            answer[first] += 1
    
    check(len(arr),0,0)

    return answer

answer는 아마 [0의 개수, 1의개수]를 일단 초기화 [0,0] 한 것일테고

 

check()는 1의 개수와 0의 개수를 재귀적으로 세는 함수

 

size=1이 되면 1인지 0인지 개수를 세면 되니까 answer[arr[y][x]]에 1을 더한 것일테고

 

size=1이 아니면 압축이 가능한 상태인데

 

첫번째를 arr[y][x]로 잡아둠

 

y행 x열 원소를 first로 잡아둔다는 소리인데

 

재귀함수 마지막에 수행할 때 check(len(arr),0,0)으로 수행한 것으로 보아 좌상단 0,0 원소를 first로 잡아둔다는 소리인데

 

size만큼 이중 for문을 도는데 행 index를 0,1,2,...,dy,...,size-1 열 index를 0,1,2,...,dx,...,size-1 

 

조건문에서 first != size[y+dy][x+dx]라는 뜻은 보니까

 

0,0에서 dy,dx만큼 움직여보면서 정사각형 안에 무슨 원소가 있는지 검사를 하는 것

 

좌상단의 0,0 원소와 dy,dx만큼 움직인 y+dy,x+dx 원소가 서로 다르다면 정사각형 내의 모든 원소가 같지않고 다르다는 소리니까 분할을 해야한다는 의미

 

분할을 어떻게 했는가??

 

정사각형 크기는 절반인 size//2로 줄이고 시작지점을 4군데를 설정을 하는것

 

0,0과 x축으로 절반길이 움직인 size//2,0과 y축으로 절반길이 움직인 0,size//2와 x,y축으로 절반길이 움직인 size//2,size//2에서 시작을 하는것

 

그림으로 생각해보면 진짜 어마어마하다

 

그림6. check()함수 분할 그림 설명

 

for문을 전부 돌았는데 return이 안된다면 arr내의 모든 원소가 전부 first와 같다는 의미이므로

 

answer[first]에 1을 더해준다

 

return을 쓰는 이유는

 

return 뒤에 아무것도 안쓰면 None을 return함

 

for문을 돌면서 검사과정에서 다른 원소가 발견이 된 순간 4개의 check로 분할을 하고 return을 해서 이 함수는 끝을 내야지

 

return을 안하면 for문이 계속 돌면서 동일한 4개의 분할 check를 서로 다른 원소가 감지될 때 마다 하게 되니까 answer가 이상해짐

 

 

6. 되돌아보기

 

재귀함수 구상이 처음에 어려웠는데 천천히 생각해서 결과적으로 잘 했다

 

1개 문제에서 4개로 분할이 된다면 재귀함수내에 4개의 부분 재귀함수를 쓰면 된다

 

1개로 계속 파고들지 말고

 

전역변수 설정할 때 함수 내에서 사용을 할려면 함수 내에서도 global로 명시를 해줘야한다는 점

 

다른 풀이에서 정사각배열 내의 원소들을 비교하는 방법이 멋있었다

 

첫 원소를 arr[0][0]으로 지정하고 이중 for문 for dx in range(size): for dy in range(size):를 돌면서

 

arr[0+dx][0+dy]를 하면 정사각배열 내의 모든 원소를 생각할 수 있었다는 점

 

 

 

7. 참고

 

https://www.infoking.site/64

파이썬 global 전역변수 사용방법과 사용예 알아보기!