greentea31's Note

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

풀이 과정

1. 파이썬 내장 함수로 문자열 입력을 8진수로 변환한 뒤, 다시 2진수로 바꿔주는 방법

2. 8진수를 케이스 분류해서 2진수로 바꿔주는 방법

소스 코드

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

a = input()
b = []
for i in a:
    if i == '7':
        b.append('111')
    elif i == '6':
        b.append('110')
    elif i == '5':
        b.append('101')
    elif i == '4':
        b.append('100')
    elif i == '3':
        b.append('011')
    elif i == '2':
        b.append('010')
    elif i == '1':
        b.append('001')
    elif i == '0':
        b.append('000')

answer = list(''.join(b))
while answer and answer[0] == '0':
    answer.pop(0)
if answer:
    print(''.join(answer))
else:
    print(0)

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

풀이 과정

파이썬에는 진법을 편리하게 다루기 위한 내장 함수가 마련되어있다.

int(string, base) => string 문자열을 base진법의 정수로 바꾸어줌

이를 통해 문제를 해결할 수 있다

소스 코드

N = int(input(), 2)
print(oct(N)[2:])

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

풀이 과정

동생이 있는곳을 지나치지 않고 방문하려면 움직이는 칸수가 동생과의 거리의 약수여야 한다

=> 모든 동생을 찾기 위한 공통적인 약수의 최대값을 구해야 한다

=> 동생과의 거리의 최대공약수를 구해달라는 말이다

GCD(a, b, c) = GCD(GCD(a, b), c)가 성립한다. 3개 이상의 수의 최대공약수를 구할때는 앞에서부터 2개씩 묶어서 구해주면 된다

소스 코드

import sys


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


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

for i in range(N):
    A[i] = abs(S - A[i])
answer = A[0]
for i in range(1, N):
    answer = gcd(answer, A[i])

print(answer)

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

풀이 과정

문제에서 시킨대로 주어진 입력의 모든 쌍을 구해 각 쌍의 GCD를 더해주면 된다

10, 20, 30, 40이 입력으로 들어왔다면 (10, 20), (10, 30), (10, 40), (20, 30), (20, 40), (30, 40)이 입력의 모든 쌍일 것이고 각 쌍의 GCD는 10, 10, 10, 10, 20, 10일테니 답은 70이 나올 것이다.

소스 코드

import sys


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


t = int(sys.stdin.readline())
for _ in range(t):
    n = list(map(int, sys.stdin.readline().split()))
    sumNumber = 0
    for i in range(1, n[0] + 1):
        for j in range(i+1, n[0] + 1):
            sumNumber += gcd(n[i], n[j])
    print(sumNumber)

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

풀이 과정

N!에서는 2가 인수로 들어가는 횟수보다 5가 인수로 들어가는 횟수가 항상 더 적었는데 조합에서는 그렇지 않다.

7C3의 경우 2가 인수로 들어가는 횟수는 0번이고 5가 인수로 들어가는 횟수가 1번임을 알 수 있다.

따라서 이번에는 nCk에서 2가 인수로 들어가는 횟수, 5가 인수로 들어가는 횟수를 일일이 세주어야 한다.

이므로 number_count(n, k)라는 함수가 n!에서 a가 인수로 몇번 들어가는지 결과값을 반환해준다고 하면

number_count(n, a) - number_count(n-k, a) - number_count(k, a)가 성립한다

n!에서 a가 인수로 몇번 들어가는지 결과값을 반환하는 함수를 파이썬 코드로 짜면

def number_count(n, k):
    count = 0
    while n != 0:
        n = n // k
        count += n
    return count

이므로 이를 활용해서 문제를 해결할 수 있다

소스 코드

def number_count(n, k):
    count = 0
    while n != 0:
        n = n // k
        count += n
    return count


n, m = map(int, input().split())
count2 = number_count(n, 2) - number_count(n-m, 2) - number_count(m, 2)
count5 = number_count(n, 5) - number_count(n-m, 5) - number_count(m, 5)

print(min(count2, count5))

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

풀이 과정

최대 500!까지 들어올 수 있는데 500!을 실제로 구하고 10으로 나눠보면서 뒤에 0이 몇번 나오는지 세기에는 500!이 너무 크다. 다른 방법을 생각해보자

N!에서 처음 0이 아닌 숫자가 나올때 까지의 0의 개수

=> N!이 10으로 나누어 떨어지는 횟수

=> N!을 소인수분해하고 나온 2의 개수를 a, 5의 개수를 b라 하면 => min(a, b) = N!이 10으로 나누어 떨어지는 횟수이다

그런데 N! = N * (N-1) * (N-2) * ... * 1고 우변에서 5가 인수로 들어가는 횟수가 2가 인수로 들어가는 횟수보다 항상 적다.

따라서 우변에서 5가 인수로 몇번 들어가는지 세주면 된다.

