(문제보기)

1. 문제 분석

시간 복잡도가 O(n²)인 정렬 알고리즘으로도 해결할 수 있는 문제이다.

삽입정렬, 거품정렬 등이 존재하는데 거품정렬을 사용하여서 문제를 해결하겠다.

2. 거품 정렬(Bubble Sort)

5칸짜리 배열을 예시로 들어보면,

각 단계에 따라 두개씩 짝을 지어서 비교한다. 만약 이동할 필요가 있다면 두 값을 바꾼다.
다음 단계에는 범위를 한칸 늘려서 비교하며 맨 처음 요소까지 비교할 때 까지 반복한다.

비교적 간단한 방법의 정렬 방법이다.

3. 소스코드

// #2750

#include<stdio.h>

int main(void){
        int N;
        int arr[1000];

        scanf("%d", &N);

        for(int i=0; i<N; i++)
                scanf("%d", &arr[i]);



        for(int i=N-1; i>0; i--)
                for(int j=i; j<N; j++)
                        if(arr[j-1]>arr[j]){
                                int temp = arr[j-1];
                                arr[j-1] = arr[j];
                                arr[j] = temp;
                        }

        for(int i=0; i<N; i++)
                printf("%d\n", arr[i]);

        return 0;
}

(문제보기)

1. 문제분석

무려 정답 비율이 27.321%, 매우 낮은 정답률을 보여주고 있는 문제이다.

문제의 요구사항은 매우 간단하다.

• 시작숫자 M과 끝 숫자 N을 준다.
• M과 N 사이의 소수를 모두 출력하라.

다만, 시간제한이 빡빡해서 앞에서 해결한 소수의 풀이방법으로는 안풀린다.

모두 시간초과에 걸리기 때문이다..

그래서 소수를 찾는 다른 방법이 있나 찾아봤다.

2. 에라토스테네스의 체

소수를 구하는 방법중 아주 유명한 방법인 에라토스테네스의 체라는 방법이 있었다.

사실 나도 잘 몰랐는데,,, 이 방법에서의 핵심 사항은 다음과 같다.

• N에 대하여, N은 제곱근 N보다 크지않은 어떤 소수로도 나누어지지 않는다.
• 즉, (어떤수)/(어떤수) = 몫 + 나머지에서, 몫과 나머지 둘둥 하나는 무조건 N의 제곱근보다 작다.
• 쉽게 말하면 제곱근N보다 큰 소수로는 나눠지지 않으므로 소수임을 판별할 때 제곱근N 이하의 수만 비교하면 된다.

여기서 에라토스테네스의 채라는 방법이 있다.

어떤 구간이 있을 때, 작은 값부터 소수를 찾아가는데, 소수를 찾았다면 그의 배수들은 모두 제외한다.

예시로, 3~10의 구간이 있다고 생각해보자.

 [ 3 4 5 6 7 8 9 10 ] 

먼저, 소수 2를 찾았다. 그러므로 2의 배수들은 구간에서 모두 제외된다.

[ 3 4 5 6 7 8 9 10 ]

다음, 소수 3을 찾았다. 3의 배수들을 모두 제외한다.

[ 3 4 5 6 7 8 9 10 ]

다음은 소수 5, 다음은 소수 7을 찾는다. 나머지는 소수가 아니므로 소수 찾기가 끝난다.

[ 3 4 5 6 7 8 9 10 ]

소수 : 3, 5, 7

이 방법에서 위의 핵심사항을 적용시킨다.

즉, 소수를 계속해서 찾아 나가나, 제곱근N까지만 찾는 것이다.

에라토스테네스의 체와 관련된 내용은 구글에 검색하면 더 좋은 자료들이 많다. 참고하길 바란다.

3. 소스코드

이전에 해결했던 소스코드가 재채점 되면서 틀렸습니다.

따라서 소스코드를 수정했습니다.

#include<iostream>
#include<math.h>

using namespace std;

