정글 5일차

정글 5일차 알고리즘 주차가 시작되었다.

오늘 배운 것들

1. 소수찾기(1978)

문제 자체는 어렵지 않지만 사소한 문제가 있었다.

for i in range(2, round(math.sqrt(n)+0.5)):
    if n % i == 0:
        result -= 1
        break

올림 처리를 하기 위해 제곱근에 0.5를 더해 주었는데 제곱근이 정수인 경우에 올림이 되는 경우도 있고 내림이 되는 경우도 있었다.
파이썬 등 여러 언어에서는 반올림 방식으로 Bankers' Rounding(Round Half to Even)방식을 사용한다.
소수부가 .5인 경우 짝수에 가까운 쪽으로 반올림된다.

round(2.5)==2
round(3.5)==4

소수부가 .5인 숫자가 아주 많은 경우 반올림은 양수방향으로 편향, 반내림은 음수방향으로 편향되기 때문이라고 한다.
또 하필 짝수방향으로 처리하는 이유는 아마 다시 2로 나누는 경우를 고려한 것 같다.

2. 하노이 탑(1914)

이미 푼 적 있는 문제다.
1개 원반의 하노이 탑에 대해서는 답이 아주 간단하게 나온다.

1개: 원반을 목적지 파이프로 옮긴다.

n(n>1)개 원반의 하노이 탑을 해결하는 알고리즘을 아주 단순화한다면 다음과 같다.

n-1개의 탑을 목적지가 아닌 파이프로 옮긴다.
남은 n크기의 원반을 목적지 파이프로 옮긴다.
n-1개의 탑을 목적지 파이프로 옮긴다.

그렇다면 n-1개의 탑은 어떻게 옮길까

n-2개의 탑을 목적지가 아닌 파이프로 옮긴다.
남은 n-1크기의 원반을 목적지 파이프로 옮긴다.
n-2개의 탑을 목적지 파이프로 옮긴다.

이런 식으로 뒤에 수행해야하는 작업이 먼저 해결되어야 앞선 작업도 완료되는 경우에 반복문 대신 재귀함수를 사용하면 풀이가 간단해진다.
파이썬으로 구현하면 다음과 같다:

def hanoi(n :int, frm :int, to :int) -> list[str]:
    _result = []
    temp = 6 - frm - to
    if n==1:
        _result += [f"{frm} {to}"]
    else:
        _result += hanoi(n-1, frm, temp)
        _result += [f"{frm} {to}"]
        _result += hanoi(n-1, temp, to)
    return _result

3. N-Queen(9663)

오늘의 피눈물 담당이다.
시간복잡도를 고려하지 않더라도 첫 정답(n=6일 때부터 10초를 넘겼다.)을 내는데 1시간 반이 걸렸다.
3시간동안 다듬었다. 그래도 n=12부터 10초를 넘겼다.
1시간 더 고민하다가 못 참고 인터넷을 찾아봤다.
solve.ac기준 난이도 골드4로 하노이 탑과 1차이가 난다.
개인적으로 1밖에 차이가 안 난다는 게 문제자체보다도 이해가 안 된다.

두 가지 함수를 사용했다.
백트래킹을 실시하는 n_queen함수.
그리고 좌표를 입력받아 좌표에 퀸을 놓을 수 있는 상태인지를 판단하는 is_available함수.

3-1. 구현

먼저 n^2길이의 리스트를 입력받아, 퀸을 놓을 수 있는 칸은 1, 없는 칸은 0으로 표시하여 리턴하도록 만들었다.

def n_queen(board :list, n :int):
    if sum(board)==0:
        return 0
    elif n==1:
        return 1
    row = LENGTH-n
    
    cases = 0
    for i, available in enumerate(board[row*LENGTH:(row+1)*LENGTH], row*LENGTH):
        if available:
            copy = is_available(board, i)
            new_cases = n_queen(copy, n-1)
            cases += new_cases

    return cases
    
