인프런 커뮤니티 질문&답변

안녕하세요 햄버거님 ㅎㅎ

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점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.