[ TIL - PGS ] 99클럽 코테 스터디 18일차 TIL + 오늘의 학습 가이드

💡 오늘의 학습 키워드

• 깊이/너비 우선 탐색(DFS/BFS)

 

✅ 오늘 공부한 내용

• 깊이 우선 탐색
• 오늘의 백준 문제! 단지번호붙이기

 

👀 오늘의 회고

🤣 오늘의 문제점

• 오늘은... 어제 공부 안한 탓에..아예 시도조차 하지 못했다.
• 대신 오늘 DFS에 대한 강의를 듣고 어떻게 구조를 짜야하는가 배웠다..
• 그런데 얘네가 양방향 연결 리스트를 위해 ArrayList를 또 다른 배열 형태로 선언해서 쓰길래 너무 생소해서 그것도 다시 공부를 해야하는...상황에 놓였다 
• 어제 내가 참고했었던 풀이법에서는 또 다른 방식으로 푸셨어서 어떤 걸 써볼 지 고민이 되었다 🤔
• 왜냐면 오늘 문제는 BFS인 것 같아서 내일 또다시 공부를 해야만 한다 🤣

 

🔥 어떤 시도를 했는가?

• 일단 초반엔 스택으로 하려고 했는데 양방향 연결 리스트 때문에.. 일단 ArrayList를 객체가 담는 형식으로 시도를 해봐야 했다.
• 또한, for문과 여러 배열을 사용하기 때문에 메모리가 덜 먹는 방향을 고안해야 했다.

 

👏 무엇을 새로 알았는가?

• 일단 깊이 우선 탐색(DFS)가 무엇인가?
  • 그래프 완전 탐색 기법 중 하나
  • 시작 노드에서 출발하여 탐색할 한 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘
  • 재귀 함수로 구현 -> 단, 스택 오버플로에 유의해야 한다.
  • 시간 복잡도는 노드 수 V, 엣지 수 E라고 치면 O(V + E)이다.
  • 스택 자료 구조를 이용한다. First In Last Out
  • 한번 방문한 노드는 다시 방문하면 안되기 때문에 노드 방문 여부를 체크할 배열이 필요하다.
  • 그래프는 인접 리스트이다.
• DFS의 흐름
  • 먼저, 시작 노드를 정해야 한다. 그리고 자료 구조를 초기화 시켜줘야 한다.
  • 아래와  같은 원본 그래프를 인접리스트로 바꿔서 본다.
  • 그 이후 방문 배열로 계속 체크를 해준다.
  • 두 번째로는 스택에서 노드를 꺼낸 노드의 인접 노드를 다시 스택에 삽입해주고
  • 세 번째로는 스택 자료 구조의 값이 없을 때 까지 반복해준다.
  • 다녀간 노드는 방문 배열을 바탕으로 재삽입하지 않는다.

• 위 과정을 거치면 해당 그래프를 다양한 방법으로 활용할 수 있다.
• 그런데 인접 리스트를 어떤 방식으로 다룰지에 대해 더 공부를 해야할 것 같다.

 

 

👩‍💻 내일은 무엇을 학습할 것인가?

• 항해 99 문제 풀기
• 책 읽기
• 못 푼 문제 및 DFS 마저 정리하기