WEEK01 알고리즘 TIL(3월17일 월요일)

https://github.com/prtky/JungleBackjoon
해당링크를 들어가면 코드와 주석만 보실수 있습니다.

점심식사를 하기전 오전시간에는 퀴즈나 시험 등을 제출할 깃허브 세팅법에 대해 알아보았다. 코치님께서 깃허브의 전체적인 로직이나 세팅 방법을 상세히 알려주셨다.

맛있는 돼지갈비찜을 먹고 알고리즘을 풀려했으나 코치님과 팀별 면담이 있어 면담을 진행했다. 1주일간 지나가면서 느낀점, 지원동기, 예상과 달랐던점/개선점 등에 대해 이야기 해보았다. TIL을 정리하는 포스팅이니 자세히 이야기하지는 않겠다.

★★★ 27번 문제(9663)N-Queen

팀원 분과 규칙에 대해 이야기를 했다. 수기로 직접 돌려보면서 규칙을 찾고 있는데 알듯 말듯하다…
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하면된다. 나는 직접 경우의 수를 적어보았다. 해보니 퀸은 같은 행과 열에 있으면 안된다. 그러기 위해서는 퀸은 한 행이나 열에 한개씩은 있어야함을 의미합니다. 근데, 대각선은 어떻게 처리를 하는지 아이디어가 떠오르지 않는다.
N=5까지 확인해보니 경우의 수는 10이다. 나느 1번 퀸을 고정하고 나머지 인자를 옮기면서 조사했다. 0,0지점의 1번퀸에서 경우의 수가 다 나오면 1,2로 옮겨서 스캔하고 옆으로 옮겨서 다시스캔하는 방식으로 했다. 뭔가 이 재스캔하는 방법을 재귀 알고리즘으로 짜면 될 것 같은데, 어떻게 시작할 지 아직 모르겠다.
하는 방식이 N 개에 해당되는 리스트를 모두 0으로 채운다. 이후 만약에 퀸을 놓지 못하는 부분이면 1로 바꾼다. 오른쪽 상하단으로 지나가는 것은 i+j일때이고, 왼쪽 상하단으로 지나갈 때는 i-j가 일정할 때이다. 지나가지 못하는 경우의 수를 lookup 테이블로 해서 제외시켜 결론을 도출한다.
N = 전체행 번호
n = 현재행 번호
전체 행의 시작이 0,0에서 시작하므로 마지막 줄은 n-1이다.
n = N 이라면 결과에 +1을 한다.
V1 = 열인 j의 해당되며 열의 위치를 표시한다. 해당 열에 해당되지 않게 설정하기 위해 사용한다.
V2 = 오른쪽 대각선인 i + j에 대해 표시한다.
V3 = 왼쪽 대각선인 i - j가 일정한 것에 대해 표시한다.
V1,2,3에 해당하는 칸을 1로 바꾼다.
lookup 테이블 참조를 통해서 구현한다. V1, V2, V3를 빠르게 공제
만약 칸에 0이라면 모든 조건에 만족하는 경우이다.

# 일단 해당 문제의 N 입력단을 쓴다.
def dfs(n):
    global ans
    if n == N:
        ans+=1
        return
    
    for j in range(N):
        if V1[j] == V2[n+j] == V3[n-j] == 0:
            V1[j] = V2[n+j] = V3[n-j] = 1
            dfs(n+1)
            V1[j] = V2[n+j] = V3[n-j] = 0
        
        
N = int(input())

ans = 0 # 나중에 답이 될 ans은 0으로 초기화한다.
 
V1 = [0] * N
V2 = [0] * (2*N)  # 대각선 계산 오른쪽위
V3 = [0] * (2*N)  # 대각선 계산 왼쪽위

dfs(0)
print(ans)

느낌상 퀸 시점에서 퀸의 열, 대각선 두개의 경우를 고려하여 작성하는 것 같다. 그러나 이건 다음에 다시 한번 보는 걸로 하겠다. 시간을 너무 잡아 먹기도 했고, 다른 팀원의 도움을 받아 작성하고 이해했기 때문에 나의 코드가 아니다. 일단 목표가 전체 문제를 풀어보는 것이고 내일 화요일 퀴즈로 퀵정렬과 컴퓨터 시스템에 대해 다시 공부해야하기 때문에 오늘은 어느정도 이해한 상태로 넘어 가겠다.

