JinWoo Kim

백문이 불여일견, 백견이 불여일행.

2 minute read

1. 소수 찾기

  • 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력

  • 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력

  • 주어진 수들 중 소수의 개수를 출력한다.

풀이

import sys

N = int(sys.stdin.readline())

nums = list(map(int,sys.stdin.readline().split()))

cnt = 0
cache = []
for n in nums:
    i = 2
    if n == 1:
        continue
    elif n == 2:
        cnt += 1
    else:
        while i < n:
            if n % i == 0:
                break
            elif n % i != 0 and i == n-1:
                cnt += 1
            i += 1

print(cnt)

채점 결과

  • 정답

리뷰

  • 각 숫자가 1000이하의 자연수이고, 배열의 최대 크기는 100 이하라는 조건이 붙어있으므로 단순 무식한 소수 구하기를 통해 문제를 해결할수 있었다.

  • 만약 제시된 예시중에 크기 100의 배열에 900~1000의 수를 넣어놓는 식으로 최악의 시간복잡도를 제시할 경우, 실패가 날 확률이 대단히 높은 방법이다.

  • 이에 대해서는 2번 문제에서 다룰 방식으로 푸는것이 정답이 될수있다.

2. 소수 구하기

  • M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

  • 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

  • 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

풀이

import sys

M, N = list(map(int, sys.stdin.readline().split()))

a = [False,False] +[True] * (N-1)
primes = []

for i in range(2,N+1):
    if a[i]:
        primes.append(i)
        for j in range(2 * i, N+1,i):
            a[j] = False

for x in primes:
    if x >= M:
        print(x)

채점 결과

  • 정답

리뷰

  • 에라토스테네스의 체를 구현하여 푸는 방식이다.

  • a는 0~N까지의 수가 소수인지 체크하기 위한 배열이다.
    • 첫 두 인덱스의 False는 0,1이 소수가 아님을 의미한다.

  • 2~(N+1)의 인덱스를 순회하며, 각 인덱스에 True값이 들어가 있는 경우(체크되지 않은 소수인 경우) primes에 추가한다.

  • 그 후 2*i부터 N+1 까지의 i의 배수에 대해 a값을 False로 변경하여 i의 배수가 인덱스로 나오더라도 조건에 걸리지 않도록 변경한다.(에라토스테네스의 체)

  • 마지막으로, primes에서 M이상의 값만 출력하도록 하면 끝.

3. 분해합

  • 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다.
  • 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다.
    • 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다.
    • 따라서 245는 256의 생성자가 된다.

  • 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.

  • 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.

입력

  • 첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

  • 첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.

풀이

# your code goes here
 
import sys
import math
 
N = int(sys.stdin.readline())
 
# 분해합 = N + N의 각 자리수
d_sum = N + sum([int(x) for x in str(N)])
 
 
N1 = math.ceil(N / 2)
N2 = int(N / 2)
 
arr = []
 
while(N2 > 0):
	if N2 == sum([int(x) for x in str(N1)]):
		arr.append((N1,N2))
 
	N1 += 1
	N2 -= 1
 
print(min(arr)[0] if len(arr) > 0 else 0)

채점 결과

  • 정답

리뷰

  • 처음으로 풀어본 브루트 포스 문제였다.(물론,알고 푼건 아니었다.)

  • 직관적으로 생각했을때 두 수의 합으로 이루어진 쌍 중에서 한 수가 다른 한수의 자릿수 합이 되는 경우를 고르면 될거같다고 판단했다.

  • 주어진 N을 반으로 나누어 N1, N2로 주고, N이 홀수일 경우를 대비해 N1에는 math.ceil을 통해 올림, N2는 나머지 버림을 취했다.

  • 조건에 맞는 수가 나올때까지 반복문을 돌리는 식으로 돌렸다.

    • 풀어놓고 이게 맞나 싶어서 입력 제한조건인 1,000,000을 넣어 돌려보니 딱 1초의 실행시간이 나온걸 통해 확신할수 있었다.

You May Also Enjoy