개요
-7 // 3은 -2일까, -3일까?
Python에서는 -3이다. 이 한 줄 때문에 탐색 로직은 멀쩡한데 숫자 만들기를 틀렸었다..
오늘 푼 세 문제와 정리한 핵심 개념들
- SWEA 1231 중위순회: 자식이 하나면 왜 왼쪽인가, 답은 입력 순서가 아니라 완전 이진 트리
-
SWEA 4871 그래프 경로: 트리엔 없던
visited, 그리고 인접 행렬이 생각보다 느린 이유 -
SWEA 4008 숫자 만들기:
//한 줄짜리 오답과 Python이 일부러 내림을 고른 이유
덤으로 visited 없이 방향 그래프를 도는 칸( Kahn ) 알고리즘까지 배웠다.
중위순회 — children[0]이 왜 왼쪽인가
문제. 알파벳이 하나씩 들어 있는 이진 트리를 중위 순회한 결과를 출력한다.
- 입력: 테스트케이스 10개. 케이스마다 첫 줄에 정점 수
N, 이후N줄에정점 번호 알파벳 [왼쪽 자식] [오른쪽 자식]. 자식이 없으면 번호가 생략된다 - 트리는 완전 이진 트리 형식으로 주어진다
- 출력:
#테스트케이스번호 순회결과문자열
import sys
sys.stdin = open("input.txt", "r")
T = 10
class Node:
def __init__(self, num, value, *args):
self.num = int(num)
self.value = value
self.children = tuple(map(int, args))
def dfs(start):
cur_node = nodes[start]
if len(cur_node.children) == 0:
results.append(cur_node.value)
return
# 왼쪽 자식 먼저 순회
dfs(cur_node.children[0])
# 본인 값 저장
results.append(cur_node.value)
# 오른쪽 자식이 있다면 추가 순회 진행
if len(cur_node.children) > 1:
dfs(cur_node.children[1])
for test_case in range(1, T + 1):
# N = 노드(정점)의 수
N = int(input())
nodes = {}
results = []
for i in range(1, N + 1):
node = Node(*input().split())
nodes.setdefault(i, node)
dfs(1)
result = ''.join(results)
print(f"#{test_case} {result}")
자식이 하나면 children[0]을 왼쪽으로 썼다. 입력에서 왼쪽이 먼저 나오니까라고 생각했다.
그런데 AI가 “자식이 하나일 때 그게 왼쪽이라는 건 어떻게 아냐”고 되물었고, 거기에 답하다 보니 이유가 입력 순서가 아니었단걸 깨달았다. 입력은 자식이 하나면 번호를 하나만 줄 뿐이라 왼쪽인지 오른쪽인지 알려주지 않는다. 그래도 왼쪽이라고 가정할 수 있던 건 완전 이진 트리라서였다. 레벨 순서대로 빈 번호 없이 채우니까, 자식이 하나뿐인 노드는 오른쪽이 비는 수밖에 없었던 것 이다.
이 조건이 있으니 번호만으로 부모·자식을 계산할 수도 있다.
| 왼쪽 자식 | 오른쪽 자식 | 부모 | |
|---|---|---|---|
| 1번부터 시작 | 2i |
2i+1 |
i//2 |
| 0번부터 시작 | 2i+1 |
2i+2 |
(i-1)//2 |
1번부터 시작하면 공식이 단순해지는 대신 0번 칸이 비고, Python heapq는 0번부터 쓰는 쪽이다( 공식 문서의 불변식이 heap[k] <= heap[2*k+1] ). 둘 중 뭐가 맞는지 헷갈릴 때는 0, 1, 2를 직접 넣어보자..
순회는 외우는 게 아니라 데이터가 흐르는 방향으로 고른다
전위·중위·후위를 놓고 보면 리프가 나오는 순서는 셋 다 똑같다. 다른 건 부모를 언제 방문하느냐 하나뿐이다.
후위 순회를 수식 계산에 쓴다는 건 알고 있었는데, 처음엔 그 이유를 피연산자가 순서대로 읽혀서라고 생각했지만, 수식 트리 계산을 따라가 보니 아니었다. + 노드에서 계산을 하려면 왼쪽과 오른쪽 결과가 이미 손에 있어야 하고, 그래서 부모를 맨 나중에 방문해야 한다. 순서는 셋 다 같으니 순서가 이유일 수가 없었다..!
정리하면 기준은 하나, 데이터가 어느 쪽으로 흐르느냐다.
- 자식의 결과가 부모로 올라가야 하면 후위 ( 수식 계산 )
- 부모의 정보가 자식으로 내려가야 하면 전위
- 이진 탐색 트리에서 정렬 순서가 필요하면 중위
그래프 경로 — 트리에 없던 visited
문제. 방향 그래프에서 출발 노드 S에서 도착 노드 G로 가는 경로가 있는지 확인한다.
- 입력: 테스트케이스 수
T. 케이스마다V E, 이후E줄에 방향 간선v1 v2, 마지막 줄에S G - 출력: 경로가 있으면
#테스트케이스번호 1, 없으면0
import sys
from collections import defaultdict
sys.stdin = open("sample_input.txt", "r")
T = int(input())
def dfs(cur, target):
# 방문 표시
visited.add(cur)
# 성공 시 기존 프로세스 간략화
if target in visited:
return
# 순회
for nxt in adj_list[cur]:
if nxt in visited:
continue
dfs(nxt, target)
for test_case in range(1, T + 1):
# V = 정점의 수, E = 간선의 수
V, E = map(int, input().split())
adj_list = defaultdict(list) # adj_list 접근 가능한 정점 기록
visited = set()
for _ in range(E):
v1, v2 = map(int, input().split())
adj_list[v1].append(v2)
# 탐색
start , target = map(int, input().split())
dfs(start, target)
answer = 1 if target in visited else 0
print(f"#{test_case} {answer}")
트리에선 없던 visited가 그래프에선 필요했다. 역할은 크게 두 가지다.
- 사이클이 있으면 같은 곳을 계속 돌아 재귀가 끝나지 않는 걸 막는다
- 여러 경로로 같은 노드에 들어올 수 있으면 같은 탐색이 중복되는 걸 줄인다
트리는 부모가 최대 하나고 두 노드 사이 경로도 하나뿐이라, 중위순회 코드에는 visited가 없어도 됐던 것이다.
if target in visited: return은 도착점을 찾으면 지금 호출만 끝내는 간략화다. 호출한 쪽의 for는 남은 이웃을 계속 돌지만, 이 문제는 도달 여부만 보면 되니 결과는 달라지지 않는다. 탐색 전체를 멈추고 싶다면 dfs가 True/False를 반환해서 위로 전파하거나, 전역 flag를 두고 루프에서 break해야 한다.
인접 리스트냐 행렬이냐 — 여기서 복잡도를 잘못 알고 있었다
복잡도는 잘못 알고 있었던 부분이 있었고, AI랑 대화하며 추가 정리했다.
인접 리스트 DFS를 O(V)로 알고 있었던 것이다. 노드마다 한 번씩 방문하니까 V라고 생각했는데, 방문한 노드마다 이웃 목록을 훑는 비용이 빠져 있었다. 이웃 목록 길이를 모두 더하면 간선 수가 되니 O(V+E)였다.
다른 하나는 인접 행렬이면 조회가 O(1)이라 더 빠르다고 생각한 것이다. O(1)인 건 “u에서 v로 가는 간선이 있나”를 확인할 때뿐이고, DFS가 하는 일은 “u의 이웃을 나열”하는 쪽이다. 행렬에서는 이웃이 몇 개든 한 행 V칸을 다 봐야 하니, 노드 V개면 O(V²)가 된다.
| 간선 확인 | 이웃 나열 | DFS 전체 | |
|---|---|---|---|
| 인접 리스트 | O(해당 노드 차수) | O(해당 노드 차수) | O(V+E) |
| 인접 행렬 | O(1) | O(V) | O(V²) |
표현은 “어느 쪽이 빠르냐”보다 알고리즘이 어떤 연산을 가장 많이 하냐로 골라야 했다..
추가 조사: 칸( Kahn ) 알고리즘
문제는 DFS로 충분했지만, 강사님의 재량으로 방향 그래프를 다룬 김에 칸 알고리즘을 추가로 알려주셨다.
칸 알고리즘은 방향 그래프를 위상 정렬한다. 간선 u → v가 있으면 결과에서 u가 항상 v보다 앞에 오도록 순서를 매기는 것으로, 선수 과목이나 작업 의존성 순서를 정할 때 쓰인다. Arthur B. Kahn이 1962년 Communications of the ACM에 발표했다.
- 모든 노드의 진입 차수( 들어오는 간선 수 )를 센다
- 진입 차수가 0인 노드를 큐에 넣는다
- 큐에서 하나 꺼내 결과에 붙이고, 그 노드에서 나가는 간선을 지운다. 그 결과 진입 차수가 0이 된 노드를 큐에 넣는다
- 큐가 빌 때까지 반복한다. 결과에 들어간 노드 수가 전체보다 적으면 사이클이 있다
from collections import deque
def kahn(n, edges):
indeg = [0] * (n + 1) # 노드별 진입 차수
adj = [[] for _ in range(n + 1)] # 인접 리스트
for u, v in edges:
adj[u].append(v) # u -> v 간선 기록
indeg[v] += 1 # v로 들어오는 간선 수 증가
q = deque(i for i in range(1, n + 1) if indeg[i] == 0) # 시작점: 진입 차수 0
order = []
while q:
u = q.popleft() # 앞에 올 조건을 다 만족한 노드
order.append(u)
for v in adj[u]:
indeg[v] -= 1 # u -> v 간선 제거
if indeg[v] == 0: # 남은 선행 노드가 없으면 큐에 추가
q.append(v)
return order if len(order) == n else None # 다 못 꺼냈으면 사이클
print(kahn(4, [(1, 2), (1, 3), (3, 4), (2, 4)])) # [1, 2, 3, 4]
print(kahn(3, [(1, 2), (2, 3), (3, 2)])) # None — 2와 3이 사이클
눈에 띈 건 visited가 없다는 점이었다. 노드는 진입 차수가 0이 될 때 한 번만 큐에 들어가니 중복 방문이 없고, 사이클 안의 노드는 서로를 기다리느라 진입 차수가 0이 되지 않아 꺼내지지 않는다. DFS에선 막아야 했던 사이클이, 여기선 “결과에 못 들어온 노드”로 드러난다. 전체는 O(V+E)다.
숫자 만들기 — 로직은 맞았는데 나눗셈에서 틀렸다
문제. 숫자 N개가 순서대로 주어지고, 그 사이에 넣을 연산자 + - * /의 개수가 주어진다. 숫자 순서는 바꿀 수 없고 연산자 배치만 바꿀 수 있다. 연산자 우선순위 없이 왼쪽부터 계산하며, 나눗셈은 소수점 이하를 버린다. 만들 수 있는 최댓값과 최솟값의 차이를 구한다.
- 입력: 테스트케이스 수
T. 케이스마다N, 연산자 개수 4개(+ - * /순, 합은N-1), 숫자N개 - 출력:
#테스트케이스번호 최댓값-최솟값
from collections import defaultdict
T = int(input())
operators = {
0: lambda a, b: a + b,
1: lambda a, b: a - b,
2: lambda a, b: a * b,
3: lambda a, b: int(a / b)
}
def dfs(depth, num, oper_list):
global max_num
global min_num
if depth == N - 1:
max_num = max(max_num, num)
min_num = min(min_num, num)
return
for idx, cnt in enumerate(oper_list):
# 없는 연산자 넘어가기
if cnt == 0:
continue
new_num = operators[idx](num, numbers[depth + 1])
new_list = oper_list.copy()
new_list[idx] -= 1
dfs(depth + 1, new_num, new_list)
for test_case in range(1, T + 1):
N = int(input()) # N = 숫자의 개수
# 연산자 들의 갯수 인덱스 기준 0 = + | 1 = - | 2 = * | 3 = /
oper_cnt = list(map(int, input().split()))
# 나열된 숫자들
numbers = list(map(int, input().split()))
max_num = float("-inf")
min_num = float("inf")
# 탐색 진행
dfs(0, numbers[0], oper_cnt)
print(f"#{test_case} {max_num - min_num}")
지금 코드의 나눗셈은 int(a / b)지만 처음엔 a // b였고, 오답이 났다. AI에게 물어보니 Python의 //는 내림( floor )이고 문제는 버림( truncation )을 요구한다고 짚어줬다. 양수에서는 같고 음수에서만 달라지는데, 돌려보니 정말 그랬다..
print(-7 // 3) # -3 — 더 작은 쪽으로 내림
print(int(-7 / 3)) # -2 — 0 쪽으로 버림
숫자는 양수만 주어지니 음수는 중간에 뺄셈으로만 생기고, 그 음수를 나누는 배치에서만 답이 달라진다.
int(a / b)에도 한계는 있다. a / b가 한 번 float를 거치기 때문에 2⁵³을 넘는 정수에서는 오차가 생길 수 있다. 이 문제는 값 범위가 작아서 괜찮았는데, 큰 정수까지 안전하게 하려면 절댓값끼리 //로 나눈 다음 부호가 다를 때( (a < 0) != (b < 0) ) 음수를 붙이는 방법이 있다. 나머지도 같은 이유로 갈린다. -7 % 3은 Python에서 2, C에서는 -1이다. 다른 언어 기준으로 만든 문제면 음수 나눗셈과 나머지부터 의심해 봐야겠다.
추가 조사: Python은 왜 내림으로 나누는가
이유는 글을 정리하며 AI와 찾아봤는데, Python을 만든 Guido van Rossum의 Why Python’s Integer Division Floors( 2010 )에 설명이 있었다.
요지는 나눗셈보다 나머지를 먼저 생각했다는 것이다. q = a // b, r = a % b일 때 b*q + r == a는 어느 방식이든 성립하는데, 내림으로 나누면 b > 0에서 나머지가 항상 0 ≤ r < b에 들어온다. 버림으로 나누면 a가 음수일 때 r도 음수가 된다.
글에 든 예시는 POSIX 타임스탬프다. 타임스탬프 t에서 하루 중 시각을 구하려면 t % 86400을 쓰는데, 1970년 이전이라 t가 음수여도 내림 나눗셈이면 0~86399 안의 올바른 값이 나온다. 버림이면 음수 시각이 나와서 의미가 없어진다. C가 버림을 택한 쪽은 당시 하드웨어 사정 때문이었을 거라고 Guido는 추정하고 있다.
Python이 틀린 게 아니라, 문제와 기준이 달랐을 뿐이었다.
복사냐 되돌리기냐
백트래킹에서 연산자 개수를 쓰고 나면 다음 분기를 위해 원래대로 돌려놔야 한다. 복구를 빠뜨리면 앞 분기에서 쓴 개수가 다음 분기에 그대로 남아 결과가 오염된다. 방법은 두 가지다.
-
되돌리기: 리스트 하나를 두고
-= 1한 뒤 재귀에서 돌아오면+= 1 -
복사: 분기마다
copy()로 새 리스트를 만들어 넘긴다( 이번 풀이 )
이 trade-off는 이전에 교육을 진행하면서 이미 알고 있던 내용이라, 이번엔 AI가 다시 되물어 본 느낌이었다. 되돌리기는 복사 비용이 없어 효율적이고, 복사는 복구를 잊을 일이 없다. 한 번에 여러 값을 연쇄로 바꾸거나 분기를 병렬로 돌리는 경우라면 복사 쪽이 안전하다.
하나 헛짚은 게 있었다. 복사 방식의 메모리를 말하다가 “2배”라고 했는데, 루프 하나만 보고 단순하게 말한 거였다. 재귀가 깊어지는 동안 각 호출이 자기 new_list를 들고 있으니 깊이만큼 복사본이 동시에 존재한다. 호출 스택에 따라 복사본이 공존한다는 건 알고 있었는데, 말하면서 놓쳤다..
소감
세 문제 중 틀린 건 숫자 만들기 하나였다. 탐색 로직은 맞았는데 음수를 나누는 방식이 문제와 달랐고, AI가 짚어주기 전까지는 보지 못했다.
그럼에도 수정하는 과정에서 설계의도까지 찾아볼 수 있었기에 좋았던 것 같다.