def fibo(n):
if n < 2:
return n
else:
return fibo(n-1) + fibo(n-2)
def fibo2(n):
f = [0] * (n + 1)
f[0] = 0
f[1] = 1
for i in range(2, n + 1):
f[i] = f[i-1] + f[i-2]
return f[n]
def f(i, k):
if i == k: # 목표에 도달하면
print(B)
return
else:
B[i] = A[i]
f(i + 1, k)
A = [i for i in range(1000)]
B = [0] * 1000
f(0, 1000)
비선형구조인 그래프 구조는 그래프로 표현된 모든 자료를 빠짐없이 검색하는 것이 중요
- 두 가지 방법
깊이 우선 탐색 (DFS)
너비 우선 탐색 (BFS)
1. 딕셔너리의 활용
graph = {}
graph['A'] = ['B', 'C']
grpah['B'] = ['D', 'F']
.
.
.
# A B C D E F
# A 0 1 1 0 0 0
# B 0 0 0 1 0 1
# C
# D
# E
# F
7 8 V E
1 2 1 3 2 4 2 5 4 6 5 6 6 7 3 7
#V(정점), E(간선)
V, E = map(int, input().split())
data = list(map(int, input().split())
arr = [[0] * (V + 1) for _ in range*(V+i)]
visited = [0] * (V + i) # 방문 여부 확인하는 리스트
# 언더스코어 쓰는 이유 꺼내오는 값 쓰지 않을 경우
for _ in range(E):
n1, n2 = arr[i+2], arr[i+2+i]
arr[n1][n2] = 1 # n1과 n2는 인접해있다.
arr[n2][n1] 1
def dfs(v): # v는 지금 현재 탐색하는 정점
visited[v] = 1
print(v)
# 현재 v는 시작정점, 인접한 정점 중 방문을 안한 곳
for w in range(1, V + i):
if arr[v][w] == 1 and visited[w] == 0:
dfs(w)
dfs(1)
1) 시작 정점 v를 결정하여 방문한다
2) 정점 v에 인접한 정점 중에서
방문하지 않은 정점 w가 있으면, 정점 v를 스택에 push하고 정점 w를 방문한다
그리고 w를 v로 하여 다시 2를 반복한다
방문하지 않은 정점이 없으면, 탐색 방향 바꾸기 위해 스택을 pop하여 받은 가장 마지막 방문 정점을 v로 하여 다시 2를 반복
3) 스택이 공백이 될때까지 2를 반복
그래프 저장 방법이 필요
손으로 따라갈 수 있으면 된다
1 -> 2-> 4-> 6 -> 5 -> 7 -> 3
기본적으로 연속적 사용
8개의 간선이 있다
7 8
1 2 11 3 5 .. 간선 정보
2개씩 몇 쌍이 주어지는지에 대한 정보
양쪽 서로간 방문이 가능