[알고리즘 기초] - 301-수학1(연습)

9613_GCD 합

⭕풀이:

import math

test_case = int(input())

for i in range(test_case):
    numbers = list(map(int, input().split()))
    total = 0
    for j in range(1, len(numbers)):
        for k in range(j+1, len(numbers)):
            sum += math.gcd(numbers[j], numbers[k])

    print(total)

📌필요지식

1) math.gcd(인자)

• gcd의 인자로 숫자들을 입력할 수 있습니다. 즉, 인자는 0개부터 N개까지 올 수 있습니다.
• gcd는 인자로 들어온 숫자들의 최대 공약수(정수)를 반환합니다.
• 인자가 0개인 경우 math.gcd()일 때, 함수의 반환 값은 0입니다.
  모든 인자의 값이 0인 경우에도 math.gcd(0) 혹은 math.gcd(0, 0, 0,..0)인 경우에도 함수의 반환 값은 0입니다.

1-1) math.gcd() 사용법

① import math
② math.gcd(숫자1, 숫자2, 숫자3,..)

---

17087_숨바꼭질 6

⭕풀이:

import math

N, S = map(int, input().split())
n = list(map(int, input().split()))

distanse = []
for i in n:
    distanse.append(abs(S - i))

ans = distanse[0]
for i in range(1, N):
    ans = math.gcd(distanse[i], ans)
print(ans)

📌필요지식

1) abs(number)

• 전달한 숫자 number의 절대값을 돌려줍니다.
• number로 올 수 있는 값은 정수, 실수, 복소수가 될 수 있습니다.
  
  
  

2) 절댓값

• 절댓값은 어떤 값을 양수로 만들어 주기 위한 장치라고 보시면 됩니다.

---

1373_2진수 8진수

⭕풀이:

ten_number = int(input(), 2)  #입력된 값을 2진수 숫자로 인식한다.
print(oct(ten_number)[2:])  #2진수인 ten_number를 10진수로 바꾸고, 앞에서 3번째부터 출력한다.

📌필요지식

1) 2진수, 8진수, 10진수, 16진수

• 파이썬은 10진수를 기본으로 합니다. 때문에 다른 진수들의 수와 차별을 두기 위해 각 진수의 수 앞에 아래 두 글자를 붙여 표현합니다.

  2진수 : 0b
  8진수: 0o
  16진쉬 0x

1-1) bin(number), oct(number), hex(number)

• 10진수에서 2진수, 8지수, 16진수 변환은 파이썬 자체 내장함수를 이용하면 됩니다.

  bin(number): 10진수 ---> 2진수 변환
  oct(number): 10진수 ---> 8진수 변환
  hex(number): 10진수 ---> 16진수 변환

2) int(value, x)

• int(value)에서 value 뒤에 , 를 찍고 뒤에 숫자를 넣으면 value를 그 숫자진법의 숫자로 인식한다는 것입니다.

  int(value + , + 인식하고 싶은 진법의 숫자)

---

1212_8진수 2진수

⭕풀이:

eight_number = int(input(), 8)
print(bin(eight_number)[2:])

---

2089_-2진수

⭕풀이:

import sys

N = int(sys.stdin.readline())
if not N:
    sys.stdout.write('0')
    exit()
res = ''
while N:
    if N % (-2):  #N % -2의 값이 존재하는 경우,(=-2로 나눠 떨어지지 않는 경우,)
        res = '1' + res  
        N = N // -2 + 1  # N // -2를 한 후에 +1을 해준다. 그 이유는 -13 / -2 = 6.5 이기 때문에 -13 // -2 = 6 으로 출력된다. 그래서 몫을 구해주기 위해서는 +1을 해줘 나머지가 양수가 되도록 해야 한다.
    else:  #N % -2의 값이 0인 경우,(=-2로 나눠 떨어지는 경우,)
        res = '0' + res  
        N //= -2

sys.stdout.write(res)

⭕풀이설명:

• 진수계산을 이용하면 다음과 같습니다.

  -13 = -2 7 + 1
  7 = -2 -3 + 1
  -3 = -2 2 + 1
  2 = -2 -1 + 0
  -1 = -2 1 + 1
  1 = -2 0 + 1
  따라서 110111 이라는 주어진 예제 -13에 대한 출력이 정상적으로 나오는 것을 확인할 수 있습니다. 코드의 내용도 이와 같습니다.

📌필요지식

1) sys.stdout.write()

2) break, contitnue, return, exit

2-1) break() = 루프 탈출 / 중단

• for과 while 문법에서 제어 흐름을 벗어나기 위해 사용됩니다.
• 루프 이후에 등장하는 코드를 계속 실행합니다.
• if문은 반복문이 아니라 조건 충족시 1번만 실행되는 코드이므로 해당되지 않습니다.
  

2-2) continue()

• break와 유사합니다.
• 단 제어 흐름은 유지하고, 코드 실행만 건너 뜁니다.
  

2-3) return() = 함수 탈출 or 인클루드 탈출

• 함수 안에서 쓰이면 함수 실행을 종료하고, 그 함수를 호출했던 지점으로 돌아가서 계속 실행합니다.
• 함수 밖에서 쓰이면 상위 파일(현재 파일을 인클루드 했던 파일)로 돌아가서 계속 실행합니다.
• 함수 밖인 데다 인클루드 한 것도 없으면 그냥 종료됩니다. 즉, exit와 동일한 효과입니다.

2-4) exit(), die() = 무조건 종료

• 프로그램이 강제로 종료됩니다.

---

17103_골드바흐 파티션

⭕풀이:

array = [True for i in range(1000001)]  #에라토스테네스의 체 

for i in range(2, 1001):
    if array[i]:
        for j in range(i * i, 1000001, i):
            array[j] = False

test_case = int(input())

for _ in range(test_case):
    n = int(input())
    cnt = 0
    for i in range(2, n // 2 + 1):  #파티션의 중복을 피하기 위해 주어진 값의 절반크기까지만 반복
        if array[i] and array[n - i]:  #소수인 두 수의 합이 주어진 값이면,
            cnt += 1
    print(cnt)

---