2/11기록 - 백준 2581

오늘의 문제는 백준 2581번 소수 문제이다. 소수 문제는 기본적인 알고리즘을 에라토스테네스의 체 라는 수학적 알고리즘을 가지고 있는 것을 전공자라면 학교 과제를 통해서 알고 있는 사람들이 많을 것 같다. 각설하고 문제로 들어가 보자.

 

 

문제는 간단하다. M과 N 사이의 소수의 합과 최솟값을 출력하면 되는 문제이다.

 

알고리즘 생각

1. 소수는 에라토스테네스의 체로 구하면 되는데, 이 때 M과 N 사이의 값이므로 for문을 한 번 더 걸어주어야 함

2. 소수 prime 변수가 true일 때(소수 일 때) sum 변수에 반복문안에서 합을 구해준다.

3. List 안에 구해진 소수를 담아주고 min 변수에 list의 제일 처음 값을 담아준다. 그게 최솟값이다.

4. 만약 소수가 없을 때(합이 0이거나 최솟값이 10000일 경우) -1 출력, 소수가 있다면 합과 최솟값 출력

 

 

이렇게 해결할 수 있었다. 소수 문제에서 체에 걸러서 하나씩 뺀다는 느낌의 알고리즘으로 에라토스테네스의 체 알고리즘은 아주 유명하다. 에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)를 참고하면 더 자세한 알고리즘을 알 수 있을 것이다.

 

이 문제에서 가장 주의할 점은 for문을 습관적으로 끝점을 < 이렇게만 할 수 있다는 것이다. 마지막까지 값이 들어가야 하는 것이므로 <=로 해 주지 않으면 틀린 값이 나오게 된다.

 

Math.sqrt(i)를 쓴 이유는 루트 형태로 표현하여 제곱수를 모두 커버할 수 있다. 제곱수를 그냥 j<i로 해서 모두 점검해도 출력값은 동일하지만 1000개의 수만 하더라도 31까지 수로 모두 커버할 수 있는데 제곱수를 모두 점검하는 것은 너무나 비효율적인 알고리즘이 된다. 때문에 Math.sqrt()를 사용하는 점을 기억해 두자!!!

 

최솟값을 구하는 방식에서 나는 리스트의 가장 첫 인덱스를 뽑아주는 것으로 맨 처음 생각했다. 하지만 초깃값을 최댓값으로 넣어주고, min>i 일때 min이 최댓값이 되니 min에 작은 값 i를 대입해 주는 방식으로도 최솟값을 구할 수 있다. List에 넣었다 뺐다를 반복하는 방식 보다 메모리 소모가 더 적은 방식이라 이 문제에서는 이 방식이 더 좋은 방식일 수 있다.

 

2/11 기록 끝!!!!!!!!