백준 Codeplus - 수학 Part(10430번,2609번,9613번,1934번,1978번,6588번- 계속 업로드)

백준에서 제공하는 SW 역량 테스트 기초가 있다. 이것을 풀 예정

https://www.acmicpc.net/workbook/codeplus

code.plus 문제집 - 1 페이지

 

정답을 무작정 찾아보기보단 조금 계속 고민하다가 안 풀리면 과감하게 넘어가도록하자! 

하루에 한 문제가 적당하다고들 한다 ㅎ 

---

< 수학 >

https://www.acmicpc.net/problem/10430

 

10430번: 나머지

 

문제

(A+B)%C는 ((A%C) + (B%C))%C 와 같을까?

(A×B)%C는 ((A%C) × (B%C))%C 와 같을까?

세 수 A, B, C가 주어졌을 때, 위의 네 가지 값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 순서대로 주어진다. (2 ≤ A, B, C ≤ 10000)

출력

첫째 줄에 (A+B)%C, 둘째 줄에 ((A%C) + (B%C))%C, 셋째 줄에 (A×B)%C, 넷째 줄에 ((A%C) × (B%C))%C를 출력한다.

 

A, B, C =  map(int,input().split())

print((A+B)%C, ((A%C)+(B%C))%C, (A*B)%C, ((A%C)*(B%C))%C, sep='\n')

---

👽 해설 👽

• map( ) 함수: https://dojang.io/mod/page/view.php?id=2286 

파이썬 코딩 도장: 22.6 리스트에 map 사용하기

리스트 요소를 지정된 함수로 처리해줌. 

• input( ).split( ) 엔터를 기준으로 값을 입력받는 함수
• sep = '\n'를 사용해서 줄바꿈 실행

---

 

https://www.acmicpc.net/problem/2609

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

문제

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

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

from math import gcd

def lcm(x,y):
    return x*y // gcd(x,y)

a, b = map(int, input().split())

print(gcd(a,b), lcm(a,b),sep='\n')

---

👽 해설 👽

• from math import gcd : 최대공약수를 사용하기 위해서 특정 함수를 사용할 때 사용되는 from import를 사용해서 최대공약수 모듈사용을 불러온다. 

https://driz2le.tistory.com/207

[펌] Python - import 와 from import 차이점

• gcd( ) : 최대 공약수를 구해주는 파이썬 내장함수(정말 파이썬 최고 ㅋ)
• def lcm(x,y) : 최소 공배수를 구해주기 위해서 함수를 만들어줌.

https://brownbears.tistory.com/454

[Python] 최대공약수, 최소공배수, N개의 최소공배수

 

---

https://www.acmicpc.net/problem/1934

1934번: 최소공배수

문제

두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다.

두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000)

출력

첫째 줄부터 T개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다.

예제 입력 1 

3 1 45000 6 10 13 17

예제 출력 1 

45000 30 221

 

<코드>

def gcd(a, b):
    c = 1
    while c != 0:
        c = a % b
        a = b
        b = c

    return a

def lcm(a, b):
    return (a * b) / gcd(a, b)


n = int(input())

for _ in range(n):
    a, b = map(int, input().split(" "))
    
    if a > b:
        print(int(lcm(a, b)))
    
    else:
        print(int(lcm(b, a)))

---

👽 해설 👽

 

• 최대공약수 함수와 최소공배수 함수를 사용
• n개만큼 a,b 값을 입력 받아 a가 b보다 크다면 a, b = a, b b가 a보다 크다면 a, b = b, a를 프린트해준다. 

---

https://www.acmicpc.net/problem/9613

9613번: GCD 합

문제

양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다.

출력

각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다.

예제 입력 1 복사

3 4 10 20 30 40 3 7 5 12 3 125 15 25

예제 출력 1 복사

70 3 35

 

<코드>

n = int(input())


def gcd(a, b) :
    if b==0:
        return a
    else :
        return gcd(b,a%b)


for _ in range(n):
    arr = list(map(int,input().split()))
    k = arr.pop(0)
    sum = 0
    for i in range(k):
        for j in range(k):
            if i<j :
                sum += gcd(arr[i],arr[j])
    print(sum)
    
    
    

