3주차

코딩테스트와 실무 역량 모두 잡는 알고리즘 스터디(Python반)에 참여한 내용을 정리했다.

3주차의 주제는 searching으로 조합과 백트래킹에 관련된 문제들을 풀었다.

N-Queen

처음 퀸을 놓았을 때 움직일 수 있는 모든 방향을 미리 표시해서 다음 퀸이 그 자리에 올 수 없도록 하는 기괴한 풀이를 생각했다.

하지만 더 간단한 방법이 있었다.

• 각 row의 col을 저장하는 1차원 배열을 사용한다.
• 첫번째 row부터 퀸을 놓으려는 전 row까지 각 열과 놓으려는 자리를 비교하면서 같은 열인지, 대각선인지 확인한다.

def possible(queen, row):
    for i in range(row):
        if queen[i] == queen[row] or abs(queen[i] - queen[row]) == row - i:
            return False
    return True

하노이의 탑

출발지, 경유지, 도착지 3개의 기둥을 두고 재귀하며 해결한다.

가지치기에 대해 생각해볼 수 있었다.

• n -1 개를 경유지로 옮긴다.
• n번째 원판을 도착지로 옮긴다.
• n -1 개를 도착지로 옮긴다.

def hanoi(n, from_, to_, through_, answer):
    if n == 1:
        answer.append([from_, to_])
        return
    hanoi(n - 1, from_, through_, to_, answer)
    answer.append([from_, to_])
    hanoi(n - 1, through_, to_, from_, answer)
    return answer

재귀 함수를 이해하는 게 어려울 경우 stack으로 바꿔서 생각해보면 더 쉽게 이해할 수 있다는 조언을 받았다.

한 문제를 BFS와 DFS 등 여러 방향으로 푼 코드를 올려주셔서 도움이 많이 됐다.