작성
·
195
답변 1
0
안녕하세요 햄버거님 ㅎㅎ
Q. 이 문제는 왜 DP로 접근해야 하는지
>>
보통 경우의 수 문제는 DP문제가 많습니다. 이걸 깔고 들어간건데요.
예를 들어
1 2 3 이라는 정점이 있고
1 -> 2 -> 3
1 -> 3
이렇게 경로가 있을 때 3까지 가는 경우의 수는 dp[3] += dp[2], dp[3] += dp[1] 이런식이 되어서 2가 될 겁니다. 즉, 경우의 수를 구할 때 그 직전이나 연결되어있는 정점의 경우의 수 상태값을 담아둔 배열의 요소를 더하게 되는 것이죠.
또한 이걸 완탐으로 만약에 풀게 되면... 굉장히 시간복잡도가 커질겁니다.
예를 들어
1 -> 2 -> 3 -> 4 랑
1 -> 2 -> 4 이렇게 되어있을 떄
1 -> 2는 중복된 경로입니다.
즉, 중복되는 문제인 것이죠. 이걸 DP를 통해 메모이제이션을 안하게 되면 해당 부분에 있어서 또한번 재귀함수가 호출이 되어야 할 것이고..
이는 큰 시간복잡도로 이어지게 됩니다.
그래서 DP로 풀어야 합니다.
정리하자면 다음과 같습니다.
1.경우의수 = 보통은 DP다
2.완탐으로 풀시에는 중복된 경우의 수 처리가 안되고 해당 부분을 계산하게 되서 시간복잡도가 너무 커진다 => 시간복잡도를 줄이는 방법인 DP를 생각해보자.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.