[백준 1978번] 소수 찾기

1978번: 소수 찾기

---

문제 상황

N개의 자연수가 주어지며,

모든 소수의 갯수를 찾아 출력하는 문제이다.

 

즉, 모든 수를 살펴보고

소수인지 아닌지를 판별해내야 하는 것이 이번 문제의 핵심이다.

---

솔루션

소수의 "수학적 정의"인

1을 제외한 약수가 존재하지 않는 수를 통해 솔루션을 마련했다.

 

따라서, 주어진 수를 숫자 1을 제외하며 주어진 수보다 작은 수들로 나누었을 때

모두 나누어 떨어지지 않는다면 소수로 판별하는 전략으로

모든 수들을 검사해 모든 소수의 갯수를 찾아냈다.

 

솔루션 코드 작성 (with Python)

아래는 다음 솔루션을 적용해 파이썬으로 작성한 코드이다.

# 백준 1978 소수찾기

answer_num = 0  # 소수 갯수 변수초기화
n = int(input(""))  # 조사할 수 갯수입력

# 조사할 수들 입력
n_list = list(map(int, input().split()))

# 소수 조사시작
for i in range(0, n):
  # 해당 수의 소수 조건검사
  if (n_list[i] != 1 and n_list[i] != 2 and n_list[i] != 3):
    for z in range(2, n_list[i]):
      if (n_list[i] % z == 0):
        break
      elif (z == n_list[i] - 1):
        answer_num += 1

  elif (n_list[i] == 2 or n_list[i] == 3):
    answer_num += 1

print(answer_num)

---

마치며

비하인드 스토리

이번 문제는 2023년 4월 24일에 군 입대를 하고,

군대와서 처음으로 사지방에서 백준을 해결한 문제이다.

오랜만에 코딩을 했던 터라, 꽤나 시간이 오래걸려서 풀었다.

문제를 풀 땐 솔루션을 생각하고 파이썬 코드로 작성하면서 파이썬 문법에 대한 구글을

되게 많이했다. 파이썬 문법이 가물가물해서 그랬었다 ㅎㅎ..

(인간은 망각의 동물인 듯 하다..ㅎㅎ)

 

사실 이 문제를 한번에 해결한 건 아니다.

그렇게 구글링을 통해 첫 솔루션에 대한 파이썬 코드를 열심히 작성했지만.. 결과는 실패였다.

백준 컴파일러에 테스트를 돌려봤지만, 문법오류도 아닌데 "실패"가 계속 떴다.

정말 그때 당시엔 이해가 안되었다. 분명히 내가 생각한 조건으로 코드를 작성했고,

콘솔에서 테스팅을 모두 해보았는데 오류가 없었다 라고 생각했다.

하지만, 나는 잘못 접근하고 있었다는 걸 'Chat GPT'를 통해 깨달았다.

 

 

 

chat GPT로 내가 작성한 파이썬 코드를 

아주.. 쉽게 디버깅해서 잘못 접근한 부분을 알려주었다.

 

(잘못된.. 첫 솔루션)

나의 솔루션은 모든 수들을 나열하고, 소수를 관찰하여

소수만의 '규칙'을 정의했다. 그에 따라 소수는

홀수인 수들 중 숫자 3으로 나누어 떨어지지 않는 수 이거나, 숫자 2,3을 소수라고 정의했다.

이때 종이에 펜으로 특정 수들을 나열해 소수의 규칙을 찾았기에

나는 모든 수들에 대한 규칙이 아닌, 특정 수들만의 소수 규칙을 정의하는 실수를 하게되었다.

정리해서, 잘못된 솔루션을 제안한 이유는

특정한 범위에서만 소수의 규칙을 정의해냈기에, 모든 소수들을 판별하지 못해내는 "솔루션"을 제안했다.

 

그러면, 모든 소수를 판별하는 "솔루션"은 어떻게 제안할 수 있을까?

소수의 '수학적 정의'를 살펴보고 솔루션을 마련하면 된다.

이전 솔루션을 제안했을 당시에는 특정 구간에 속한 수들에 대해서만 규칙을 찾아

모든 수들의 규칙이 아닌 페쇄적인 솔루션을 제공했다.

정답 솔루션은 소수의 '수학적 정의'인 1을 제외한 약수가 존재하지 않는 수를 토대로

주어진 수가 1을 제외한 모든 수(주어진 수보다 작은 수)로 나누었을 때 나누어 떨어지지 않는다면 소수로 판별해내어

모든 소수를 찾을 수 있도록 했다.

정리해서, 이번 문제는 "소수"라는 수학적 정의가 마련되어 있는 상황 속에선 '기본정의'를 토대로 솔루션을 제시해

모든 구간에 대한 포괄적인 솔루션을 제시해야 된다는 것이 핵심이다.

 

깨달음

이번 문제를 통해 얻은 깨달음은 어떤 상황에서

'기본정의'가 드러난 것을 토대로 솔루션을 마련하고자 할 땐, 추론하여 접근 후 페쇄적인 솔루션을 마련하는 것이 아닌

어떤 상황에서 드러난 '기본정의' 를 토대로 솔루션을 마련하는 것이 포괄적인 솔루션을 제시할 수 있는

지름길이라는 점을 깨달았다.

정리해서, 솔루션이란 모든 상황에서 적용되어야 된다는 점을 이해하고,

마련하려는 태도를 지녀야한다.