오늘 한 일
- 미니 프로젝트 회고 및 GitHub 리포지토리 README 작성을 완료했다.
- 재귀, 정렬, 완전 탐색 알고리즘 문제들을 의사코드부터 다시 작성하며 복습했다.
- 코치님과 면담을 통해 알고리즘 공부 방향성을 재설정했다.
- CSAPP 1장을 완독했다.
배운 점
-
DFS의 핵심은 '상태' 전달이다. DFS 함수를 설계할 때 매개변수는 다음 재귀 호출에 필요한 '상태(state)' 정보의 집합이라는 것을 명확히 이해했다. 현재 위치, 방문 기록, 특정 조건 등 문제 해결에 필요한 모든 요소를 상태로 보고 매개변수로 넘겨야 한다.
-
알고리즘 공부는 '양보다 질'이다. 무작정 많은 문제를 푸는 것보다, 풀었던 문제라도 다른 접근법을 고민하고 컴퓨팅 사고(Computational Thinking) 자체를 훈련하는 것이 중요하다는 것을 깨달았다. 해결의 본질에 집중하는 공부법을 적용해봐야겠다.
-
마크다운 작성에 익숙해지고 있다. 회고와 README를 직접 작성하면서 이전보다 마크다운 문법을 더 적극적으로 활용하게 되었다. 문서를 구조화하고 꾸미는 과정에서 재미를 느끼기 시작했다.
어려웠던 점 & 해결
DFS: '어떤 상태를 넘길 것인가'에 대한 고민
어려웠던 점
- 막연한 매개변수 설정: DFS 함수를 작성할 때, 재귀 호출에 어떤 값을 넘겨야 할지 항상 막막했다. 특히 백준 2468번 (안전 영역) 문제에서
dfs(row)와 같이 단순히 행(row)만 넘기는 잘못된 설계를 하여 '연결된 덩어리'를 찾는 데 실패했다. - 잘못된 종료 조건: DFS의 구조를 잘못 이해하다 보니, 어디서 재귀를 멈춰야 하는지에 대한 '종료 조건'을 찾는 데 어려움을 겪었다.
해결 및 깨달음
- DFS 매개변수는 '다음 상태에 필요한 정보'다: DFS의 매개변수는 다음 탐색 단계로 넘겨주어야 할 '상태(state)' 그 자체라는 것을 깨달았다. 2차원 공간 탐색에서는 현재 위치
(x, y)가 가장 기본적인 상태이며, 문제에 따라 방문 기록(visited), 탐색 깊이(depth), 현재까지의 합(sum) 등이 추가 상태가 될 수 있다. - DFS의 암시적 종료: 올바른 DFS는 더 이상 방문할 곳(유효한 범위 내의, 방문하지 않은, 조건을 만족하는 노드)이 없을 때 자연스럽게 종료된다. 명시적인
if (조건) return;형태의 종료문이 항상 필요한 것은 아니었다. - 역할 분리의 중요성:
is_safe_area라는boolean배열을 미리 계산하여 DFS에 넘겨주는 아이디어를 통해, **'탐색할 지도를 만드는 과정'**과 **'만들어진 지도를 탐색하는 과정'**을 분리할 수 있었다. 이로 인해 코드가 더 명확해지고 각 함수의 책임이 단순해졌다.