GDSC Ewha 아침 스터디 TIL 11일차 💛

오늘 GDSC 아침 스터디 시간에는 백준 알고리즘 문제 풀이를 진행했습니다! 이번 문제는 총 두 번의 시도 끝에 답을 맞출 수 있었습니다. 

 

처음으로 한 풀이는 시간 초과..! 로 실패..😂

 

 

// 백준 1929번 소수 구하기

#include <stdio.h>
#pragma warning(disable:4996)

int main()
{
int M, N, boolean = 0, j;
scanf("%d %d", &M, &N);

for (int i = M; i < N; i++)
{
for (j = 2; j < i; j++)
{
if (i % j == 0)
{
boolean++;
}
}
if (boolean == 0)
{
printf("%d\n", j);
}
boolean = 0;

}

return 0;
}

 

위 코드는 제가 처음으로 풀이한 일반적인 소수 구하기 코드입니다. 코드 자체에는 문제가 없으나 반복문을 과도하게 사용하면서 입력값이 커졌을 경우 제한된 시간 (2초) 내에 작업을 완수하지 못 하기 때문에 틀린 답안으로 인정되었습니다.

 

// 백준 1929번 소수 구하기 재시도

#include <stdio.h>
#pragma warning(disable:4996)

int main()
{
int M, N;
int arr[1000001] = {0};


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

for (int i = 2; i <= N; i++)
{
for (int j = 2; i * j <= N; j++) {
arr[i * j] = 1;
}
}

 

arr[1] = 1;
for (int i = M; i <= N; i++)
{
if (arr[i] == 0)
{
printf("%d\n", i);
}
}
return 0;
}

  

시간 초과 에러를 해결해 본 경험이 많지 않아서 어떻게 하면 시간을 줄일 수 있을지 고민을 많이 해 보았습니다. 거듭된 고민의 결과 풀이 방향이 크게 두 가지로 좁혀졌는데, 

첫 번째는 이차원 배열을 이용해 소수가 아닌 값들을 행렬의 규칙을 찾아 소거하는 방법이었고

두 번째는 중첩 반복문을 이용해 2의 배수, 3의 배수, 4의 배수...를 소거하는 방법이었습니다. 

 

첫 번째 방법의 경우 N보다 작은 소수를 모두 구해야 한다는 점과 배열에서 찾을 수 있는 규칙성이 한계가 있다고 판단되어 보류하였고,

https://velog.io/@usoab0561/백준-1929번-소수구하기-성공 << 해당 블로그 글을 참고한 후 

백준 1929번 C언어 소수구하기 - 성공

위와 같이 중첩 반복문을 이용해 시간 복잡도를 줄여 제출할 수 있었습니다!