인프런 커뮤니티 질문&답변
작성한 질문수
고급 BFS, DFS 는 어떻게 공부해야 할까요?
해결된 질문
작성
·
81
0
안녕하세요! 하반기 채용 때문에 코딩테스트 찾아보다가 제가 너무 원했던 강의라서 결제 후에 개념 위주로 빠르게 보는 중입니다.
요약하자면 코딩테스트에서 DFS나 BFS 문제들이 나올 시에 기본적인 내용 + 문제해결력(테크닉) 으로 나오는 것 같은데
테크닉 적인 부분은 어떻게 공부를 해야될까요? 가령
https://school.programmers.co.kr/learn/courses/30/lessons/1832
풀이를 찾아보면 3차원(checked)으로 풀면 풀리긴 하는데, 제 직관으로는 각 그래프 경로를 분리해낸다는 컨셉이 당연하게 느껴지지가 않더라구요.
이런 까다로운 문제를 상대하려면 어떤 부분이 잘 준비되어 있어야 할까요? 강의 중에 비슷한 문제가 있다면 그부분 해설강의 꼼꼼히 봐보려고 합니다
답변 1
0
안녕하세요. lee님!
해당 문제는 그래프로 해석해서 푸는 것보단, DP로 해석해서 푸는 것이 더 적합하다고 할 수 있습니다.
[DP로 해석해서 푸는 게 더 타당한 이유]
'섹션4의. 실전 문제풀이1' DP 문제인 'BOJ 11726' 강의에서 ‘경우의 수를 구하는 문제이고 경우의 수를 어떤 수로 나눈 나머지를 구하는 형식의 문제라면 DP문제일 확률이 높다’고 언급하였으니 해당 강의를 참고해보시면 좋을 거 같습니다.
[DP 관련 문제를 잘 푸는 법]
DP 문제를 잘 풀려면 문제의 재귀적인 구조를 찾아 DP Table을 적절히 만들 수 있어야 하는데요.
예를 들어, 올려주신 문제에서는 DP Table을 dp[i][j]를 (i, j)까지 도달하는 경우의 수로 정의해보면 문제를 쉽게 접근할 수 있습니다.
정확하게는 보행할 수 없는 경우도 고려해야 하므로 dp[i][j]를 위에서 왔는지 왼쪽에서 왔는지를 고려해주어야 합니다.
따라서 dp[i][j] = {(i- 1, j)에서 (i, j)를 왔을 때의 경우의 수, (i, j - 1)에서 (i, j)를 왔을 때의 경우의 수} 와 같이 dp[i][j]는 2가지 정보를 담게끔 DP Table을 설계해줘야 합니다.
위와 같이 DP Table을 잘 설계하면 쉽게 풀 수 있는 문제입니다.
위 답변이 잘 이해가 안 가신다면, DP 관련 강의인 '섹션3. 필수 알고리즘1'의 DP와 관련된 강의들을 최대한 이해하며 들으시는 것을 추천드립니다.
더불어 여유가 되신다면 '섹션3. 필수 알고리즘1'의 브루트포스 알고리즘 관련 내용도 들으시면 문제를 접근할 때 도움이 많이 될 거 같습니다.
[추가적으로]
추가적으로 문제를 접근할 때 그래프 문제가 아닌 문제를 그래프 문제로 해석하여 접근하는 경우가 빈번하다면 '섹션6. 그래프 알고리즘' 파트를 보시면 그래프는 어떤 문제에 쓰이는지 더 잘 이해하실 수 있을겁니다.
혹여나 DP 파트를 수강한 후에도 올려주신 문제나 DP 문제에 대해 이해가 안 가신다면, 추가 질문 남겨주세요.
또 궁금하신 점 있으시면 언제든 질문 부탁드립니다.
감사합니다. :)
정말 감사합니다! 답글 달아주신것 보고 소름이 돋았습니다. 초보자도 이해할 수 있게 적어주셔서 정말 감사합니다.
말씀대로 DP로 풀으면 빠르다고 대놓고 요구하는 문제였는데 제가 눈에 뭐가 씌였는지 이상하게 돌아가려고 했었네요
DP가 익숙해지지 않아서 DP로 안풀려고 무의식중에 피했던 것 같습니다
말씀해주신 강의 부분 꼼꼼히 들으면서 바꿔보겠습니다 정말 감사합니다!