복습한 내용:
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을 파지 않을까.... 자바 공부도 계속 해야하는데 흑흑
'크래프톤정글10기 > 파이썬' 카테고리의 다른 글
| [백준/G2] 가운데를 말해요 (0) | 2025.08.22 |
|---|---|
| [백준/G4] 스도쿠 (1) | 2025.08.18 |
| [백준/G3]소문난칠공주 (2) | 2025.08.16 |
| DP + 그리디 과제 정리 (4) | 2025.08.06 |
| 파이썬으로 이해하는 트리,그래프 (3) | 2025.07.25 |