N-퀸 문제를 풀어보고 있으니 금방 저녁시간이 다가왔다. 코치님과 합석을 해서 여러가지 이야기를 하고 교육장으로 돌아왔다. 내일 퀴즈에 퀵솔트에 대해 나온다고 하여 개인 공부 후 팀원들과

퀵솔트

일단 퀵솔트 내용에 앞서, 퀵솔트 방식이 굉장히 많은데, 해당 포스팅 중 책에 나오지 않은 내용을 다뤘다. 시간이 남으면 내용을 보충하겠지만, 이런 식의 퀵솔트 방식이 있구나로 알아두면 좋을 것 같다. 나도 다른 팀원분들이랑 푸는 방식이 달라서 의견을 주고 받았던 기억이있다.
일단 오늘 낼 퀴즈에 나온다고 하는 퀵솔트에 대해서 알아봐야한다. 팀원 회의전 정리를 해보았다.
예시를 들어 설명하겠다.

pl

648257913

                                     pr

왼쪽을 pl(left) 오른쪽을 pr(right)라고 합니다.

가운데 아무숫자를 피벗이라는 기준점으로 둡니다(보통 중앙). 여기서는 5를 피벗으로 두고 설명하겠습니다.

퀵소트의 기본원리는 pl부터 오른쪽으로 스캔하며 피벗값보다 큰 요소를 찾고, pr값에서 왼쪽으로 스캔하여 피벗값보다 작은 요소를 찾습니다. 그후 순차적으로 pl과 pr쪽의 숫자를 교환합니다.
왼쪽을 스캔해봅니다. pl에서 6이 5보다 크고 pr에서는 3이 5보다 작습니다. 6과 3을 교환합니다.

pl->

348257916

                                   <-pr

pl에서는 4는 건너뛰고 8, pr에서는 1이 교체가 되야합니다.

pl

348257916

                                     pr

pl에서는 없고, pr에서는 9,7 을 건너뛰고 피벗인 5에 도착하는데, 서로 교채할 게 없으므로 5는 그대로 두고 피벗 이상과 이하를 나눕니다.

pl

341257986

                                     pr

pl에서 2도, pr에서 8도 교체할 수 없으니 피벗 이하와 이상을 나눕니다.

pl

34125(고정)7986

                                     pr

이하와 이상을 나누어서 위의 과정을 반복합니다.

pl

34125(고정)7986

                                     pr

pr에서 4보다 작은 2는 교체 대상이다. 그러나 pl에서 충족되는 조건이 없어 교체 대상인 2에서 만나게 된다.
이렇게 되면 피벗인 2와 교체를 하고 피벗이었던 4는 고정이된다.

pl

34125(고정)7986

                                     pr

4 이상인 피벗 이상이 존재하지 않으므로 3,2,1만 퀵솔트를 하면된다. 2를 피벗으로 지정한다.

1과 3을 서로 교체해야되므로 교체한다. 이후 2에서 만나므로 2는 고정이 되고, 정렬이 완료된다.(1~4)

pl

3214(고정)5(고정)7986

                                     pr

이제 피벗 이상부분의 정렬을 수행해보자. 피벗 9를 기준으로 6이 교체 대상이 되지만 pl은 조건 충족하는 부분이 없기 때문에(9보다 작으니) 6번에서 pl과 pr이 만나게 된다. 그러면 전과 같이 피벗인 9와 6이 교체되고 9가 고정된다.

pl

1234(고정)5(고정)7986

                                     pr

이제 7, 6, 8만 퀵솔트하면 된다. 6을 피벗으로 두고 비교 시 7은 교체대상이 되고(6보다 크니) pr과 7과 6사이에서 충돌난다. 그럼 충돌 지점에 두 부분 중 작은 값은 앞으로 보내며 퀵솔트를 다시하지만 6은 혼자 남으니 건 드릴 이유가 없다, 그리고 7과 8을 비교해서 7을 피벗 기준으로 8이 더 크니 그대로 답이 나온다.

