Skip to content

Latest commit

 

History

History
723 lines (397 loc) · 12 KB

_백준_강의_기초(1)_수학.md

File metadata and controls

723 lines (397 loc) · 12 KB

4375번: 1

2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.

## 4375번: 1
#### 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.


# 값 입력받기 (try-except 구문)
while True:
    try:
        n = int(input())

    except:
        break

    result = 0 # 나머지 연산의 결과

    i = 1 # 한자릿수(1로만 이루어진 n의 배수) 부터 시작
    while True:
        result = result*10 + 1
        result %= n

        if result == 0:
            print(i)
            break # while 문 빠져나오기

        i += 1
3
3
7
6
9901
12

def recursive(N, result): # 재귀함수로 짜본 코드 -> 살짝 돌아가다가 "런타임 에러 (RecursionError)" 뜸
    if (result % N) == 0:
        return len(str(result))

    return recursive(N, (result*10 + 1))


while True:
    try:
        n = int(input())

    except:
        break


    print(recursive(n, 1%n))
    
3
3
7
6
9901
12

7
7

c = int(input())

l = input().split()

small = l[:c//2]
large = l[c//2:]

print(map(int, l))
2
2 4
<map object at 0x7ffb06ab0390>

c = int(input())

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

small = l[:c//2]
large = l[c//2:]

print(small[0]*large[-1])
2
2 4



---------------------------------------------------------------------------

TypeError                                 Traceback (most recent call last)

<ipython-input-31-cb2bf6ac180e> in <module>()
      1 c = int(input())
      2 
----> 3 l = list(map(int, input().split()))
      4 
      5 small = l[:c//2]


TypeError: 'map' object is not callable

1037번: 약수

어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오.

## 1037번: 약수
#### 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오.

c = int(input())

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

print(min(l) * max(l))

17427번: 약수의 합 2

자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다. 자연수 N이 주어졌을 때, g(N)을 구해보자.

## 17427번: 약수의 합 2
#### 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다. 자연수 N이 주어졌을 때, g(N)을 구해보자.


# 시간 복잡도 : O(N)
n = int(input())

g_x = 0 # 모든 자연수의 약수의 합

for i in range(1, n+1): # O(N)
    g_x += n * (n//i) # O(1)
    
print(g_x)

17425번: 약수의 합

자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다. 자연수 N이 주어졌을 때, g(N)을 구해보자.

## 17425번: 약수의 합
#### 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다. 자연수 N이 주어졌을 때, g(N)을 구해보자.



# 시간 복잡도: O(NlogN) + O(T)


# 1) d[]와 s[] 만들기
MAX = 1000000
d = [1] * (MAX+1) # f_x
s = [0] * (MAX+1) # g_x

for i in range(2, MAX+1): # '배수' 원리를 이용
    j = 1 # 인덱스
    while i*j <= MAX:
        d[i*j] += i
        j += 1 # 인덱스
        
for i in range(1, MAX+1):
    s[i] = s[i-1] +d[i]
    
    
# 2) Testcase에 맞게 출력
T = int(input())
ans = [] # 시간 초과 방지를 위한 답 출력 방식

for _ in range(T):
    n = int(input())
    ans.append(s[n])
    
#print('\n'.join(map(str, ans))+'\n')
print('\n'.join(map(str, ans))) # '\n' 로 이어 붙이기
MAX = 10
d = [1] * (MAX+1) # f_x
s = [0] * (MAX+1) # g_x

for i in range(2, MAX+1): # '배수' 원리를 이용
    j = 1 # 인덱스
    while i*j <= MAX:
        d[i*j] += i
        j += 1 # 인덱스
        
for i in range(1, MAX+1):
    s[i] = s[i-1] +d[i]
print(d)
print(s)
[1, 1, 3, 4, 7, 6, 12, 8, 15, 13, 18]
[0, 1, 4, 8, 15, 21, 33, 41, 56, 69, 87]

ans = [1,
4,
87,
4065,
82256014]
print('\n'.join(map(str, ans)))
1
4
87
4065
82256014

## 재귀함수로 유클리드 호제법 구현해보기 (파이썬 버젼)
#### GCD(a, b) = GCD(b, r) (* r = a % b)

def recursive(a, b):
      if b == 0:
        return a

      return recursive(b, a%b)



recursive(24, 16)
8

2609번: 최대공약수와 최소공배수

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

## 2609번: 최대공약수와 최소공배수
#### 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.


def recursive(a, b): # GCD(최대공약수) 찾는 재귀함수
    if b == 0:
        return a

    return recursive(b, a%b)


# 문제 입력 및 출력
a, b = map(int, input().split())

print(recursive(a, b))
print(a * b // recursive(a, b)) # LCM(최소공배수)는 GCD * (a/GCD) * (b/GCD) 임을 이용
#### (주의) 파이썬 나눗셈 / 아니고 //
## 유형 1 - 소수 찾기 판별법 중 시간복잡도 O(루트 N) 구현해보기
#### (2 ~ 루트 N) 중 약수가 없음을 확인


import math


def prime(n):
    if n < 2: # (예외 처리) 1은
        return False # 소수가 아님

    for i in range(2, int(round(math.pow(n, 0.5), -1))):
        if (n % i) == 0: # 중간에 약수가 존재한다면
            return False # 소수가 아님


    else: # 무사히 다 돌았다면
        return True # 소수가 맞음
prime(100)
False

prime(7)
True

prime(2)
True

prime(17)
True

n = 100


int(round(math.pow(n, 0.5), -1))
10

1978번: 소수 찾기

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

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


def is_prime(n):
    if n < 2: # (예외 처리) 1은
        return False # 소수가 아님

  i = 2
    while i*i <= n: # 파이썬 for문 대신 while문으로 표현 가능 (2 ~ 루트N 까지 약수인지 확인)
        if (n % i) == 0: # 중간에 약수가 존재한다면
            return False # 소수가 아님
    
    i += 1

  #else: # 무사히 다 돌았다면
  return True # 소수가 맞음


# 문제 입력 & 출력
num_count = int(input())
num_list = list(map(int, input().split()))
ans = 0

for num in num_list:
    if is_prime(num):
        ans += 1

print(ans)
## 유형 2 - 범위 내 소수 모두 찾기

MAX = 1000000
check = [False] * (1000000+1)
check[0] = check[1] = True # (예외 처리) -> 소수가 아님 -> 지움 처리

i = 1
while i*i <= MAX:
    i += 1

    if check[i] == False:
        j = i+i # j는 i의 배수
        while j <= MAX:
            check[j] = True # 지움 처리
            j += i # 다음 배수
    
check[2]
False

check[3]
False

check[4]
True

check[17]
False

1929번: 소수 구하기

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

## 1929번: 소수 구하기
#### M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

# 내가 풀은 정답 (*(2 ~ 루트 N) - while문 이용)
MAX = 1000000
check = [False] * (1000000+1)
check[0] = check[1] = True # (예외 처리) -> 소수가 아님 -> 지움 처리

i = 1
while i*i <= MAX:
    i += 1 # (2 ~ 루트 N) 동안 체크

    if check[i] == False:
        j = i+i # j는 i의 배수
        while j <= MAX:
            check[j] = True # 지움 처리
            j += i # 다음 배수
            
            
# 문제 입력 & 출력
m, n = map(int, input().split())

for i in range(m, n+1):
    if check[i] == False: # 소수라서 지워지지 않았다면
        print(i)
# 선생님 정답 (*(2 ~ 루트 N) - for문 이용 & check 배열 초기화 시 False 대신 숫자 0 사용)
MAX = 1000000
check = [0] * (1000000+1)
check[0] = check[1] = True # (예외 처리) -> 소수가 아님 -> 지움 처리


for i in range(2, MAX+1): # (2 ~ 루트 N) 동안 체크
    if not check[i]:  # False
        j = i+i # j는 i의 배수
        while j <= MAX:
            check[j] = True # 지움 처리
            j += i # 다음 배수
            
            
# 문제 입력 & 출력
m, n = map(int, input().split())

for i in range(m, n+1):
    if check[i] == False: # 소수라서 지워지지 않았다면
        print(i)
3 16
3
5
7
11
13

# 선생님 정답 (*(2 ~ 루트 N) - for문 이용)
MAX = 1000000
check = [0] * (1000000+1)
check[0] = check[1] = True # (예외 처리) -> 소수가 아님 -> 지움 처리


for i in range(2, MAX+1): # (2 ~ 루트 N) 동안 체크
    if not check[i]:  # False
        j = i+i # j는 i의 배수
        while j <= MAX:
            check[j] = True # 지움 처리
            j += i # 다음 배수
check[2]
0

check[3]
0

check[4]
True

에라토스테네스의 체

  • 에라토스테네스의 체를 사용한 경우,

어떤 수 N이 소수인지 아닌지 판별하기 위해 루트 N 방법을 사용할 필요가 없다.

  • 에라토스테네스의 체의 결과에서 지워지지 않았으면 소수, 아니면 소수가 아니기 때문이다.

False로 인식되는 경우

  • None

  • 숫자 0

  • 숫자 0.0...0

  • 빈 컨테이너 (ex. 빈문자열, 빈 바이트열, 빈 리스트, 빈 튜필, 빈 딕셔너리 등)

위의 상황을 제외하면 모두 True로 인식됩니다.

bool(0)
False

bool()
False

bool(1) # True ..
True

bool(0.0)
False

6588번: 골드바흐의 추측

백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.

## 6588번: 골드바흐의 추측
#### 백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.


MAX = 1000000
check = [0] * (1000000+1)
check[0] = check[1] = True


prime = [] # 소수만 담을 리스트 배열

for i in range(2, MAX+1):
    if not check[i]: # False라면 = 아직 지워지지 않은 가장 작은 소수라면
        prime.append(i)
        j = i+i # i의 배수
        while j <= MAX:
            check[j] = True # 1.배수 지우고
            j += i # 2.다음 배수로 넘어가기
            
prime = prime[1:] # 2는 짝수 소수이므로, 3부터 시작


# 문제 입력 & 출력
while True:
    n = int(input())
    if n == 0: # 입력의 마지막 줄에는 0이 주어진다. (즉, 종료 flag)
        break
        
    for p in prime: # A + B = N
        if check[n-p] == False: # 소수인지 체크
            print("{0} = {1} + {2}".format(n, p, n-p)) # N = A + B
            break # 다음 입력을 받기 위한 for문 빠져나오기

골드바흐의 추측

  • 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다.

(응용: 3을 더하면, *5보다 큰 모든 홀수는 세 소수의 합으로 표현가능하다.)

  • 아직 증명되지 않은 문제이나, 10^18 이하에서는 참인 것이 증명되어 있다.