int main(void) {
	int arr[1001] = { 0 };
	int m, n;
	cin >> m >> n;

	int max;

	int cnt = 0;
	for (int i = m; i <= n; i++) {
		max = sqrt(i);
		cnt = 0;
		for (int j = 2; j <= max; j++) {
			if (i % j == 0) cnt++;
			if (cnt != 0) {
				arr[i] = -1;
				break;
			}
		}
		if (cnt == 0) arr[i] = 1;
	}

	arr[1] = -1;
	for (int i = m; i <= n; i++)
		if (arr[i] != -1) cout << i << "\n";
}

이전 소스코드.

더보기

// #1929
#include<stdio.h>
#include<math.h>

int main(void){
        int M, N;
        int length;
        scanf("%d %d", &M, &N);

        length = N-M+1;

        int array[length];
        //set array
        for(int i=0; i<length; i++){
                array[i] = M;
                M++;
        }


        //select data
        for(int i=2; i<sqrt(N); i++)
                for(int j=0; j<length; j++)
                        if(array[j] != -1 && array[j]%i == 0 && array[j] != i)
                                array[j] = -1;

        //1 is not prime number
        if(array[0] == 1) array[0] = -1;

        //print prime number
        for(int i=0; i<length; i++)
                if(array[i] != -1) printf("%d\n", array[i]);

        return 0;
}

 

소스자체가 깔끔하진 않지만,,, 돌아간다는 것이 감격스러웠다.

 

비록 중간중간에 딴짓을 하긴 했는데 한문제로 무려 2시간이나 잡아먹었다.

정답률이 왜 낮은지 알것 같았다.

 

소스코드를 최적화하고 싶은데... 이렇게 많이 시도를 하니까 지친다...

그러니까 소스가 좀 더러워도 이해해주면 감사하겠다..

(문제보기)

1. 문제 분석

간단한 문제이다.

정수 N이 주어졌을때 소인수 분해를 하는 프로그램이다.

소인수를 하나 선언하고, 2부터 시작하여 모드연산이 0이 되는 값을 만나면 소인수를 출력하고 N값을 소인수로 나눠준다. 만약 나눌 수 없다면 소인수 값을 1 증가 시킨다.

이 과정을 N이 1이 될 때 까지 반복하면 해결될 것이다.

(N이 1이 되면 더이상 소인수 분해를 할 수 없으므로)

2. 소스코드

// #11653

#include<stdio.h>
int main(void){
        int N;
        //1 is not prime number
        int prime_factor = 2;
        scanf("%d", &N);

        while(N != 1){
                if(N%prime_factor == 0){
                        printf("%d\n", prime_factor);
                        N = N/prime_factor;
                }
                else
                        prime_factor++;
        }

        return 0;
}

(문제보기)

1. 문제 분석

이전 문제에서 푼 소수의 다른 버전이다.

M, N을 입력받아 두 숫자 사이의 소수의 합을 더한 결과와 제일 작은 소수의 값을 출력하는 문제이다.

단 범위 내에 소수가 없을 경우 -1을 출력한다.

위의 조건을 따르고 이전의 구현을 참고하면 어렵지 않은 구현이 될것이다.

2. 소스코드

// #2581


#include<stdio.h>

int main(void){
        int N, M;
        int count;
        int sum=0;
        int min=10000;
        int result = 0;

        scanf("%d", &M);
        getchar();
        scanf("%d", &N);

        for(int i=M; i<=N; i++){
                count = -1;

                // if mod = 0, count++
                for(int j=1; j<=i; j++)
                        if(i%j == 0)
                                count++;

                if(count == 1){
                        sum += i;
                        if(min>i) min = i;
                }
        }

        if(sum == 0) printf("-1\n");
        else
                printf("%d\n%d\n", sum, min);
        return 0;
}

(문제보기)

1. 문제 분석

문제의 단계를 분석하면 다음과 같다.

1. N을 입력받고 N개의 숫자를 입력받음

2. 소수인지 아닌지 분류하기

   -> 1 또는 자기 자신으로만 나눌 수 있는 숫자

3. 분류된 소수의 총 개수를 출력하기

소수인지 아닌지 확인하기 위하여 mod연산을 사용했다.

또한 1은 소수가 아니므로 1을 걸러낼 수 있는 장치가 필요하다.

2. 소스코드

// #1978


#include<stdio.h>

