✍️오늘 공부한 내용

• 백준 문제 풀이
  • 2252번 줄 세우기
  • 2573번 빙산
  • 21606번 아침산책

📋새로 배우게 된 내용

• 알고리즘 공부를 같이 하고 있는 동료들에게 어떻게 하면 문제들을 잘 풀 수 있는 지 물어봤는데 input, 함수 def , output 3부분으로 나눈다면 def 틀은 최대한 건드리지 않고 코드를 구현하는게 좋다고 했다.
• 이번에는 bfs,dfs,다익스트라에 이어 위상정렬 풀이접근도 분석해봤다.

😜bfs , dfs 문제 풀이 방식 공통

1. vertex 방문 graph만들어주기
2. 방문여부 그래프 만들어주기
3. edge개수만큼 연결 상태 나타내기
4. 함수 선언하고 vertex인덱스 인자로 받기
5. 큐(bfs) 또는 재귀함수(dfs)로 방문여부 반영
   (추가 분석➕➕)
   ✔️ bfs는 deque를 import해서 leftpop()한 가장 먼저 탐색한 값을 가지고 다음 vertex로 탐색진행을 따지는 경우
   ✔️ dfs는 vertex 하나를 잡고 방문여부를 기준으로 탐색진행을 따지는 경우 (이미 방문을 했다면 재귀빠져나가기)
   ✔️ 다익스트라는 heapq를 import해서 edge가 지닌 weight를 기준으로 우선순위 큐를 활용해서 우선순위를 따지는 경우
   ✔️ 위상정렬은 1. 진입 차수가 0인 정점을 큐에 삽입한다. 2. 큐에서 원소를 꺼내 해당 원소에 연결된 간선을 제거한다. 3. 간선을 제거한 후 진입 차수가 0이 된 정점을 큐에 삽입한다. 4. 위 과정을 반복한다

🫥오해했던 점

• 지금까지 dfs문제를 풀 때 간선 연결을 이중배열로 나타냈었는데 (0==연결X, 1==연결O) dict형태로 구현해보려고 했는데 트리라서 그래프에서 하려다보니 안되는 건가? 싶었는데
• 👉여기를 참고해보니 꼭 그렇지는 않은듯.
• bfs, dfs문제 풀이 핵심 중 하나인 방문여부도 표현을 해야지 가능한 접근이 아닐까 싶다.
• 이중배열로 풀면 간선정보와 방문여부를 나타낸 그래프 각각이 같은 구조 (배열 인덱스로 해당 vertex 접근)이기 떄문에 더 복잡하게 생각하지 않아도 돼서 편하려면 이중배열로 가는게 맞다고 생각이 들었다.

🤯어려웠던 점

1. 위상정렬은 아직 이해가 덜 돼서 다시 봐야겠다.

🤔아쉬웠던 점

• 이번주 알고리즘 주차가 마무리되는데 아직 풀지 못한 문제들이 좀 많아서 아쉽다. 개념정리를 다시 하면서 문제들을 마저 풀도록 해야겠다.

😝느낀점

• 정형화된 풀이 방법이 있는데 복잡미묘한 기분이 든다.
  • 😇 정형화된 풀이? 오 그럼 연습만 충분히 하면 뭐든 풀 수 있겠네!
  • 😈 아, 뭔가 다르게 이 문제를 풀 수 있는 방법이 없을까? 접근방법을 아예 달리해서 푸는 방법이?
• 이 둘 사이에서 갈등했었는데, 시간과의 싸움에서 😇편에 붙기로 함.
• 앞으로 많은 문제들을 풀어보면서 더욱 익숙해져야겠다.

👊다짐

• 1일 1커밋🤔 1일 1코테 문제풀이😁

🚀오늘의 한줄평

• dfs, bfs개념은 알고리즘에 있어서 중요하니까 또보고 또보자 🤨