0712: 파이썬 알고리즘

복습한 내용:

deque를 이용한 bfs 풀이

 

https://www.acmicpc.net/problem/2468

 

이 전엔 dfs로 풀었다가, bfs로도 풀어보았다. 확실히 파이썬이 자바보다 편한 게 실감이 났다.

또한 Counter, Generator, 슬라이싱 등... 구현하기 편한 요소가 많았다. 

 

다만 N-Queen 문제에서 JIT를 사용하는 pypy이 아니라 python3으로 제출하면 시간 초과가 발생하는 이슈가 있었는데,  내 코드를 더 개선해서 python3으로 돌아가게 할 수 있을지는.... 복습할때 도전해봐야겠다.

 

import sys
input = sys.stdin.readline

N = int(input())
cnt = 0
cols = [0] * N
visited = [False] * N  # 열 방문 체크

def check(r, c):
    # 열 체크는 visited로 이미 했으니 대각선만 체크
    for i in range(r):
        if abs(i - r) == abs(cols[i] - c):
            return False
    return True

def bt(row):
    global cnt
    if row == N:
        cnt += 1
        return
    
    for col in range(N):
        if not visited[col] and check(row, col):
            visited[col] = True
            cols[row] = col
            bt(row + 1)
            visited[col] = False

bt(0)
print(cnt)

 

 

https://www.acmicpc.net/problem/10819

https://www.acmicpc.net/problem/10971

 

이런 문제도 백트래킹을 연습하기 좋았다. 36문제를 하루만에 풀다보니 제대로 못 파고든 문제도 꽤 있어서 복잡도 관련해서 공부도 하고 의미있었다.

 

알고리즘 뿐 아니라 CS-APP의 Ch1도 공부했는데, 개괄적인 내용이었지만 이후에 있을 운영체제 폭탄을 조금이나마 덜 아프게 맞으려 이것저것 공부해보았다. 이전에 학부에서 공부한 고급시스템프로그래밍, 마이크로프로세서, 운영체제 등의 과목이 전부 나오기 시작하는데 이미 2년 넘게 자바 공부를 한 내겐 C와 어셈블리의 원리를 이해하기가 빡셌다.....

현재는 C언어가 실행되는 방식, CPU의 내부 구성 요소와 각 요소가 통신하는 방법, 각 하드웨어와 메모리 계층 구조 까지 봤는데 쉽지 않음을 느꼈다. 내일은 일요일인데 아마 못쉬고 계속 cs-app을 파지 않을까.... 자바 공부도 계속 해야하는데 흑흑