학원에서 프로젝트를 진행한다는 핑계로 알고리즘을 제대로 못본지 거의 한달이 넘었습니다.
알고리즘/자료구조에서 진행하다보면 나오는 그래프/DFS/BFS를 넘어서지 못한 채로 한달이상이 지난건데요. 문득 제가 뭘 제대로 몰랐는지 깨달아서...
다시 헷갈릴일은 없겠지만 혹시나 해서 기록을 남겨봅니다.
1. 함수와 전역변수, 지역변수
함수에서 변수에 변경을 할 때(더하기,빼기) 어떤 일이 일어나는지 확인해봅시다.
시간이 없으시다면, 6번만 확인하셔도 됩니다.
1. 함수에서 argument를 받아서 처리할 때
N = 1
def add_1(N) :
N += 1
print("result_of_1 : ", N)
add_1(N)
# result_of_1 : 2
print(N)
# 1
# 결론 : 전역변수 N의 값에 영향을 끼치지 않음.2. 함수에서 arg가 없을 때
N = 1
def add_2():
print("result_of_2 : ", N+1)
add_2()
# result_of_2 : 2
print(N)
# 13. arg를 사용하지 않고 전역변수에 변화를 주려고 할 때
N = 1
def add_3():
N += 1
print(N)
add_3()
# 에러 발생 : N+1 부분에서, N이 정의(선언)되지 않았다고 나타남.이렇게 전역변수/지역변수의 관계는 아래와 같습니다.
-
함수에서 변수를 인자로 받는 경우에 인자(변수)에 뭔가 변화를 가하더라도, 그 변화는 외부의 변수에 영향을 끼치지 않는다.
-
함수에서 변수를 인자로 받지 않은 경우에, 변수에 변화를 가한다면 그 변화는 외부의 변수에 영향을 끼친다.
그렇다면 전역변수에 대해 변화를 주려면 어떻게 해야 할까요?
4. 외부의 N을 변경하려면?
glboal "변수명"을 사용하는 것입니다.
N = 1
def add_4():
global N # 전역변수 N을 사용한다고 선언.
N +=1
print(N)
add_4()
#2
print(N)
# 25. (결론) 전역 변수를 리스트로 설정했을 때
그러나 위의 4개의 예시와는 달리,
변수의 데이터 타입을 숫자가 아닌 list로 바꾸면
- 굳이 global로 선언하지 않아도
- 변수를 인자로 받아도
변경사항이 변수에 저장됩니다.
이 부분이 제가 굉장히 헷갈렸던 부분입니다.
그리고 이 부분이 DFS에서 방문처리 리스트를 전역변수로 사용하거나
arg로 받거나 모두 똑같이 동작하는 원인입니다.
TEST = [0,1,2,3,4]
def append_1():
TEST.append(1)
print(TEST)
# [0,1,2,3,4]
append_1()
print(TEST)
# [0,1,2,3,4,1]이에 대해 이유를 설명해보면
숫자 저장된 변수는, 기본 데이터 타입이 저장되어 있고,
리스트가 저장된 변수는 header를 향한 주소가 저장된 것이기 때문이라고 할 수 있겠습니다.
아래에서 실제로 어떻게 되는건지 예시를 보겠습니다.
2. 재귀함수
재귀함수는 DFS 풀기 전에 꼭 먼저 알아야 하는 개념입니다.
이 전역변수, 지역변수가 재귀함수에서는 어떻게 일어나는지 확인해봅시다.
1. 첫번째 예시
아래는 나동빈님께서 보여주신
재귀함수의 동작을 직관적으로 잘 나타내는 예시입니다.
def recursive_function(i):
# 5번째 호출을 했을 때 종료되도록 종료 조건 명시
if i >= 5: # 2
return
print(i, '번째 재귀함수에서', i + 1, '번째 재귀함수를 호출합니다') # 1
recursive_function(i + 1) # 3
print(i, '번째 재귀함수를 종료합니다') # 4
recursive_function(0)
"""
결과 값
0 번째 재귀함수에서 1 번째 재귀함수를 호출합니다
1 번째 재귀함수에서 2 번째 재귀함수를 호출합니다
2 번째 재귀함수에서 3 번째 재귀함수를 호출합니다
3 번째 재귀함수에서 4 번째 재귀함수를 호출합니다
4 번째 재귀함수에서 5 번째 재귀함수를 호출합니다
4 번째 재귀함수를 종료합니다
3 번째 재귀함수를 종료합니다
2 번째 재귀함수를 종료합니다
1 번째 재귀함수를 종료합니다
0 번째 재귀함수를 종료합니다
"""
위의 예시를 토대로 재귀함수를 더 세세하게 나눠보면
재귀함수의 동작을 이해할 수 있습니다.
- 특정 조건의 경우, 자신을 호출하기 전에 return으로 함수 끝내버림.
- <선동작> (없을 수도 있음)
- 자기 자신 호출
- <후동작> (없을 수도 있음)
전역변수를 함수 내부에서 어떻게 변화시키는지
확인하기 위해서, 숫자 i를 리스트 list로 변경해보겠습니다.
2. 두번째 예시
def recursive_function(list):
# 5번째 호출을 했을 때 종료되도록 종료 조건 명시
if len(list) >= 5: # 2
return
print(len(list), '번째 재귀함수에서', len(list)+1, '번째 재귀함수를 호출합니다') # 1
list.append(0)
recursive_function(list) # 3
print(len(list), '번째 재귀함수를 종료합니다') # 4
recursive_function([0])
""" 결과값
1 번째 재귀함수에서 2 번째 재귀함수를 호출합니다
2 번째 재귀함수에서 3 번째 재귀함수를 호출합니다
3 번째 재귀함수에서 4 번째 재귀함수를 호출합니다
4 번째 재귀함수에서 5 번째 재귀함수를 호출합니다
5 번째 재귀함수를 종료합니다
5 번째 재귀함수를 종료합니다
5 번째 재귀함수를 종료합니다
5 번째 재귀함수를 종료합니다
"""3번째 예시
이번에는 list를 인자로 받지 않고
외부에 있는 전역변수를 사용해서
변화를 확인해보겠습니다.
list = [0]
def recursive_function():
# 5번째 호출을 했을 때 종료되도록 종료 조건 명시
if len(list) >= 5: # 2
return
print(len(list), '번째 재귀함수에서', len(list)+1, '번째 재귀함수를 호출합니다') # 1
list.append(1)
recursive_function() # 3
print(len(list), '번째 재귀함수를 종료합니다') # 4
recursive_function()
"""결과값
1 번째 재귀함수에서 2 번째 재귀함수를 호출합니다
2 번째 재귀함수에서 3 번째 재귀함수를 호출합니다
3 번째 재귀함수에서 4 번째 재귀함수를 호출합니다
4 번째 재귀함수에서 5 번째 재귀함수를 호출합니다
5 번째 재귀함수를 종료합니다
5 번째 재귀함수를 종료합니다
5 번째 재귀함수를 종료합니다
5 번째 재귀함수를 종료합니다
"""결론
차이가 느껴지시나요?
위에서 봤던 결론이 똑같이 나타납니다.
- 함수에서 인자로 사용하건 말건, 리스트는 변경 사항이 어디에서나 작업 순서(시간순서)에 따라 저장된다.
3. DFS, BFS
기본적으로 같은 이야기를 반복하고 있습니다.
지역변수, 전역변수를 DFS, BFS에서는 어떻게 적용하는지 확인해봅시다.
제가 가장 헷갈렸던 점은 어떤 DFS의 풀이에서는
방문처리 변수(visited)를 arg로 처리하는 경우와
전역변수로 처리하는 경우의 차이였습니다.
1. arg 미사용
리스트를 전역변수로 사용했습니다.
아래의 예시를 보면,
마치 전역변수이기 때문에
"visited" 리스트에 어떤 변화가 주어졌을 때
모든 함수에서 공유하는 것처럼 보입니다.
def dfs(v):
visit_list2[v] = 1
print(v, end = " ")
for i in range(1, n + 1):
if visit_list2[i] == 0 and graph[v][i] == 1:
dfs(i)
def bfs(v):
q = deque()
q.append(v)
visit_list[v] = 1
while q:
v = q.popleft()
print(v, end = " ")
for i in range(1, n + 1):
if visit_list[i] == 0 and graph[v][i] == 1:
q.append(i)
visit_list[i] = 12. DFS,BFS - arg 사용
그러나 visited, graph를
인자로써 전역변수가 아닌 지역변수로 사용하면
더 하위 단계에서의 "visited" 리스트의 변경 사항을
더 상위 단계에서는 공유받지 못할 것처럼 보이지만
(적어도 저는 이 단계에서 엄청 헷갈렸습니다.)
실제로는 하위단계의 변경사항도 모든 위치에 반영됨을 알 수 있습니다.
def dfs_orig(graph, v, visited) :
#현재 노드를 방문 처리.
visited[v] = True
print(v, end=' ')
#현재 노드와 연결된 다른 노드를, 재귀적으로 방문하기
for i in graph[v] :
if not visited[i] :
dfs_orig(graph, i, visited)
return None
def bfs_orig(graph, start, visited) :
#큐 구현을 위해 deque 라이브러리 사용.
queue = deque([start])
#현재 노드를 방문처리
visited[start] =True
#큐가 빌 때까지 반복
while queue :
#큐에서 하나의 원소를 뽑아 출력하기.
v = queue.popleft()
print(v, end=' ')
#아직 방문하지 않은 인접한 원소들을 큐에 삽입
for i in graph[v] :
if not visited[i] :
queue.append(i)
visited[i] = True
4. 정리
이렇게 DFS,BFS의 동작에 대해 헷갈린 것은
제가 파이썬의 전역변수,지역변수에 대해 애매하게 알았기 때문입니다.
벌써 DFS,BFS 문제를 풀어볼 생각에 기대되네요!
다른 분들께서는 헷갈려서 시간낭비 없으시길 바라며 글을 마칩니다.
감사합니다.
이후에 확인한 키워드 : 중첩함수