며칠전 해결하지 못했던 알고리즘 강의의 문제를 해결했다. 3이 들어간 시각을 찾는 문제였다. 그당시 문제의 답을 미리 풀고 답을 낸 뒤, 코드를 짜서 나온 결론과 비교하는 방식으로 풀었더니 이상한 결과가 나왔었다. 이번에는 모든 경우의 수를 확인해서 답을 내는 코드로 짜봤더니 정답이 나왔다.
두번째 문제는 왕실의 나이트였다. 유튜브에서 나온 코드와 내 코드는 꽤 많이 달랐다. 영상 속 코드는 리스트를 이용해서 나이트가 이동 가능한 방향을 다 적어놓고 하나씩 비교해보는 코드였고, 나는 나이트의 현재 위치에 따라 이동 불가능한 위치를 빼주는 코드를 만들었다.
내가 짠 코드는 조건문과 반복되는 코드가 많아서 다양한 해결법을 고민해 볼 필요가 있다고 느꼈다.
아래는 그다음 영상을 보고 정리한 내용이다.
탐색
탐색이란 원하는 데이터를 찾는 과정을 말하고,
대표적인 그래프 탐색 알고리즘으로는 DFS/BFS가 있다.
그 전에 알아두어야 할 자료구조 두가지를 먼저 살펴보자
스택
- 먼저 들어온 데이터가 나중에 나가는 선입후출 자료구조이다.
- 입구와 출구가 동일한 형태로 시각화 가능하다.
- 파이썬에서는 리스트를 사용하면 스택 구현이 가능하다.
큐
- 먼저 들어온 데이터가 먼저 나가는 선입선출 자료구조이다.
- 입구와 출구가 모두 뚫려 있는 터널 형태로 시각화 가능하다.
- deque 라이브러리를 이용해서 파이썬에서 큐 구현이 가능하다.
- 리스트를 이용할 수도 있지만, 시간복잡도가 높아서 비효율적으로 동작할 수 있다.(파이썬)
- popleft함수로 deque에 들어간 첫번째 요소 삭제 가능하다.(파이썬)
참고 사이트 : https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3