소스 코드

def factorial_count(n):
    count5 = 0
    while n >= 1:
        if n % 125 == 0: count5 += 3
        elif n % 25 == 0: count5 += 2
        elif n % 5 == 0: count5 += 1
        n -= 1
    return count5


N = int(input())
print(factorial_count(N))

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

풀이 과정

1. python의 math 모듈 내의 factorial 함수 사용하기

import math

N = int(input())
print(math.factorial(N))

2. 팩토리얼의 정의에 따라 재귀 함수 구현하기

def factorial(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n - 1)


N = int(input())
print(factorial(N))

소스 코드

풀이 과정 참조

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

풀이 과정

100만 이하의 모든 짝수 입력에 대해 두 홀수 소수의 합으로 나타낼 수 있는지 확인하면 된다.

100만 이하의 모든 소수를 에라토스테네스의 체로 구해서 배열에 넣어주고, 입력 받은 수 - 소수배열[i] (1 <= i < 소수배열 길이) 값이 소수면 두 홀수 소수의 합으로 나타낼 수 있는 것이니 출력해주면 된다.

코드

import sys

prime = []
primeCheck = [0] * 1000001

for i in range(2, 1000001):
    if primeCheck[i] == 0:
        prime.append(i)
        for j in range(2*i, 1000001, i):
            primeCheck[j] = 1

while True:
    n = int(sys.stdin.readline())
    if n == 0: break
    for i in range(1, len(prime)):
        if primeCheck[n - prime[i]] == 0:
            print(f'{n} = {prime[i]} + {n - prime[i]}')
            break

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

풀이 과정

소수 찾기 문제처럼 각각의 수에 대해 소수 판정을 하면 시간 초과가 난다. 소수를 판정하는 알고리즘의 시간 복잡도는 O(rootN)인데 1이상 100만 이하의 소수를 구하라는 입력이 들어올 수 있다.

100만 * root 100만 = 대략 10억번 가량의 연산이 필요하고 시간 제한 2초내로 해결할 수 없다.

특정 범우의 모든 소수를 구할 때는 에라토스테네스의 체라는 알고리즘을 활용해야 한다. 알고리즘은 다음과 같다.

1. 2부터 N까지 모든 수를 적어놓고

2. 남아있는 수중 가장 작은수를 검색하고

3. 그 수를 소수라고 한다음에

4. 그 수의 배수는 모두 소수가 아니니 지워 없앤다

int prime[100]; // 소수를 저장하는 배열
int pn = 0; // 소수의 개수
bool check[101]; // 지워졌으면 true로 체크한다
int n = 100; // n 까지의 소수를 구하겠다

for (int i = 2; i <= n; i++) {
	if (check[i] == false) {
    	prime[pn++] = i;
        for (int j = 2*i; j <= n; j += i) {
        	check[j] = true;
        }
    }
}

prime = []
check = [0] * 101
n = int(input())
for i in range(2, n+1):
    if check[i] == 0:
        prime.append(i)
        for j in range(2*i, n+1, i):
            check[j] = 1

c++와 파이썬으로 구현한 에라토스테네스의 체 알고리즘이다. 에라토스테네스의 체로 2부터 N까지의 모든 소수를 구하는 시간복잡도는 O(NloglogN)으로 알려져 있으므로 시간 제한내에 문제를 해결할 수 있다.

코드

prime = []
primeCheck = [0] * 1000001

M, N = map(int, input().split())

for i in range(2, N+1):
    if primeCheck[i] == 0:
        prime.append(i)
        for j in range(2*i, N+1, i):
            primeCheck[j] = 1

for i in prime:
    if i >= M: print(i)

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

풀이 과정

어떤 수 N이 소수임을 판정하려면 2부터 N-1까지 나누면서 나누어 떨어지는지 확인하면 된다.

=> 2부터 N/2까지만 나누어도 된다. N = a * b (2 <= a <= b <= N-1)에서 b는 N/2를 넘을 수 없다.

=> 2부터 rootN까지만 나누어도 된다. N = a * b (2 <= a <= b <= N-1) 에서 rootN 이하의 a를 발견하지 못했으면 b는 존재하지 않기 때문이다

이유: rootN 이상의 a가 존재하면 b = N / a인데 a가 rootN보다 크므로 b가 rootN보다 작게 된다. 근데 그러면 a <= b가 아니므로 존재할 수 없다.

따라서 2부터 rootN까지 나눠보면서 소수 판정을 진행하면 된다.

코드

import sys

N = int(sys.stdin.readline())
inPu = list(map(int, sys.stdin.readline().split()))
answer = 0
for i in inPu:
    if i == 1: continue
    primeFlag = True
    for K in range(2, int(i**(1/2)) + 1):
        if i % K == 0: primeFlag = False
    if primeFlag: answer += 1
    else: pass

print(answer)