pl

1234(고정)5(고정)7689(고정)

                                     pr

최종적으로 아래와 같이 오름차순으로 정렬된다.

pl

1234(고정)5(고정)6789(고정)

                                     pr

팀원분들과 퀵솔트에 대해서 학습을 해본 후 알게된 주의할 내용을 적어보겠다.

※ 주의점 ※
위의 경우로 할 때,
1. 퀵솔트 케이스가 두가지 케이스가 있다.
교제에 나온것 처럼 pl과 pr이 계속 진행하다가 피벗에서 만나게되서 피벗 이상과 이하가 나눠지고 다시 솔트하는 방법(여기서 피벗과 만난 값이 더 큰 수가 오른쪽으로 가야한다.)(여기선 피벗값도 포함해서 퀵솔트) 아니면 pl이나 pr에서 피벗값과 비교해서 교체 대상이되는데, 한 쪽에서 충족되는 조건이 없어서 교체대상까지 도달하여 pl과 pr이 충돌할 경우 피벗을 지나가서 교체 지점까지간다. 결국 pl과 pr이 만나게되는 지점이 발생되게 되는데, 해당 요소하고 피벗하고 교체를 한다. 그후 피벗이었던 값은 자리가 고정이된다. 고정된 지점을 기점으로 피벗이하와 이상으로 나뉘게 되고 계속해서 퀵솔트를 진행하면된다.(고정된 피벗값은 퀵솔트하지 않는다.)
2. 여기서 퀵솔트 재귀횟수에 대해서 물어볼수도 있는데, 횟수는 그림으로 봤을때 그룹이 나눠지면서 가지치기한 횟수를 세면 편하다.
3. 아래의 파이썬 코드에서 //2 로 피벗값을 정하기 때문에 1~4의 요소같이 짝수 요소만 남으면 2.5로 2의 자리에 있는 요소를 피벗값으로 지정한다.

퀵 솔트의 소스코드를 참고 하면 좋을 것 같다. 해당 코드는 위의 퀵솔트 방식과 다름을 유의해주세요.(x = a[(left + right) // 2] # 피벗(가운데 요소)를 보면 된다.)

from typing import MutableSequence

def qsort(a: MutableSequence, left: int, right: int) -> None:
    """a[left] ~ a[right]를 퀵 정렬"""
    pl = left                   # 왼쪽 커서
    pr = right                  # 오른쪽 커서
    x = a[(left + right) // 2]  # 피벗(가운데 요소)

    while pl <= pr:    # 실습 6-10과 같은 while 문
        while a[pl] < x: pl += 1          # 내림차순 시 교체 대상!!!!!!!!!!!!!!
        while a[pr] > x: pr -= 1          # 내림차순 시 교체 대상!!!!!!!!!!!!!!
        if pl <= pr:
            a[pl], a[pr] = a[pr], a[pl]
            pl += 1
            pr -= 1

    if left < pr: qsort(a, left, pr)
    if pl < right: qsort(a, pl, right)

def quick_sort(a: MutableSequence) -> None:
    """퀵 정렬"""
    qsort(a, 0, len(a) - 1)

if __name__ == '__main__':
    print('퀵 정렬을 수행합니다.')
    num = int(input('원소 수를 입력하세요.: '))
    x = [None] * num   # 원소 수가 num인 배열을 생성

    for i in range(num):
        x[i] = int(input(f'x[{i}]: '))

    quick_sort(x)      # 배열 x를 퀵 정렬

    print('오름차순으로 정렬했습니다.')
    for i in range(num):
        print(f'x[{i}] = {x[i]}')

해당 코드를 내림차순으로 정렬하려면 위 주석의 교체 대상의 비교 등호를 반대로 하면 된다.
내일부터는 시험치는 목요일까지 시간이 얼마 남지 않아 어려운 문제인 Z와 같은 문제를 건너뛰고 쉬운것과 복습을 위주로 알고리즘 학습을 할 예정이다.