greentea31's Note

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)

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

풀이 과정

최대공약수는 유클리드 호제법을 이용해서 구할 수 있다.

GCD(a, b)를 a, b의 최대공약수라고 하고 a % b = r 이라고 하면 GCD(a, b) = GCD(b, r)이 성립한다. 이 과정을 반복해서 GCD(c, 0)이 되면 c가 두 수 a, b의 최대공약수다.

ex) GCD(24, 16) = GCD(16, 8) = GCD(8, 0) => 24와 16의 최대공약수는 8

최소공배수 LCM은 a*b / GCD임이 알려져 있으니 이를 통해 구하면 된다.

ex) LCM(24, 16) = 24 * 16 / 8 = 48 => 24와 16의 최소공배수는 48

코드

import sys

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

lcm = lambda a, b: a*b//gcd(a, b)


a, b = map(int, input().split())
print(gcd(a, b))
print(lcm(a, b))

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

풀이 과정

(A+B) mod M = ((A mod M) + (B mod M)) mod M

(AxB) mod M = ((A mod M) x (B mod M)) mod M

(A-B) mod M = ((A mod M) - (B mod M) + M) mod M은 모두 성립한다.

따라서 문제에서 물어보는 것은 모두 같다가 정답이고 실제로 출력해보면 실제로 같게 나온다.

코드

import sys

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

print((A+B)%C)
print((A+B)%C)
print((A*B)%C)
print((A*B)%C)

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

풀이 과정

오큰수 문제와 비슷하게 접근하면 된다. 수열 A에 등장한 횟수를 배열에 저장하고, 오등큰수를 찾지 못한 수의 index를 스택에 저장한다. 그리고 다음 수를 인식하면서 stack top의 index에 해당하는 수보다 등장 횟수가 더 많으면 그 index의 해당하는 수의 오등큰수를 바꿔주면 된다.

코드

import sys

N = int(input())
A = list(map(int, input().split()))

NGF = [-1] * N
F = [0] * 1000010

stack = []

for i in A:
    F[i] += 1

for i in range(N):
    while len(stack) and F[A[i]] > F[A[stack[-1]]]:
        NGF[stack.pop()] = A[i]
    stack.append(i)

for i in NGF:
    print(i, end=' ')

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

풀이 과정

문제를 다 읽으면 수열을 다 입력받은 상태에서 Ai의 다음 원소부터 끝까지 검색하면서 Ai보다 큰 수가 보이면 바로 출력해주는 방식이 떠오르지만 이 방법은 O(N^2) 방법이고, A의 크기가 100만이므로 시간 제한 1초 내로 해결할 수 없다.

스택을 이용한 더 효율적인 방법으로 풀어보자. 스택을 하나 생성하고, 오큰수가 담겨있는 배열 NGE를 만들고 -1로 초기화 하자.

입력 배열 A의 첫 번째 원소부터 살펴보면서 오큰수를 아직 못 찾은 수의 index를 스택에 저장하면서, 다음 index j를 확인했을 때 스택탑의 index i와 비교해 Ai < Aj이면 NGE[i] = Aj로 두고 스택에서 원소를 꺼내는 과정을 Ai < Aj가 아닐 때까지 반복해주자. 이러면 A의 원소에 대해 존재하는 모든 오큰수가 구해진다.

왜 이러한 방법이 성립할까? 스택에서 더 작은 수의 index일수록 위에 담겨있기 때문이다. 더 큰 수의 index는 i의 오큰수가 되어서 스택에 들어오지 않고 기존 수보다 더 작은 수의 index만 스택에 쌓여간다.

코드

import sys

N = int(input())
A = list(map(int, input().split()))
NGE = [-1 for x in range(N)]
stack = []

for j in range(N):
    if len(stack) == 0:
        stack.append(j)
        continue
    i = stack[-1]
    while A[i] < A[j]:
        NGE[i] = A[j]
        stack.pop()
        if len(stack) == 0: break
        else: i = stack[-1]
    stack.append(j)

for i in range(N): print(NGE[i], end=' ')

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

풀이 과정

count = 아직 안끝난 쇠막대기의 개수

answer = 정답 이라고 하자.

'(' 인식시 일단 쇠막대기의 시작이라고 간주 => count += 1

')' 인식시 앞 문자가 '('이면 앞의 '('이 쇠막대기의 시작이 아니였으므로 count -= 1, 그 후 안끝난 쇠막대기들 자르니까 answer += count를 해주고, 앞 문자가 '('이 아니면 쇠막대기의 끝이므로 count -= 1, answer += 1를 해주면 된다.

코드

import sys

solve = list(input())
count = 0
answer = 0
for i in solve:
    if i == '(':
        count += 1
    elif i == ')':
        if stack[-1] == '(':
            count -= 1
            answer += count
        else:
            count -= 1
            answer += 1

print(answer)