---

👽 해설 👽

큰 수를 작은 수로 나누어 구한 나머지로 큰 수를 대체한다. 큰 수를 작은 수로 계속 나누어서, 나누어 떨어질 때까지 반복한다. 나누어 떨어질 때(나머지가 0일 때), 나누는 수가 최대공약수이다. 
👉출처: https://wikidocs.net/21759

• 최대공약수를 사용하기 위해서 함수를 사용했다. def gcd(a,b) 이때 유클리드 호제법을 사용해서 최대공약수 함수를 만들었다. 
• 입력받은 n개의 정수를 이용하여 arr 리스트 변수에 값을 추가 시킨다. list(map(int,input( ).split( ))) 리스트형으로 입력받겠다는 의미.
• arr에 있는 값들을 k.pop(0)를 이용해서 첫번째 요소로 지정하여 마지막까지 뽑아 쓸 수 있도록 k를 준비하여 중첩반복문을 사용하여 최대공약수를 sum 함수에 넣고 마지막에 출력해준다. 출력 역시 최대공약수가 입력받은 n개 만큼 전부 구해질 때마다 출력되어야 하기 for _ in range(n)만큼 돌아야 한다.   

---

https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

문제

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

입력

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

출력

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

예제 입력 1 복사

4 1 3 5 7

예제 출력 1 복사

3

n = int(input())
x = list(map(int,input().split()))
num_count = 0

for i in x : #입력받은 x의 리스트에서 1개씩 꺼내오기
    
    count = 0
    if i == 1 : # x에서 꺼내온 값인 i가 1이라면 다시 처음으로 돌아가서 진행, 1은 소수가 아니다.
        continue
    for j in range(2,i+1): #소수 찾기: 소수는 1과 자기자신만으로 나눠지는 것이 소수이기때문에 count 판별
        if i%j == 0:
            count += 1
    if (count == 1): #count가 1이라면 소수이기 때문에 num_count를 1씩 늘려준다.
        num_count += 1
print(num_count)

👽 해설 👽

- 위의 문제는 간단하게 i를 x에 담긴 값들을 한 개씩 꺼내서 쓸 동안 도는 for 구문이라고 생각하면 편하다

 

- if i == 1 일때 컨티뉴문을 사용하여 다시 for문으로 돌아가 다음 값을 꺼내서 for문을 진행

 

- 소수는 1과 자기 자신으로만 나눠지기 때문에 x에서 꺼내온 값 i를 j로 나눴을 때 나머지가 0이라면 소수라고 판단되어 count 변수에 값을 1개를 추가해주고 반복문이 끝났을 때 count값이 1이라면 소수인 것을 판단한 것이기 때문에 전체적으로 x값에 소수가 몇개인지를 판단하면 num_count 값에 값을 추가해준다. 이때 count 변수는 지역변수로 for문이 끝나면 사라지게 된다. 그러나 num_count는 전역 변수로 계속해서 값을 유지한다. 

---

https://www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다.

4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.

예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다.

이 추측은 아직도 해결되지 않은 문제이다.

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

입력

입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다.

각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ≤ 1000000)

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력한다. 또, 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong."을 출력한다.

예제 입력 1 복사

8 20 42 0

예제 출력 1 복사

8 = 3 + 5 20 = 3 + 17 42 = 5 + 37

import sys
#골드바흐 추측
def goldbach(n,p):
  m = n//2+1
  for i in range(3,m,2):
    if p[i] == True and p[n-i] == True:#n, n-p가 모두 소수이면
      print(n,'=',i,'+',n-i)
      return
  print("Goldbach\'s conjecture is wrong.")

#에라토스테네스의 체
p = [True]*1000001
for i in range(3,1001,2):
  if p[i] == True:
    for j in range(i**2,1000001,i):
      p[j] = False

#입력
while True:
  n = int(sys.stdin.readline())
  if n == 0:
    break
  else:
    goldbach(n,p)

👽 해설 👽

- 시간초과 문제를 해결하기 위해서는 최적화가 필수인 문제.

- import sys의 사용은 반복문 안에서 시간초과 문제가 일어날 수 있어서 불러오는 것