# 놓을 수 있는 칸을 0으로 바꿔 리턴하는 함수
def is_available(board :list, pos :int) -> list:
    copy = board[:]
    pos_row = pos//LENGTH
    pos_column = pos%LENGTH
    min(pos_row, pos_column)
    pos_diagonal_lr = pos - min(pos_row, pos_column)*(LENGTH+1)
    pos_diagonal_rl = pos - min(pos_row, LENGTH-1-pos_column)*(LENGTH-1)
    pos_diagonal_lr_row = pos_diagonal_lr//LENGTH
    pos_diagonal_lr_column = pos_diagonal_lr%LENGTH
    pos_diagonal_rl_row = pos_diagonal_rl//LENGTH
    pos_diagonal_rl_column = pos_diagonal_rl%LENGTH
    # 가로 처리
    for i in range(pos_row*LENGTH, (pos_row+1)*LENGTH, 1):
        copy[i] = 0
    # 세로 처리
    for i in range(pos_column, LENGTH**2, LENGTH):
        copy[i] = 0
    # 대각선 처리(top-left to bottom-right)
    for i in range(pos_diagonal_lr,
                   pos_diagonal_lr+(LENGTH+1)*(min(LENGTH-1-pos_diagonal_lr_row, LENGTH-1-pos_diagonal_lr_column))+1, 
                   LENGTH+1):
        copy[i] = 0
    # 대각선 처리(top-right to bottom-left)
    for i in range(pos_diagonal_rl, pos_diagonal_rl+(LENGTH-1)*(min(LENGTH-1-pos_diagonal_rl_row, pos_diagonal_rl_column))+1, LENGTH-1):
        copy[i] = 0
    return copy

시간 초과가 나왔다. 문제는 is_available함수의 for문에 있었으나 당시엔 몰랐다.
아래와 같이 보드에 놓여진 퀸의 위치만을 이용하여 놓을 수 있는지를 리턴하는 함수를 다시 만들었다.

def is_available(positions, queen):
    queen_row = queen//LENGTH
    for pos in positions:
        pos_row = pos//LENGTH
        if abs(pos-queen)%LENGTH==0:
            return False
        elif pos-queen == (pos_row-queen_row)*(LENGTH+1):
            return False
        elif pos-queen == (pos_row-queen_row)*(LENGTH-1):
            return False
    return True
def n_queen(positions :list, n :int):
    if n==0:
        return 1
    row = LENGTH-n
    
    n_cases = 0
    for i in range(row*LENGTH, (row+1)*LENGTH):
        if is_available(positions, i):
            new_positions = positions + [i]
            new_cases = n_queen(new_positions, n-1)
            n_cases += new_cases

    return n_cases

성능은 비슷했다.
더 고민해도 답이 안 나와 인터넷을 찾아봤다.

def is_unavailable(pos):
    row, col = pos
    # 세로체크
    if col in banned_col:
        return True
    if row+col in banned_cross_0:
        return True
    if row-col in banned_cross_1:
        return True
    return False

def n_queen(row):
    if row>=LENGTH:
        return 1
    
    n_cases = 0
    for col in range(LENGTH):
        if is_unavailable((row, col)):
            continue
        banned_col.add(col)
        banned_cross_0.add(row+col)
        banned_cross_1.add(row-col)
        
        n_cases += n_queen(row+1)
        
        banned_col.remove(col)
        banned_cross_0.remove(row+col)
        banned_cross_1.remove(row-col)
    
    return n_cases

row-col, row+col 만으로 동일 대각선에 있는지 판단할 수 있다.
굳이 놓여진 퀸의 정보를 다 저장할 필요 없이 대각선 정보만 저장하고 놓으려는 위치의 대각선과 비교만 하면 된다.
정보를 가공한 셈인데 혼자서는 절대 떠올리지 못 했을 것 같다.

3-3. 백트래킹

사실 맨 처음에는 DFS로 구현해 시간이 더 오래 걸렸다.
하위 트리에 해가 존재하지 않는 경우에는 바로 중단하도록(가지치기) 수정했는데 찾아보니 이를 백트래킹이라고 부른댄다.
DFS랑 구분하는 이유가 무엇인가 했는데, 다른 탐색 알고리즘에서도 해가 존재하지 않을 때 돌아가도록 한다면 백트래킹이라고 하니 부분집합의 관계는 아니다.