[알고리즘 문제풀이] 9. 모두의 약수(제한시간 1초)★

 

내가 푼 풀이

문제점: n이 1000을 넘어가게 되면 제한시간 1초를 넘어서게 된다.

#include <stdio.h>
using namespace std;
   
int main(){
   
   //freopen("input.txt", "rt", stdin);
   
   // 1. 자연수를 입력 받는다.
   int n = 0;
   int cnt = 0;
   scanf("%d", &n);
    
   // 2. 1부터 n까지 약수를 출력한다.
   for( int i = 1; i <= n; i++){
      cnt = 0;
      for( int j = 1; j <= i; j++){
         if( i % j == 0) cnt++;
      }
      
      printf("%d ", cnt);
   } 
    
   return 0;
}

 

정답대로 답은 나온다. 1초를 넘어설 뿐..

채점 결과: 시간 제한을 초과했다는 문구와 60점

 

 

---

실행 시간을 단축시키는 풀이

i는 1~n까지 돌고 j는i의 배수에만 cnt를 1씩 증가시켜준다.

#include <stdio.h>
int cnt[5001];
int main(void){
   //freopen("input.txt", "rt", stdin);
   
   // 1. 자연수를 입력 받는다.
   int n = 0;
   scanf("%d", &n);
    
   // 2. i는 1~n까지 돌고 j는i의 배수에만 cnt를 1씩 증가시켜준다. 
   for( int i = 1; i <= n; i++){
      for( int j = i; j <= n; j = j + i){
         cnt[j]++;
      }
  	}
      
    for( int i = 1; i <= n; i++){
    	printf("%d ", cnt[i]);
	}
}

1부터 n까지 i의 배수만큼 1씩 더해주는 아이디어.

와.. 어떻게 이런 생각을 할 수 있지

 

잉? 오히려 시간 제한이 더 많이 걸린다

뭐가 문제지

Q&A를 달아보자. -  컴퓨터 성능 차이라는데.. 아쉽다.. ㅠㅜ 

나중에 피시방 갈 일 생기면 한 번 코드 돌려봐야겠다.

 

 

 

 

 

 

위 아래 코드의 시간복잡도를 분석해보자

시간복잡도라 하면 연산의 횟수를 구하는 거라 생각하면 되겠습니다.

처리할 데이터의 크기가 n이고, 연산의 횟수를 구해주는 함수를 T(n)이라고 하겠습니다.

▣ 첫 번째 경우:

for(i=1; i<=n; i++){  //n회 반복

    for(j=1; j<=i; j++){  //평균 (n+1)/2 회 반복

           연산;

    }

}

위 코드의 T(n)=n*(n+1)/2 이고 Big-O 표기법은 차수가 낮은 항들과 계수를 무시하고 표현하므로 O(n^2)이라 합니다.

 

▣ 두번째 경우 : 

for(i=1; i<=n; i++){   //n회 반복

    for(j=1; j<=n; j=j*2){   //log n(밑은 2) 반복

            연산;

    }

}

위 코드의 경우 T(n)=n*logn 이고 Big-O 표기법으로는 O(nlogn)입니다.

 

for(i=1; i<=n; i++){  //n회 반복

    for(j=1; j<=n; j=j+i){ // n/i 회 반복 

           연산;

    }

}

코드의 경우 T(n)의 식을 n에 관한 다항식으로 표현하기 힘듭니다만 j 가 i의 증가율로 증가하므로 

위 코드가 "▣첫 번째 경우"의 코드 보다는 성능이 좋고 "▣두번째 경우"의 코드 보다는 성능이 떨어집니다.

즉 위코드의 성능이 O(n^2)과 O(nlogn)사이에 있으며 제가 봤을 때는 위 코드의 성능이 O(nlogn)에

가깝다고 생각합니다. 영상에서는 이정도의 근거로 제 느낌을 얘기한 것입니다.