int main(void){
        int N;
        int temp;
        int count;
        int result = 0;

        scanf("%d", &N);
        getchar();

        for(int i=0; i<N; i++){
                scanf("%d", &temp);
                count = -1;

                // if mod = 0, count++
                for(int j=1; j<=temp; j++)
                        if(temp%j == 0)
                                count++;

                if(count == 1)
                        result++;
        }

        printf("%d\n", result);
        return 0;
}

count를 활용하여 모드연산을 하여 0이 나오면 count를 증가시키고,

count를 -1로 초기화 하여서 1일경우 count가 1번만 증가한다.

이를 활용하여 count가 1일 경우에만 소수로 판별하고 result를 증가시키고, 반복이 N만큼 되면 result를 출력하는 형식으로 프로그래밍 하였다.

(문제보기)

1. 문제 살펴보기

연속된 숫자 666이 들어간 값을 계속해서 찾는 문제이다.

166, 1666, 2666, 3666, ... 

여기서 주의할 사항은 N+'666' 만으로는 풀 수 없다.

6336663 와 같이 중간에 666이 들어가 있거나,

6660, 6661, 6662, ... 와 같이 666이 쭉 이어지는 구간이 존재한다.

즉, 이 문제를 풀기 위한 단계는 두가지로 나눌 수 있다.

1. 연속된 숫자(666)을 찾는다.
2. 1번을 N개 찾을때까지 반복한다.

그렇기 위해서는 다음을 고안해야한다.

• 연속된 숫자(666)를 찾는 방법

이번 문제에서는 3칸짜리 작은 큐를 하나 만들어서 진행하였다.

666 을 예시로 들어보겠다.

1. 큐를 -1로 초기화 한다.

2. 값을 10으로 모드연산 한 값을 큐에 넣는다. ( 666%6 )

   단, 배열의 2번째, 1번째, 0번째 인덱스 순으로 처음엔 넣는다.

3. 이후 값을 10으로 나눠준다. (666/10 = 66)

4. 큐를 확인하여 666이 저장되어 있는지 확인하고, 저장되어있다면 count를 1 증가시킨다.

   그렇지 않다면 다음 단계로 진행한다.

5. 2번으로 돌아가서 반복한다. 값이 0이 된다면 반복을 종료한다.

이 과정을 진행하면 다음과 같은 과정이 진행된다.

(2번째 반복, 시작값 66)

큐 확인결과 : 666이 아님

(3번째 반복, 시작값 6)

큐 확인 결과 : 666 발견. count 증가

위의 방법을 사용한다면 작은 값부터 비교를 진행하기 때문에 문제의 요구조건을 만족할 수 있다.

이제 남은 일은 연속된 숫자를 찾는 방법을 고안했으니, N번째 숫자를 찾을 때 까지 반복하는 일만 남았다.

이를 위하여 count라는 변수를 만들었고, count가 N과 동일해지면 반복을 중단하면 된다.

2. 소스코드

// #1436

#include<stdio.h>

int queue[3] = {-1, -1, -1};

//init Queue
void init(){
        for(int i=0; i<3; i++)
                queue[i] = -1;
}

//insert
void inqueue(int input){
        if(queue[2] == -1)
                queue[2] = input;
        else if(queue[1] == -1)
                queue[1] = input;
        else if(queue[0] == -1)
                queue[0] = input;
        else{
                queue[2] = queue[1];
                queue[1] = queue[0];
                queue[0] = input;
        }
}

//check 666
int check(){
        if(queue[0] == 6 && queue[1] == 6 && queue[2] == 6)
                return 1;
        else
                return 0;
}

int main(void){
        int N;
        int num=0;
        int count = 0;

        scanf("%d", &N);

        while(count != N){
                num++;
                int temp = num;
                init();
                while(temp != 0){
                        inqueue(temp%10);
                        temp = temp/10;

                        //find 666
                        if(check()){
                                count++;
                                break;
                        }
                }
        }

        printf("%d", num);
        return 0;
}

큐를 사용하다보니 함수를 몇개 나눠서 코드를 작성했다.

큐에 삽입하는 방법은 쉬엄쉬엄 만들긴 했는데 채점엔 별 이상 없었다.

물론 큐가 저렇게 작으면 그냥 인덱스에 바로 접근해서 비교하는게 훨씬 나을것 같다는 생각도 든다..