크래프톤 정글 week01, day07 - 알고리즘 문제 풀기

소수

• 1보다 큰 자연수 중 1과 자신만을 약수로 가지는 수
  • ex) 11은 1x11로만 성립되기 때문에 소수

​

• 에라토스테네스의 체
  • 임의의 자연수 n에 대해 그 이하의 소수를 찾는 가장 효율적으로 소수를 찾는 방법이다.
  • 순서(100 이전의 소수를 모두 찾기)
    • 1을 먼저 제거
    • 2를 제외한 2의 배수 모두 제거
    • 3을 제외한 3의 배수 모두 제거
    • 5를 제외한 5의 배수 모두 제거
    • 7을 제외한 7의 배수 모두 제거
    • ... 등 제거하고 남은 제일 낮은 수의 배수를 모두 제거하면 소수만 남는다.
  • 일정 범위 내에서 구하기는 이 방법이 좋지만 특정 값이 소수인지 판별하는건 다른 알고리즘이 더 빠르다.

 

주어진 N개 중에 소수가 몇 개인지 찾기

• 주어진 N개의 소수를 받아 그 안에 소수가 몇 개인지 찾아야 한다.

import math

# 몇 개 받을 지 입력받기
cnt = int(input())
arr = []

nums = list(map(int, input().split()))

# 받은 값만큼 반복문 돌리기
for i in range(len(nums)):
# 값이 1이면 넘기고 아니면 for문 진입
    if nums[i] == 1:
        continue
    else:
# 2부터 입력값의 제곱근+1값 까지 반복하며 값이 j값에 맞아 떨어지면 넘기고 아니면 배열에 추가
        for j in range(2, int(math.sqrt(nums[i])) + 1):
            if nums[i] % j == 0:
                break
        else:
            arr.append(nums[i])

print(len(arr))

 

처음에 소수의 알고리즘 파악이 어려워서 좀 헤맸었다. 그래서 1부터 입력값까지 하나씩 다 비교해서 할려고 했었는데 입력값이 커지면 커질수록 시간이 너무 오래걸릴거 같아 검색하던 중 제곱근을 이용한 방법을 접했다.

​

• 입력값이 제곱근 이상의 수로 나누어 떨어지면 그 값은 반드시 제곱근 이하가 된다.
  • 예시) 81**(1/2) = 9 일때 81은 9의 제곱근이고 2부터 9까지 81을 나누면 3에서 나누어 떨어진다. 이 말은 이미 3에서 나누어 떨어졌기 때문에 81은 소수가 아니라고 단정할 수 있다.
• ​"에라토스텔레스의 체" 알고리즘은 뭔지는 알았는데 코드를 이해를 잘 못하여 나중에 소수 값을 찾는 알고리즘에 사용해보려고 한다.

 

골드바흐의 추측

• 유명한 정수론의 미해결 문제이며 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다
• ex) 8 = 3+5, 18 = 11 + 7, 24 = 13 + 11 등등
• N개의 입력값을 받아 그 값이 골드바흐의 추측을 증명할 수 있는지 찾아야한다.

# 몇번 반복할건지 입력 받기
cnt = int(input())
# 입력받은 횟수만큼 반복
for i in range(cnt):
    num = int(input())
    # find라는 배열에 0, 1은 false로 저장하고 뒤에 입력받는 값-1 만큼 True 넣기
    # (0, 1)은 소수가 아니기 때문에 false로 하고 2부터 일단 true로 해놓고 나중에 변경
    find = [False, False] + [True]*(num-1)

    # 2부터 num값의 제곱근을 계산해 +1 붙여주기.
    # int로 변환하면 소숫점을 버리기 때문에 1을 붙여 값이 더 높음을 인지
    for j in range(2, int(num ** (1/2)) + 1):
        # 만약 find 배열의 j번쨰가 true일 때
        if find[j]:
            # j가 2이면 2의 2배수부터 입력값미만이라 +1까지 2씩 증가하며 반복
            for k in range(j*2, num+1, j):
                # 배수씩 뛰는거라 2이면 4, 6, 8... 등이 false로 바뀜
                find[k] = False
    # 변수 두개에 입력값의 반절씩 넣기
    # 가운데서 좌우로 이동하며 값을 찾기 위함
    left = right = num // 2

    # 왼쪽으로 갈 값이 0보다 클 때
    while left > 0:
        # 만약 find의 [left], [right]가 true이면 left, right를 출력하고 빠져나오기
        if find[left] and find[right]:
            print(left, right)
            break
        # false라면 left는 1 빼고 right는 1 더하고 left가 0이 될떄까지 무한 반복
        else:
            left -= 1
            right += 1

이건 내 머리론 도저히 알고리즘이 안풀려서 지피티의 힘을 좀 빌렸다. 소수찾기처럼 제곱근을 이용해서 소수를 찾는 코드는 작성했으나 배열에 True, False를 이용해 소수가 뭔지 입력하는 방식은 전혀 생각을 못했던 터라 엄청 독특했다 소수를 구한 이후 최적의 합을 찾기 위해 값의 가운데에서 좌우로 이동하며 소수를 찾았다.

​

계속 못 풀면서 시간 지나갈 때 빨리 해답 확인해서 학습했어야 했는데 계속 풀어볼려고 붙잡고 있다가 몇개 못 풀고 하루를 써버렸다. 그래도 막힌 곳 하나는 뚫었으니 다음 문제도 열심히 풀려고 한다.

​

학습시간 : 14 ~ 26시