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

욕망의햄버거님의 프로필 이미지

작성한 질문수

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

7-B

7-B 강의 질문

23.11.14 21:44 작성

·

189

0

안녕하세요 큰돌 선생님!

강의를 여러번 보고서도 이해가 되지 않아서 질문 남깁니다.

 

Q. 이 문제는 왜 DP로 접근해야 하는지 보충 설명을 추가해주시면 감사하겠습니다... 브루트포스 느낌인건 알겟는데 경우의 수를 계산하기 위해서 식을 어떻게 세워야 할 지 논리적으로 맞는지를 잘 모르겠습니다... 도와주시면 감사하겠습니다!

답변 1

0

큰돌님의 프로필 이미지
큰돌
지식공유자

2023. 11. 15. 08:48

안녕하세요 햄버거님 ㅎㅎ

 

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

감사합니다.

강사 큰돌 올림.