크래프톤 정글 8기 - 9일차 TIL

크래프톤 정글 9일 차 TIL 및 회고를 진행합니다.

9일 차 주요 이슈 : 알고리즘 기초 특강

정글 생존 9일 차 알고리즘 1주 차 진행 중 알고리즘 기초 특강을 진행해 주셨다. 코치님이 앞에 서서 문제를 풀고 풀이를 설명하는 것은 아니었다. 다만 알고리즘이 왜 중요한지 그중 특히 정글러들이 모두 어려워하는 재귀에 대해서 30분가량 짧게 설명해 주셨다. 그리고 이후. 오늘의 알고리즘 풀이는 주로 재귀와 관련된 문제를 진행했다.

재귀에 대한 이모저모

재귀를 실무에서 개발자가 직접 코딩하는 경우가 있는가? - 물론 직접 재귀를 사용해 구현을 하는 경우는 없을 수 있다. 대신 우리가 자주 사용하는 정렬이나 함수 중에 이미 재귀를 이용해 구현이 되어 있는 것들이 많다. (이진트리, BSP, 퀵정렬, 병합정렬)

재귀는 점화식이 중요하다. - 피보나치, 팩토리얼을 생각 했을 때 작고 단순한 케이스에서 점차 크기를 키워가며 점화식을 찾는다. 점화식을 찾고 그 점화식을 구현하다 보면 재귀 함수를 설계가 가능하다.

재귀를 잘하는 방법에는 정답은 없다. 단지 많이 풀어보고 점화식을 찾아보아라 점화식을 찾기 위해 문제 사이즈를 줄이고 단순화하라

백준 16505 별

https://www.acmicpc.net/problem/16505

n = int(input())
size = 2 ** n
board = [[' ' for _ in range(size)] for _ in range(size)]


def recursion(x, y, size):
    if size == 1:
        board[x][y] = '*'
        return
    else:
        half = size // 2
        recursion(x, y, half)
        recursion(x + half, y, half)
        recursion(x, y + half, half)

recursion(0, 0, size)

for i in range(size):
    print(''.join(board[i]).rstrip())

크래프톤 정글 8기 알고리즘 1주 차 문제 중

https://www.acmicpc.net/problem/1074

이 문제를 풀어보고 처음 이해하는데 많은 시간이 걸렸다. 하지만 동료들과 학습하며 개념을 이해했고 비슷 한 문제인 별 문제를 풀어보았다. 이 문제 역시 Z 문제와 같이 공간을 쪼개가며 작은 단위로 줄여가고 제일 작은 1 X 1 크기의 케이스에서 문제를 이해하며 재귀를 사용하였더니 풀어낼 수 있었다.

백준 1780 종이의 개수

https://www.acmicpc.net/problem/1780

import sys
input = sys.stdin.readline

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

def check_same_paper(x, y, n, data):
    for i in range(x, x+n):
        for j in range(y, y+n):
            if paper[i][j] != data:
                return False
    return True

zero_count = 0
one_count = 0
minus_one_count = 0


def recursion(x, y, n):
    global zero_count, one_count, minus_one_count
    if check_same_paper(x,y,n,paper[x][y]):
        if paper[x][y] == 0:
            zero_count += 1
        elif paper[x][y] == 1:
            one_count += 1
        else:
            minus_one_count += 1
    else:
        three = n//3
        d_three = three + three
        recursion(x, y, three)
        recursion(x + three, y, three)
        recursion(x + d_three, y, three)
        recursion(x, y + three, three)
        recursion(x + three, y + three, three)
        recursion(x + d_three, y + three, three)
        recursion(x, y + d_three, three)
        recursion(x + three, y + d_three, three)
        recursion(x + d_three, y + d_three, three)

recursion(0,0, num)
print(minus_one_count)
print(zero_count)
print(one_count)

이 문제 역시 비슷한 유형의 문제였다. 결국 문제를 작게 쪼개서 그 작은 케이스에서의 동작을 생각하니 해결할 수 있는 문제였다.

백준 1992 쿼드트리

https://www.acmicpc.net/problem/1992

n = int(input())

screen = [list(input()[:]) for _ in range(n)]

def check_same_num(x, y, n, bw):
    for i in range(x, x+n):
        for j in range(y, y+n):
            if screen[i][j] != bw:
                return False
    return True


def recursion(x, y, n):
    if check_same_num(x, y, n, screen[x][y]):
        return screen[x][y]
    else:
        half = n//2
        temp = "("
        temp += recursion(x, y, half)
        temp += recursion(x, y+half, half)
        temp += recursion(x+half, y, half)
        temp += recursion(x+half, y+half, half)
        temp += ")"
    return temp

print(recursion(0, 0, n))

쿼드 트리 문제 역시 위에서 소개한 문제들과 유사하다. 이 외에도 2630 색종이 만들기도 있다.

핵심은 재귀를 잘 설계하기 위해 문제를 작게 쪼개고 단순화한다는 것을 오늘 몸소 느꼈다. 그리고 확실히 이해를 위해 비슷한 유형의 문제들을 풀어보며 해당 유형의 문제의 감을 익힐 수 있었다는 것이다. 막막했던 알고리즘 공부에 방향이 조금씩 잡히고 있는 것 같다. 내일 10일 차에는 알고리즘 시험이 있는데 해당 시험을 잘 볼 수 있었으면 하는 바람이다.