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

안녕하세요 kkh님 ㅎㅎ

코드와 시간복잡도 계산이 따로 놉니다.

	for(int i=start+1;i<26;i++){
		if(!is_okay(i))continue; 
		v.push_back(i);
		solve(v,i,k);
		v.pop_back();
	}

이부분이 핵심인데요.

이 코드는 for문 기반으로 함수를 호출하고 있습니다.

이 코드의 시간복잡도는 팩토리얼입니다.. 하하

그니까

26! *

25! *

24!

...

을 하신거에요.

0부터 26까지의 함수를 호출

그리고 다시 1 ~ 26까지의 함수를 호출 ... 또 그다음에 2 ~ 26를 호출하기 때문에 그렇습니다. (물론 isOkay가 어느정도는 막아줘서 정확히는 21!입니다.)

이전 시간복잡도 강의에서 설명드렸는데요.

예를 들어

void go(){
	go()
	go()
}

이런 함수는 2^n이 됩니다.

그리고...

void go(){
	go()
	go()

	go()
	go()
}

이런 함수는 4^n이 됩니다.

함수호출에 따라 시간복잡도 차이가 크죠?

시간복잡도는 함수호출 * 메인로직인데요.

kkh님 코드는 함수호출을 너무 많이 하는 로직이라 시간복잡도가 팩토리얼에 수렴해서 시간초과가 났다고 보시면 됩니다.

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

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

감사합니다.

강사 큰돌 올림.

안녕하세요, 인프런 AI 인턴입니다.

kkh185924님의 질문에 대해 답변드리겠습니다.

1. 시간복잡도 계산:
   제시하신 시간 복잡도 계산 방식은 기본적으로 적절하게 수행하신 것 같습니다. 여기서 21C(k-5)는 조합을 통해 가능한 모든 문자 선택 경우의 수를 계산하는 것이며, 50은 단어의 최대 개수, 15는 각 경우의 수를 계산할 때 필요한 시간으로 보입니다. 그렇기 때문에 21C(k-5) * 50 * 15는 브루트포스 방법을 사용할 때 예상되는 전체적인 시간 복잡도를 나타내는 것으로 보입니다.

2. 시간 초과 원인:
   저희가 제공하는 정보에 따르면 강의 내용과 직접적인 시간 초과 문제 해결 방법은 포함되어 있지 않습니다. 하지만 시간 초과가 발생하는 일반적인 원인은 다음과 같습니다:

• 알고리즘이 효율적이지 않거나 최적화가 필요할 경우
  
• 입력의 크기가 크고 처리해야 할 데이터의 양이 많은 경우
  
• 불필요한 계산을 많이 하는 경우
  

시간 초과를 해결하기 위해서는 코드의 최적화를 고려해야 합니다. 예를 들어, 백트래킹을 활용하여 불필요한 경우의 수를 줄이거나, 빠른 입출력 함수를 사용하거나, 다이나믹 프로그래밍 등을 통해 중복 계산을 줄이는 방법을 고려해보시는 것이 좋습니다.

문제를 자세히 들여다보고 어떤 부분에서 시간을 많이 소모하고 있는지, 어떤 최적화 방법을 적용할 수 있는지 고민해보시기 바랍니다.