[이코테] 부스러기: 방향벡터/ 스택, 큐, 재귀함수 for 탐색 알고리즘

#방향벡터

좌표 구현 문제에서 방향벡터를 이용하여 좌표를 이동시키기.

방향벡터란 방향을 나타내는 벡터. 

예를 들어서

dx=[-1,1,0,0]

dy=[0,0,-1,1]

각각의 i번째 원소를 현재 x,y 좌표에 각각 더해주면 이동이 됨.

또는 

moves=[(-1,-1),(-1,0), ... ] 처럼 하나의 리스트로 나타낼 수도 있음.

 

#탐색

탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

그래프 탐색 알고리즘 DFS/BFS

 

-스택: 리스트로 구현. append(*), pop()

최상단 원소부터 출력 > print(list[::-1]

최하단 원소부터 출력 > print(list)

-큐: 리스트로도 가능하나 비효율적. deque(덱) 라이브러리 이용

from collections import deque

queue=deque()

queue.append(*)

queue.popleft()

queue.reverse()

print(queue)

-재귀함수: 자기 자신을 다시 호출하는 함수 => 반복 가능

단 문제풀이시 반드시 재귀함수의 종료 조건 명시. 무한루프 방지.

--유클리드 호제법: 두 자연수의 최대공약수를 구하는 알고리즘

모든 재귀함수는 반복문을 이용하여 동일한 기능 구현 가능. 반대도 마찬가지.

컴퓨터가 함수를 재귀적으로 (연속적으로) 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓임.

-> so 스택 사용시 구현상 스택 라이브러리 대신 재귀함수 이용하는 경우가 많다. (DFS)

 

#DFS

...2/25 이어서:

https://minheedg.tistory.com/21

[이코테] DFS 와 BFS 개념