get_k 문제 2

2022.03.01 - [알고리즘] - (내가 붙인 이름) get_k 문제 1

(내가 붙인 이름) get_k 문제 1

먼저 앞서 살펴본 get_k 문제에 대해 고찰을 이어나가보자.

 

 

get_k 문제에 대한 고찰

 

반복 수행 - 반복문 vs 재귀 함수

get_k 코드의 기반이 되는 코드는 수행을 N번 반복하는 코드이다. 반복 수행 코드는 for와 while을 사용한 반복문과 함수 내에서 함수 자신을 호출하는 재귀 함수로 구현 가능하다. 이 중에서 동적으로 N개의 반복문이 중첩되어 있는 코드를 구현하기 위해 재귀 함수로 구현하였다.

 

get_k 문제 역시 0 ~N번 수행을 반복해야되기 때문에, N번 반복하는 코드를 구현해야하고, 마찬가지로 재귀 함수로 구현하였다. 여기에 k번째 수행에서는 이전까지의 수행, 0 ~ k - 1번째의 수행를 참조하도록 하는 코드를 추가하면 된다.

 

 

이전 수행 참조

앞서 예시로 살펴본 0 ~ 9 숫자 중 N개 조합하여 오름차순으로 출력하는 문제에서는 이전 수행들을 참조할때에 직전의 숫자(prev_number)보다만 큰 숫자를 선택하면 되었다.

 

유명한 N-Queen 문제에서는 이전 수행을 참조하는 코드는 어떻게 구현하면 될까? 현재 놓고자 하는 행과 열 그리고 대각선에 퀸이 놓여있는지 확인하면 된다. 매번 체스판을 순회하여 판별할수도 있고, DP를 적용하여 판별할수도 있다. N이 큰 N-Queen 문제에서는 매번 체스판을 순회하여 판별하면 시간초과가 나므로, DP지만 간단하므로 DP를 적용해보자.

 

---

get_k 문제 적용: N-Queen (with DP)

 

기본 코드 구조

def solution(N):
    field = [[0] * N for _ in range(N)]
    def check(r, c):
        ...
    def get_k(k, prev_number):
        if k == N:
            print(field)
        else:
            for col in range(N):
                if not check(k, col): # k == row
                    continue
                field[k][col] = 1
                get_k(k + 1)
                field[k][col] = 0 # 반드시 필요하다.
    get_k(0) # 초기화: 2번째줄에서 field 각각 -1로 초기화

아직 DP를 고려하지 않은 기본 코드 구조를 먼저 작성하였다. 해당 코드에서는 get_k 함수는 k번째 행에 놓일 퀸말의 열 위치를 선택하고 있다. 해당 row & col에 놓을 수 있는지 True / False를 반환하는 check 함수를 구현했다고 가정하였다. 이렇게 작성된 코드는 매번 해당 row & col에 놓을 수 있는지 field를 순회하며 판별해야되기 때문에 비효율적이다.

 

DP 적용 코드

def solution(N):
    col_used = [-1] * N
    dia_used1 = { x: 0 for x in range(-N + 1, N} }
    dia_used2 = { x: 0 for x in range(0, 2N -1} }
    def get_k(k):
        if k == N:
            print("".join(col_used))
        else:
            for col in range(N):
             # 열, 대각선 10-4방향, 대각선 2-8방향 체크
            if col_used[col] != -1 or dia_used1[k - col] or dia_used2[k + col]:
                continue
            col_used[col] = k
            dia_used1[k - col] = 1
            dia_used2[k + col] = 1
            get_k(k + 1)
            col_used[col] = -1 # 반드시 필요하다.
            dia_used1[k - col] = 0 # 반드시 필요하다.
            dia_used2[k + col] = 0 # 반드시 필요하다.
    get_k(0) # 초기화: 2~4번째줄에서 각각 초기화

