11725 부모 찾기
문제
루트 없는 트리가 주어진다. 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구해 2번 노드부터 순서대로 출력하는 문제
DFS 풀이
import sys
sys.setrecursionlimit(10**6)
n = int(sys.stdin.readline())
graph = [[] for i in range(n + 1)]
for i in range(n - 1):
a, b = map(int, sys.stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
visited = [0] * (n + 1)
visited[1] = 1
def dfs(now):
for nxt in graph[now]:
if visited[nxt] == 0:
visited[nxt] = now
dfs(nxt)
dfs(1)
for x in range(2 , n + 1):
print(visited[x])풀이
각 노드의 간선(edge)를 graph라는 이중 리스트에 저장한다. a와 b를 각각 인덱스와 요소로 바꿔서 저장합니다.
visited라는 배열에 N개 만큼 0을 추가하고 재귀적 방법(백트래킹)을 통해 DFS를 구현합니다.
dfs 함수에 now 매개변수는 현재의 값(부모 노드로 저장될)이고 nxt는 왼쪽(오른쪽) 자식 노드의 값입니다. visited는 부모 노드의 값이 저장되어 결과값으로 출력될 리스트입니다.
BFS 풀이
import sys
from collections import deque
N = int(sys.stdin.readline())
graph = [[] for i in range(N+1)]
for _ in range(N-1):
a, b = map(int, sys.stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
queue = deque()
queue.append(1)
ans = [0]*(N+1)
def bfs():
while queue:
now = queue.popleft()
for nxt in graph[now]:
if ans[nxt] == 0:
ans[nxt] = now
queue.append(nxt)
bfs()
for x in ans[2:]:
print(x)변수의 값들의 저장은 DFS 방식에서와 같습니다.
데크(deque)를 이용해서 큐를 활용하는 방식으로 BFS를 구현했으며 ans 리스트의 요소들이 부모의 노드가 됩니다.
초기 큐에 담긴 1을 popleft하여 for문에서 now(부모 노드)입니다. nxt는 graph의 해당 요소의 리스트 요소값이 되어 인덱스로 활용하여 ans에서 해당 인덱스가 0이면 부모의 값을 append하는 식입니다.
오늘의 py.docs(3.2. 표준형 계층)
- None : 이 형은 하나의 값만을 갖습니다. 이 값을 갖는 하나의 객체가 존재합니다. 이 객체에는 내장된 이름 None 을 통해 접근합니다. 여러 가지 상황에서 값의 부재를 알리는 데 사용됩니다. 예를 들어, 명시적으로 뭔가를 돌려주지 않는 함수의 반환 값입니다. 논리값은 거짓입니다.
- numbers.Integral(정수 (int), 불린(boolean))
이것은 (가상) 메모리가 허락하는 한, 제약 없는 범위의 숫자를 표현합니다. ... 음수는 일종의 2의 보수(2’s complement)로 표현되는데, 부호 비트가 왼쪽으로 무한히 확장된 것과 같은 효과를 줍니다.- 이것은 논리값 거짓과 참을 나타냅니다. False 와 True 두 객체만 불린 형 객체입니다. 불린 형은 int 형의 자식형(subtype)이고, 대부분 상황에서 각기 0과1처럼 동작합니다. 예외는 문자열로 변환되는 경우인데, 각기 문자열 "False" 와 "True" 가 반환됩니다.
- numbers.Real (float)
이것들은 기계 수준의 배정도(double precision) 부동 소수점 수를 나타냅니다. 허락되는 값의 범위와 오버플로의 처리에 관해서는 하부 기계의 설계(와 C 나 자바 구현)에 따르는 수밖에 없습니다. 파이썬은 단정도(single precision) 부동 소수점 수를 지원하지 않습니다.
- 부동 소수점 산술: 문제점 및 한계
불행히도, 대부분의 십진 소수는 정확하게 이진 소수로 표현될 수 없습니다. 결과적으로, 일반적으로 입력하는 십진 부동 소수점 숫자가 실제로 기계에 저장될 때는 이진 부동 소수점 수로 근사 될 뿐입니다.
이 문제는 먼저 밑 10에서 따져보는 것이 이해하기 쉽습니다. 분수 1/3을 생각해봅시다. 이 값을 십진 소수로 근사할 수 있습니다:0.3 또는, 더 정확하게, 0.33 또는, 더 정확하게, 0.333등등. 아무리 많은 자릿수를 적어도 결과가 정확하게 1/3이 될 수 없지만, 점점 더 1/3에 가까운 근사치가 됩니다.
같은 방식으로, 아무리 많은 자릿수의 숫자를 사용해도, 십진수 0.1은 이진 소수로 정확하게 표현될 수 없습니다. 이진법에서, 1/10은 무한히 반복되는 소수입니다
0.0001100110011001100110011001100110011001100110011...
유한 한 비트 수에서 멈추면, 근삿값을 얻게 됩니다. 오늘날 대부분 기계에서, float는 이진 분수로 근사 되는 데, 최상위 비트로부터 시작하는 53비트를 분자로 사용하고, 2의 거듭제곱 수를 분모로 사용합니다. 1/10의 경우, 이진 분수는 3602879701896397 / 2 55 인데, 실제 값 1/10과 거의 같지만 정확히 같지는 않습니다.**1 / 10 0.1인쇄된 결과가 정확히 1/10인 것처럼 보여도, 실제 저장된 값은 가장 가까운 표현 가능한 이진 소수임을 기억하세요. 이것이 이진 부동 소수점의 본질임에 주목하세요: 파이썬의 버그는 아니며, 여러분의 코드에 있는 버그도 아닙니다. 하드웨어의 부동 소수점 산술을 지원하는 모든 언어에서 같은 종류의 것을 볼 수 있습니다.
출처
https://d-cron.tistory.com/22
https://docs.python.org/ko/3/reference/datamodel.html#the-standard-type-hierarchy
