인프런 영문 브랜드 로고
인프런 영문 브랜드 로고

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

Helldo님의 프로필 이미지

작성한 질문수

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

1주차 개념 #5-2. 문제로 연습하는 시간복잡도 Q3 점화식 설명

왜 당연히 n=8일때 아래 가지가 2개씩 늘어나나요?

해결된 질문

작성

·

40

0

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

 

강의 1주차 개념 #5-2의 1분 59초

 

안녕하세요 큰돌님 n=4일때는 그냥 2n-1으로

7번 반복됨을 아는데 왜 당연하게 n=8일때는 아래 8개가 늘어나는지가 궁금합니다.

 

물론 직접 해보면 저렇게 되는것을 알고 있긴한데 어떤 이유에서 저렇게 당연하게 말씀하신게 궁금합니다.

답변 2

0

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

안녕하세요 ㅎㅎ

왜 당연하게 n=8일때는 아래 8개가 늘어나는지가 궁금합니다.

-> 코드를 보시면 n이 8일 때 8을 계속 둘로 나눠서 함수가 호출이 되죠?

00:03 부분.

8 -> 4 -> 2 -> 1

이렇게 호출이 되는데 부분을 설명한 부분인데요 ㅎㅎ

아래 8개가 늘어나는 것은 마지막 기저사례, l과 r이 같을 때가 n만큼 있기 때문에 ex) 1, 2, 3, 4, 5, 6, 7, 8 8개가 호출되는 것입니다.

 

감사합니다.

0

인프런 AI 인턴님의 프로필 이미지

안녕하세요, 인프런 AI 인턴입니다. Helldo님, 질문하신 내용에 대해 관련된 답변을 찾아보았습니다.

해당 강의에서 언급한 알고리즘에서 특정 경우 루프가 어떤 방식으로 증가하는지에 대한 질문을 이해하도록 돕겠습니다. n 값이 증가함에 따라 재귀적 또는 반복적인 호출이 지수적으로 증가하는 경우, 각 단계에서 가지가 두 배로 늘어나는 패턴이 발생할 수 있습니다. 이는 주로 문제 해결을 위한 모든 가능한 집합을 고려할 때, 각 선택이 결과적으로 두 가지 가능한 상태(예: 선택 여부)를 가지기 때문입니다.

관련된 질문과 답변을 제공하는 게시물을 직접 확인하시어 추가적인 이해를 도모하시는 것이 좋겠습니다.

  1. 수업노트 관련 질문있습니다.: 이 질문에서는 재귀적인 문제 풀이와 선택의 경우의 수에 대해 설명하고 있습니다. 이는 각 단계에서 가지가 증가하는 패턴을 이해하는데 도움이 될 수 있습니다.

질문하신 주제는 알고리즘의 기본적인 재귀 구조와 관련된 것으로 보입니다. n 값이 커질수록 문제의 복잡도가 기하급수적으로 증가할 수 있으며, 이는 재귀적 호출이 각 단계에서 여러 번 발생하기 때문입니다. 예를 들어, n=4일 때 각 단계마다 두 가지 선택지를 고려한다고 가정하면, n=8일 경우에는 그 선택지가 두 배로 확장되어 더 많은 경우의 수를 가지게 됩니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

Helldo님의 프로필 이미지

작성한 질문수

질문하기