글 읽기 - 이 코드의 시간복잡도가 어떻게 되나요??

rhsnfl1122 3년 전 0

do while문 안에 for문이 있다고 생각하고 O(n^2)이라고 생각하면 되나요?

재귀함수가 나오면 시간복잡도 계산할 때마다 헷갈리네요..

#include <stdio.h>
#include <stdlib.h>

int SelfNumber(int a, int* arr)
{
	if (a >= 10000 )
		return 0;

	int sum, factor;

	sum = a;

	do {
		sum += a % 10;
		a /= 10;
	} while (a != 0);
	
	if (sum <= 10000) 
	{
		if (arr[sum] == 1)		//연산 시간 축소를 위해서 같은 숫자가 나오면 재귀를 멈춤
			return 0;

		arr[sum] = 1;			//selfnumber가 아닌 숫자를 arr배열에 표시함
	}
	SelfNumber(sum, arr);
}

int SelfNumberProblem()
{
	int num = 1, i;
	int arr[10001] = { 0 };
	
	do {
		if (arr[num] == 0)
			SelfNumber(num, arr);
		num++;
	} while (num < 10000);

	for (i = 1; i <= 10000; i++)
		if (arr[i] == 0)
			printf("%d\n", i);

}

ckdgus2482 3년 전 0

메모이제이션을 통해 중복 계산을 피하고 있기 때문에 O(N)입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이 코드의 시간복잡도가 어떻게 되나요??

rhsnfl1122 3년 전 0

ckdgus2482 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말