크래프톤 정글 1주차 WIL

WIL: Weekly I Learned; 또는 What I Learned This Week

정글의 설경

겨울입니다. 시간이 흘러 정글 캠퍼스에도 첫눈이 내렸습니다.가 아니라 세상에, 3월에 이런 함박눈을 보게 될 줄은 몰랐습니다. 이런 광경은 2월 중순이었던가, 마지막으로 봤던 것 같은데, 그때만 해도 이런 눈을 다시 보려면 내년까지 기다려야겠지, 했지요. 또 볼 줄이야! 너무나 반가웠습니다.

알고리즘 입문

크래프톤 정글의 새로운 주(週)의 시작은 항상 목요일입니다. 이전 포스트에서 설명한 0주차 미니 프로젝트가 끝나고, 저희는 새로운 팀을 배정받게 되었습니다. 정글 이외의 프로그램에서 구하기 어려운 것 중 하나가 바로 컴퓨팅 이론에 대한 동료 학습일 것입니다. 이번 1주차에서 저희는 3인 1팀으로 커리큘럼을 따라가고, 매일 1회 이상의 '코어 타임'을 통해 동료들끼리 각자 학습한 내용과 작성한 코드의 결과물들을 서로 공유하고 리뷰하였습니다. 감사하게도, 이번에 새로이 구성된 팀원들 역시 학습에 너무나도 적극적인 자세로 참여해주셨습니다.

이번 1주차는 알고리즘에 입문하는 시간이었습니다. 정글에서 제가 가장 기대했던 것 중 하나입니다. 컴퓨터 관련하여 독학할 때 개인적으로 가장 힘들었던 것이 바로 알고리즘과 자료구조였는데, 정글에서는 몰입과 동료 학습을 통해 Python의 기본 문법과 반복문을 이용한 구현으로부터 시작하여 재귀, 정렬, 완전탐색까지 파헤칠 수 있었습니다.

동료 학습

구체적으로 백준 9663번 N Queen 문제를 들 수 있겠습니다. 어찌저찌 문제의 타당한 접근법은 깨우쳤지만, 알고리즘의 A도 모르던 제가 재귀의 필요성에 대해서 이해할 턱이 없었습니다. 그래서 나온 첫 번째 결과물은 아래와 같았습니다. (참고: 안 돌아갑니다 - 백트래킹 적용하다가 실패)

def pi_board():
    for b in board:
        print(b)
    input()
    
init_size = int(input())
board = [[False for _ in range(init_size)] for _ in range(init_size)]

# 각 row마다 반복
row = 0
prev_col = []
# 이전 column 기억
while True:
    # Q 놓기 - 모든 row, col, 대각선으로도
    col=0
    while True:
        # 놓을 수 없으면 생략
        if board[row][col] == True: continue
        
        # 이 row의 모든 col이 True면 포기, 1 row 후퇴, 1 col 생략
        gave_up = True
        for col in board[row]:
            if board[row][col] == False: gave_up = False
        if gave_up == True: 
            board[row-1][prev_col.pop()] = True
            row = row-1
            continue;

        # 놓기 핵심 - 일단 현재 col 기억
        prev_col.append(col)

        # row 전체
        board[row] = [True]*init_size
        # col 전체
        for i in range(init_size):
            board[i][col] = True
        # 대각선 전체
        for i in range(init_size):
            pi_board()
            # 우하향 대각선
            # i 증가
            if not( (row+i) > (init_size-1) or (col+i) > (init_size-1) ): 
                print(f"i b{row+i} {col+i}")
                board[row+i][col+i] = True
            # i 감소
            if not( (row-i) < 0 or (col-i) < 0 ): 
                board[row-i][col-i] = True

            # 우상향 대각선
            # 증,감
            if not( (row+i) > (init_size-1) or (col-i) < 0) : 
                board[row+i][col-i] = True
            # 감,증
            if not( (row-i) < 0 or (col+i) > (init_size-1)) : 
                board[row-i][col+i] = True
        input("COL DONE")
        col +=1
        if col >= init_size: break

    row +=1
    if row >= init_size: break
print(board)

저런 60줄이 넘어가는 3중 반복문을 짜다가 PTSD가 도졌습니다. 바로 제가 신입 채용 코딩테스트를 보던 때가 딱 저랬기 때문입니다. 보통 3문제씩 출제되는데 1번은 웬만하면 단순 구현이라 적당히 짜졌고, 2번을 풀 때 저런 식이었습니다. 저렇게 60줄 100줄씩 넘어가는 (엉망진창인) 코드 만든다고 2시간씩 쏟아붓다가, 운 좋게 돌아가면 그대로 제출하는 거고, 나쁘면 그냥 포기하고 마는 것입니다. 3번 문제는 아예 시도조차 못하는 경우가 대부분이었습니다.

