04_cotest
13_DFS
# DFS예제!!!
===> 깊이 중심!!!
Stack으로 처리를 한다!!!
# 0) 탐색을 지도에서 해야하므로 --> 지도를 코드화!!!!
# ==> 인접리스트 방식 표현을 하자!!!!
# 1) 파이썬 리스트 vs 2) 파이썬 Dict
# ---> 선택 : 파이썬 리스트!!!!!!
# 1번 도시부터네;;;
graph_list = [
[], # <--- 가상의 0번 도시가 있따고 가정,
[2,3,8], # <--- 1번 도시의 연결된 도시(직접)
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
graph_list
[[], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7]]
graph_list[3]
# 3번 도시에 바로 연결된 도시들은 뭐에요?
# --> 구체적은 연결된 도시를 찾을려면
# 직접 찾아 해매야 합니다!!!!
[1, 4, 5]
graph_list[2]
[1, 7]
# 탐색에 DFS 함수
입력 : 지도 , 시작점(1)
-- 필요한 변수 세팅 : 방문할 곳 리스트 To Do List
-- 방문한 곳 리스트 Done List
==> 방문할 곳 리스트 : 시작점에 대한 정보를 추가...
사무실에 나와서 출발!!!!!!!
큰틀 : 방문할 곳 리스트가 하나도 없을 때 까지!!!! ==> 횟수X, 조건:while
구현) while 리스트:빈 리스트가 될 때 까지....:물론 갯수 등으로 할 수도 있는데,,굳이....
--> 방문할 곳을 어떻게 처리 : Stack --> 맨 뒤 pop()
# 처음 방문한 곳이면 할 일 : 2가지 --> 도장/또 할일(방문할곳) 부여 받아야 함!!!
1) 여기가 내가 처음 온 곳인가? --> 도장 받기
DoneList.append(뒤로 추가)
2) 여기서 연결된 곳은 어딘가요?--> 또 방문할 곳 부여 받음!!!
ToDoList.append(뒤로 추가)
입력 : 지도, 시작점
기능 : DFS방식으로 주어진 지도를 탐색/방문하세요!!!
출력 : 방문 기록을 제출!!!!
def dfs_m1( graph, start):
# 초기 변수들을 세팅!!!
# - 1) 방문할 곳 리스트 : To Do List
# - 2) 방문한 곳 리스트 : Done List
need_visit = list() # []
visited = list()
# ---> 스스로 일 할 준비를 세팅
# --> 팀장한테 가서 어디서 출발할까요 ==> 방문할 곳에 추가!!!!
need_visit.append(start)
#########################
# 출발!!!
# ===> 언제까지 이거 하면 되지?? need_visit 비울 때 까지!!!!
# 몇 번으로 끝나지는 아무도 몰라요;;;
# 단, 퇴근 조건은 암!!! 리스트 비울 때 까지 ==> while
while need_visit:
# 1) 나 어디로 갈지 : 방문할 곳 꺼내서 : Stack-->맨 뒤
node = need_visit.pop()
# 2) node 내가 이미 갔던 곳인지 // 신규 방문지 체크!!!!
# ==> 갔던 곳이면 : pass
# ==> 신규 방문지 : 도장찍고 & 새로운 미션 부여 받아야 함!!
# (여기서 바로 연결된 곳들)
if node not in visited: # <--- 신규 방문지!!!!
# 2-1) 도장찍고
visited.append( node )
# 2-2) 할일부여 받음!! : 연결된 도시들 정보를 할 일에 추가..
# graph[1] = [2,3,8]
need_visit.extend( graph[node])
return visited
def dfs_m1( graph, start):
need_visit = list() # []
visited = list()
need_visit.append(start)
while need_visit:
node = need_visit.pop()
if node not in visited: # <--- 신규 방문지!!!!
visited.append( node )
need_visit.extend( graph[node])
return visited
dfs_m1(graph_list, 1)
[1, 8, 7, 6, 2, 3, 5, 4]
원래 그림상 의도 : 1 -- >2 ---> 7 --~~~ : 동일한 연결에서는
도시 번호가 작은 애들먼저..
실제 위의 코드 : 1 ---> 8 --> 7 ~~~ : 동일한 연결에서
도시 번호가 큰 친구 우선으로 방문!!!
이유 : 처음 방문지 1번에 가서...물어봐을때..
지도가 : 리스트로 표현하는 과정에 [2,3,8]
정리된 상태에서 할 일에 추가를 해서...
stack으로 꺼내다보니 8번이 먼저 꺼내져서,,
동일한 조건 하에서는 숫자 큰 것이 우선 방문하게 됨!!!
def dfs_m2( graph, start):
need_visit = list() # []
visited = list()
need_visit.append(start)
while need_visit:
node = need_visit.pop()
if node not in visited: # <--- 신규 방문지!!!!
visited.append( node )
#### 순서를 지정 : 같은 조건이면 작은 번호를 먼저.
# 역방향 : .reverse(), reversed(), [::-1], sort/sorted
# ==> 조건이 있다면,,,조정을 해야 함!!!
temp = graph[node]
temp_reverse = list(reversed(temp))
need_visit.extend( temp_reverse )
# need_visit.extend( graph[node][::-1])
return visited
dfs_m2(graph_list, 1)
[1, 2, 7, 6, 8, 3, 4, 5]
14_BFS
# BFS
===> 1번 도시를 출발한다고 하면,,,
BFS 방식 : 스케줄링 큐 방식으로 하면,,,
어떻게 돌아갈까???
# 0) 탐색을 지도에서 해야하므로 --> 지도를 코드화!!!!
# ==> 인접리스트 방식 표현을 하자!!!!
# 1) 파이썬 리스트 vs 2) 파이썬 Dict
# ---> 선택 : 파이썬 리스트!!!!!!
# 1번 도시부터네;;;
graph_list = [
[], # <--- 가상의 0번 도시가 있따고 가정,
[2,3,8], # <--- 1번 도시의 연결된 도시(직접)
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
graph_list
[[], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7]]
# 탐색에 BFS 함수
입력 : 지도 , 시작점(1)
-- 필요한 변수 세팅 : 방문할 곳 리스트 To Do List
-- 방문한 곳 리스트 Done List
==> 방문할 곳 리스트 : 시작점에 대한 정보를 추가...
사무실에 나와서 출발!!!!!!!
큰틀 : 방문할 곳 리스트가 하나도 없을 때 까지!!!! ==> 횟수X, 조건:while
구현) while 리스트:빈 리스트가 될 때 까지....:물론 갯수 등으로 할 수도 있는데,,굳이....
--> **방문할 곳을 어떻게 처리 : 큐!!!! --> 맨 뒤 pop(0)
# 처음 방문한 곳이면 할 일 : 2가지 --> 도장/또 할일(방문할곳) 부여 받아야 함!!!
1) 여기가 내가 처음 온 곳인가? --> 도장 받기
DoneList.append(뒤로 추가)
2) 여기서 연결된 곳은 어딘가요?--> 또 방문할 곳 부여 받음!!!
ToDoList.append(뒤로 추가)
def bfs_m1( graph, start):
# 초기 변수들을 세팅!!!
# - 1) 방문할 곳 리스트 : To Do List
# - 2) 방문한 곳 리스트 : Done List
need_visit = list() # []
visited = list()
# ---> 스스로 일 할 준비를 세팅
# --> 팀장한테 가서 어디서 출발할까요 ==> 방문할 곳에 추가!!!!
need_visit.append(start)
#########################
# 출발!!!
# ===> 언제까지 이거 하면 되지?? need_visit 비울 때 까지!!!!
# 몇 번으로 끝나지는 아무도 몰라요;;;
# 단, 퇴근 조건은 암!!! 리스트 비울 때 까지 ==> while
while need_visit:
# 1) 나 어디로 갈지 : 방문할 곳 꺼내서 : 큐!!!--> pop(0)
node = need_visit.pop(0)
# 2) node 내가 이미 갔던 곳인지 // 신규 방문지 체크!!!!
# ==> 갔던 곳이면 : pass
# ==> 신규 방문지 : 도장찍고 & 새로운 미션 부여 받아야 함!!
# (여기서 바로 연결된 곳들)
if node not in visited: # <--- 신규 방문지!!!!
# 2-1) 도장찍고
visited.append( node )
# 2-2) 할일부여 받음!! : 연결된 도시들 정보를 할 일에 추가..
# graph[1] = [2,3,8]
need_visit.extend( graph[node])
return visited
bfs_m1(graph_list, 1)
[1, 2, 3, 8, 7, 4, 5, 6]
15_DFS_BFS_정리
# 중요한 내용 : 탐색이라는 것을 어떻게 코드화!!!
===> 변수들을 세팅을 해야 함!!( 해야할 목록, 한 목록)
해야할 일을 다 할 때 까지 주구장창 : while
- 지금 해야할 일이 신규 일인지 아닌지 체크
- 신규 일 : 했다고 도장찍고!!!!
다시 새로운 미션을 부여 받아서 할 일에 추가!!!
-----------주어진 상황에 모든 할 일/방문을 다 할 수 있음!!!
할일 : 이런 기본적인 패턴/ 내용에 대해서 다양하게 가능함!!
==> 다양한 주어진 문제에 적용하는 연습!!!!
기본 내용과 100프로 일치하는 경우는 거의 XXX
기본적인 내용과 주어진 문제의 차이점&공통점!!!=-> 탐색
중요한 내용
- DFS : 해야할 일에 대한 관리 ==> Stack
(할 일은 맨 뒤에 추가)
(선택은 맨 뒤에서 뽑아서)
- BFS : 해야할 일에 대한 관리 ==> Queue
(할 일은 맨 뒤에 추가.)
(선택은 맨 앞에서 뽑아서)
==> 모든 곳들은 다 방문을 할 수 있음!!!!
but 방문하는 스타일이 달라진다!!!!
DFS : 꼬리에 꼬리를 물면서 진행---> 깊이 중심(출발점에 일단 멀리 도망)
BFS : 맨 앞에서 부터 하나씩 순차적인 해결 ==> 시작점 중심 방사형...너비중심
# 참고) 주어진 탐색같은 경우에 대해서 "지도형 문제"
==> 추상적인 지도를 어떻게 코드화 할 것인가!!!
- 인접행렬방식 : 파이썬코드화(리스트): 가로/세로 딱 맞춰서 행렬처럼
- 인접리스트방식 : 파이썬코드화(리스트/Dict): 정수인덱스/키 중심으로 연결성들을 리스트업!!!
==> 모양이 가로/세로 딱 맞춰진 케이스 : 행렬
값의 길이가 각양 각색 : 리스트
중요!!!!!) 지도만 탐색을 하는 것이 아니라 다양한 곳에 적용이 됨!!!
# 참고) 파이썬으로 Queue은 운영을 하면 속도이슈 무조건 발생!!!
===> 파이썬 자체의 자료구조 리슽가 태생적인 속도 한계!!!!!!
===> 코테에서는 주로 deque 패키지/자료형을 사용하면 해결이 됨!!!
코테/알고리즘 대회 : deque 패키지
참고) 파이썬 리스트/numpy array 등 쓰는데,,조금이라도 빠르게 핬겠다
: deque!!!!
# collections 패키지의 여러 모듈 중 하나1!!
from collections import deque
a_list = [1,2,3]
a_list
[1,2,3]
a_dq = deque([1,2,3])
a_dq
deque([1,2,3])
# 원소 추가 : 무조건 맨 뒤 append
a_dq.append(4)
a_dq
deque([1,2,3,4])
# 리스트 : 원소 빼기 : pop() --> 맨 뒤에서 제거
a_list
[1,2,3]
a_list.pop()
3
a_list
[1,2]
a_dq
deque([1,2,3,4])
a_dq.pop()
4
a_dq
deque([1,2,3])
# 맨 앞에서 원서 뺄 때 : pop(0)
a_list
[1,2]
a_list.pop(0)
1
a_list
[2]
a_dq,pop(0) # --> 에러 발생!!
// TypeError
a_dq.popleft()
1
a_dq
deque([2,3])
# deque로 하면,,
stack처럼 사용하려면 처음 세팅만 deque하면 끝!!!!
Queue처럼 사용하려면 처음 세팅 deque로 하고 pop(0)-->popleft()
현실적으로
코테에서는 내가 stack으로 하는 것은 굳이 deque 변경안 해도 됨!!!
Queue로 하는 것은 무조건!! deque로 해야 함!!!!!!
# 실험 : list vs deque : stack
from collections import deque
import time
N = 1000 # 초기에 넣어둘 원소의 갯수
TIMES = 100 # 실험 횟수
M = 1000 # M 번 pop, M번 append
# 일단 2개의 자료형에 N 개의 원소들을 넣어두겠습니다.
list_stack = list([i for i in range(0,N)])
deque_stack = deque([i for i in range(0,N)])
# List--> Stack
s_time = time.time()
for _ in range(0, TIMES):
# M개의 원소들을 append, pop
for i in range(0,M):
list_stack.append(i)
list_stack.pop()
print("list",time.time()- s_time)
# deque--> Stack
s_time = time.time()
for _ in range(0, TIMES):
# M개의 원소들을 append, pop
for i in range(0,M):
deque_stack.append(i)
deque_stack.pop()
print("list",time.time()- s_time)
list 0.019702672958374023
list 0.01571798324584961
N = 1000 # 초기에 넣어둘 원소의 갯수
TIMES = 100 # 실험 횟수
M = 1000 # M 번 pop, M번 append
# 일단 2개의 자료형에 N 개의 원소들을 넣어두겠습니다.
list_queue = list([i for i in range(0,N)])
deque_queue = deque([i for i in range(0,N)])
# List--> Queue
s_time = time.time()
for _ in range(0, TIMES):
# M개의 원소들을 append, pop
for i in range(0,M):
list_queue.append(i)
list_queue.pop(0)
print("list",time.time()- s_time)
# deque--> Queue
s_time = time.time()
for _ in range(0, TIMES):
# M개의 원소들을 append, pop
for i in range(0,M):
deque_queue.append(i)
deque_queue.popleft()
print("list",time.time()- s_time)
list 0.03551363945007324
list 0.01670551300048828
# BFS 수정
def bfs_list( graph, start):
need_visit = list() # []
visited = list()
need_visit.append(start)
while need_visit:
node = need_visit.pop(0)
if node not in visited: # <--- 신규 방문지!!!!
visited.append( node )
need_visit.extend( graph[node])
return visited
def bfs_deque( graph, start):
need_visit = deque([]) # ****
visited = deque([]) # ****
need_visit.append(start)
while need_visit:
#node = need_visit.pop(0)
node = need_visit.popleft() # ***********
if node not in visited: # <--- 신규 방문지!!!!
visited.append( node )
need_visit.extend( graph[node])
return visited
'ASAC 빅데이터 분석가 7기 > ASAC 일일 기록' 카테고리의 다른 글
| ASAC 빅데이터 분석가 과정 9일차 - 1 (24.12.16) (1) | 2024.12.16 |
|---|---|
| ASAC 빅데이터 분석가 과정 8일차 - 2 (24.12.13) (3) | 2024.12.13 |
| ASAC 빅데이터 분석가 과정 7일차 - 2 (24.12.12) (0) | 2024.12.12 |
| ASAC 빅데이터 분석가 과정 7일차 - 1 (24.12.12) (0) | 2024.12.12 |
| ASAC 빅데이터 분석가 과정 6일차 - 2 (24.12.11) (1) | 2024.12.11 |