📝 Day15. DFS

99클럽 코테 스터디 15일차 TIL + DFS

📍 오늘의 학습 키워드

• 그래프 탐색
• DFS (깊이 우선 탐색)
• 연결된 컴포넌트 찾기
• 인접 행렬

📝 공부한 내용 본인의 언어로 정리하기

오늘은 컴퓨터 네트워크 문제를 풀면서 DFS 알고리즘을 공부했다. DFS는 그래프에서 시작점부터 가능한 깊이까지 탐색한 후, 다시 돌아와 다른 경로를 탐색하는 방법이다. 이를 통해 연결된 모든 노드를 탐색할 수 있다. 네트워크 문제에서는 연결된 컴포넌트의 개수를 찾기 위해 각 컴퓨터를 방문하며 연결된 컴퓨터들을 모두 방문하는 DFS를 사용했다.

📖 오늘의 회고

📚 어떤 문제가 있었고, 나는 어떤 시도를 했는지

네트워크 문제를 처음 접했을 때, 컴퓨터 간의 연결 상태를 어떻게 효율적으로 탐색할지 고민했다. 처음에는 모든 가능한 경로를 일일이 확인해야 하는지에 대해 고민했으나, 그래프 탐색 알고리즘인 DFS와 BFS를 떠올리게 되었다.

🤔 어떻게 해결했는지

🔖 참고링크 (https://develop-tracking.tistory.com/79)

문제를 그래프 탐색 문제로 재구성한 후, DFS 알고리즘을 사용하여 각 컴퓨터를 탐색하기로 했다. DFS를 통해 하나의 컴퓨터에서 시작해 연결된 모든 컴퓨터를 방문한 후, 새로운 컴퓨터를 시작점으로 DFS를 반복하여 네트워크의 개수를 세었다.

문제를 해결하기 위해 먼저 그래프를 이해하고, DFS 알고리즘을 사용하여 연결된 컴퓨터들을 찾았습니다. 그 후에는 다른 알고리즘인 BFS나 수학적 접근 방식도 고려해보며 다양한 해결책을 고려했습니다.

🤓 무엇을 새롭게 알았는지

오늘은 네트워크 문제를 풀면서 그래프 탐색 알고리즘과 수학적 접근 방식을 사용하여 문제를 해결하는 방법을 배웠습니다. 다양한 알고리즘과 접근 방식을 사용할 수 있다는 것을 알게 되었습니다.

• DFS와 BFS의 차이점과 각각의 사용 사례를 명확히 이해하게 되었다.
• 인접 행렬을 사용하여 그래프를 표현하고 탐색하는 방법을 익혔다.
• 연결된 컴포넌트를 찾기 위해 DFS를 사용하는 방법을 배웠다.

⏳ 내일 학습할 것은 무엇인지

• BFS 알고리즘을 사용한 그래프 탐색 방법을 더 깊이 이해하고 문제에 적용해보기.
• 다른 유형의 그래프 탐색 문제를 풀어보며 다양한 그래프 탐색 기법 익히기.
• 그래프 관련 알고리즘의 시간 복잡도 분석과 최적화 방법 학습.