하지만 저는 이번 동료 학습을 통해 문제에 대한 다른 접근 방식을 터득할 수 있었습니다. 바로, 저런 문제에 대해서는 반복문을 지양하고 재귀를 통해 문제를 푸는 것입니다. 팀원들은 각자 본인들이 작성한 재귀를 통한 접근법을 설명해주셨고, 그제서야 저는 알고리즘에 대한 새로운 관점을 터득할 수 있었습니다. 재귀. 재귀가 바로 첫 봉우리였습니다. 단순히 문제의 내용을 기계처럼 구현하려 드는 것이 아니라, 문제로부터 패턴을 간파해야 이를 기반으로 수도코드(또는 점화식)를 도출할 수 있고, 이것이 있어야만 비로소 제대로 된 해결법을 작성할 수 있었던 것입니다. 개인적으로 이것을 깨닫기까지 넘어야 했던 봉우리가 바로 재귀였습니다. 동료 학습이 없었다면 얻지 못했을 인사이트일 것입니다.

위 N Queen 문제는 어떻게 되었을까요.

input_n = int(input().strip())

count = 0 # 결과
col = [0] * input_n  # 각 행의 퀸의 열 번호의 리스트

# is_safe는 지금 퀸을 놓을 후보 행(=row)과 컬럼(=c)를 받아, 이전에 놓은 퀸들을 하나하나 순회하며 안전한지 검사
def is_safe(row, c):
    result = True
    for i in range(row): # 이전 행들의 퀸들과 충돌하는가? 충돌 즉시 False
        if col[i] == c or abs(col[i] - c) == row - i: # abs(col[i]-c)==row-i ==> 이전 퀸과, 놓으려는 새 퀸의, 행 차이 == 컬럼 차이
            return False
    return result

def backtrack(row):
    global count
    if row == input_n: # 베이스 조건 - 모든 행에 퀸을 놓았으므로
        count += 1
        return
    for c in range(input_n): # c: 현재 행에 놓을 후보 컬럼 번호
        if is_safe(row, c): # is_safe()가 모든 컬럼에서 False면 backtrack()이 호출되지 않음 ==> 자연스럽게 다음으로 넘어감
            col[row] = c
            backtrack(row + 1)

backtrack(0) # 0번째 row부터 시작
print(count)

재귀로 접근하니, 구현하다가 만 백트래킹까지 저렇게 간단하게 끝났습니다. 2차원 보드를 1차원으로 줄인 것은 덤입니다.

갈 길은 멀다

크나큰 깨달음을 주는 한 주였지만 이는 그저 시작일 뿐, 저는 여전히 병아리입니다. 게임으로 치자면 마치 튜토리얼을 끝낸 레벨 1짜리 뉴비나 다름없습니다. 앞으로도 이분탐색, 분할정복, 그래프, DFS(깊이 우선 탐색), BFS(너비 우선 탐색), 위상정렬(방향 그래프에서 노드 정렬하기), 다이나믹 프로그래밍(기억시키며 풀기), 그리디 알고리즘(매순간 최적해로써 해결하기)과 같은 그냥 읽기만 해도 무시무시한 것들이 저를 마주하고 있습니다. 이외에도 저를 기다리는 C 기반 자료구조 구현, 레드-블랙 트리, 말록(malloc) 랩, PintOS와 같은 것들 모두, 제가 컴퓨터과학으로부터 한 발짝 비켜나 있을 때 제 친구들이 학부에서 비명을 지르며 수행했던 과제들입니다. 피하고 싶었지만, 그래서 여태까지 피해왔지만, 피할 수 없었습니다. 제가 꿈꾸었던 모든 커리어 패스는 이를 요구하고 있습니다. 이제 더 이상 물러날 곳은 없습니다.

어제 알고리즘 특강을 해주신, 게임랩 코치님께서는 알고리즘 문제 팁으로 아래와 같이 말씀하셨습니다.

• 문제의 사이즈를 줄여라. 예: n개 => 3개로 줄이기, 단순화시키기.
• 점화식은 작은 문제들이 모여 큰 문제를 이루는 것.

인생도 어쩌면 이와 다르지 않을 수 있겠습니다. 커다란 문제들이 산적해 있는 것은 정글뿐만 아니라 우리네 인생도 마찬가지이며, 이것이 모여 사회로 이어집니다. 그렇지만, 그럴수록, 제가 풀 수 있는 그 작은 조각부터 찾아내어 해결해봅니다. 그저 문제가 하나하나 풀릴 때마다 느껴지는 유포리아만이 저를 앞으로 나아가게 할 뿐입니다.