판별은 행 & 열 & 대각선(10-4) & 대각선(2-8) 네 가지가 필요하다. get_k 코드는 행에 대해서 순차적으로 진행되므로 판별에서 제외해도 된다. 열에 대한 판별은 col_used 리스트를 하나 선언하여 활용한다. 단순히 0과 1로서 사용여부를 체크 할 수 도 있지만, 값에 행값과 동일한 k값을 주어 정답 출력에 활용할 수 있다. 각 대각선에 대한 판별은 dia_used 딕셔너리를 2개 선언하여 활용한다. 딕셔너리의 key값으로는 각각 (행 - 열)값과 (행 + 열)값을 사용하였다. 이는 대각선(10-4)은 각 원소에 대해 (행 - 열)값이 동일하고, 대각선(2-8)은 각 원소에 대해 (행 + 열)값이 동일하다. 즉, 각 대각선을 고유하게 표현할 key값으로서 (행 - 열)값과 (행 + 열)값을 사용한 것이다.

 

코딩 테스트에서 활용한 get_k 코드

작년 하반기 카카오 블라인드 공채 4번 양궁대회 문제에서 get_k 코드를 적용하여 풀이하였다. k점짜리 과녁판에 맞힐 화살의 수를 선택하는 방식으로 구현하였다.

def solution(n: int, info: list) -> list:
    path: list = [0] * 11
    answer: list = [0] * 11
    max_answer: list = [0]
    def set_answer() -> None:
        for i in range(11):
            answer[i] = path[i]
    def my_cmp() -> int:
        for i in range(11):
            if answer[10 - i] != path[10 - i]:
                return path[10 - i] - answer[10 - i]
        return 0
    def get_k(k: int, arrow: int, score: int) -> None:
        if k == 0:
            if score <= 0 or score < max_answer[0]:
                return
            path[10 - k] = arrow
            if score > max_answer[0]:
                max_answer[0] = score
                set_answer()
            elif score == max_answer[0] and my_cmp() > 0:
                set_answer()
            path[10 - k] = 0
            return
        get_k(k - 1, arrow, score - k if info[10 - k] else score)
        if arrow >= (info[10 - k] + 1):
            path[10 - k] = info[10 - k] + 1
            get_k(k - 1, arrow - (info[10 - k] + 1), score + k)
            path[10 - k] = 0
    get_k(10, n, 0)
    return answer if max_answer[0] else [-1]

---

마지막 고찰 : DFS

위 get_k 코드에는 재귀호출전에 col_used등의 값을 변경하고, 재귀호출된 함수가 종료되면 다시 col_used등의 값을 원래 값으로 돌려놓는다. 이게 왜 되는지 의문인 동료들이 많았고, 나 또한 처음 재귀함수를 배우고 사용할 때, 이게 왜 되지 싶었다. 이것을 트리(⊂그래프)와 트리를 순회하는 DFS를 통해 설명하고자 하였다.

 

get_k 코드에서 k를 트리의 깊이, 각 노드가 k번째 수행에서 선택할 경우의 수라고 생각할 수 있다. k번째 어떤 수행(a라고 하겠다)을 하였다면, 해당 노드(k)의 자식 노드(k + 1)에서 대해서 순회가능한 노드를 순회한다. (즉, k + 1번째 수행을 한다.) 모두 순회하였으면, 비로소 k번째 수행(a)가 아닌 다른 수행(b라고 하겠다)을 한다. 마찬가지로 자식 노드에 대해서 모든 순회가능한 노드를 순회를 한다. 더 이상 가능한 k번째 수행이 존재하지 않는다면, 부모 노드(k - 1)번째에서 다음 순회를 시작한다.

즉, N-Queen 문제에서 (0,0), (1, 2), (2, 4)에 퀸말을 두었다면, 해당 퀸말은 건드리지 않은 채, 3번째 행(k)부터 수행을 이어나간 뒤, 모든 가능성을 수행한 뒤, (2, 4)에 두었던 퀸말부터 물러서 다음 가능성을 찾아 수행을 이어나간다.