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

안녕하세요 수민님 ㅎㅎ

메인로직은 해당 함수에서 시간복잡도가 어느정도 큰 주요 로직이라고 보시면 됩니다.

다음 코드를 볼까요?

#include<bits/stdc++.h>
using namespace std;  
int N, cnt;
void solve(int N){
	cnt++;
	cout << cnt << '\n';
	if(N == 0) return;
	for(int i = 0; i < 3; i++){
		solve(N - 1);
	} 
	return;
}
int main(){
	cin >> N; 
	solve(N);    
	return 0;
} 

이 solve라는 함수에서 주요한 로직은

	for(int i = 0; i < 3; i++){
		solve(N - 1);
	} 

이부분입니다.

정확히는... 두가지의 로직이 합쳐져 있죠?

• 로직1 : 주어진 N에 대해 solve(N - 1)을 3번 재귀 호출

• 로직2 : 각 호출마다 cnt를 증가시키고 출력합니다.

여기서 메인로직이란 반복적으로(재귀적으로) 호출하는 부분이 시간복잡도가 크기 때문에 로직1이 됩니다.

다만 재귀함수에서 시간복잡도를 산정할 때는 여러가지 로직 중에서 재귀적으로 호출되는 함수부분과

다른 부분을 분리시켜서 봐야 하고

재귀적으로 호출되지 않는 부분중에 가장 시간복잡도가 큰 부분이 중요한 메인로직이 됩니다.

그리고 재귀함수의 시간복잡도는 해당 메인 로직 * 반복횟수로 결정됩니다.

void solve(int N){
	cnt++;
	cout << cnt << '\n';
	if(N == 0) return;
	for(int i = 0; i < 3; i++){
		solve(N - 1);
	} 
	return;
}

이코드에서 반복되는 for문을 제외하고 가장 큰 부분은 cout 부분 출력 = O(1)이기 때문에(로직2가 메인로직이 된다.)

	cout << cnt << '\n';

총 시간복잡도는 O(1) * 반복되는 횟수 = 3^n이 되어 3^n이 됩니다.

자 그러면... 이코드의 시간복잡도는 얼마일까요?

void solve(int N){
    cnt++;
    for(int i = 0; i < N; i++){
        cout << cnt << '\n';
    } 
    if(N == 0) return;
    for(int i = 0; i < 3; i++){
        solve(N - 1);
    } 
    return;
}

O(N) * 3^n이 되겠죠? 반복적으로 호출되는 부분 제외 -> 가장 큰부분 = for문 x 반복횟수가 되기 때문입니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

수민님~ 제가 답변을 수정해서 다시 달았습니다.

기존답변은 설명이 좀 부족했던 것 같습니다.

참고부탁드립니다. 😃