IT-garden

최대공약수(GCD : Greatest Common Divisor)
최대공약수는 두 자연수의 공통된 약수 중 가장 큰 수를 의미합니다.

최소공배수(LCM : Least Common Multiple)

최소공배수는 두 자연수의 공통된 배수 중 가장 작은 수를 의미합니다.

최소공배수 = 두 자연수의 곱 / 최대공약수

유클리드 알고리즘은 자연수 2개의 최대공약수를 구하는 알고리즘입니다.
2개의 자연수 a, b(a > b)에 대해 a를 b로 나눈 나머지를 r(0 < r < b)이라 하면 a와 b의 최대공약수는 b와 r의 최대공약수와 같습니다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수입니다. 이 알고리즘은 명시적으로 기술된 가장 오래된 알고리즘으로도 알려져 있습니다.

유클리드 알고리즘은
1. a, b 두 수가 주어집니다. (a > b)
2. b가 0이면 a을 리턴합니다.
3. a가 b로 나눠 떨어지지 않으면 a를 b로, b를 a에서 b로 나눈 나머지를 대입하고 1번으로 돌아갑니다.
3. a가 b로 나눠 떨어지면 b을 리턴합니다.

유클리드 알고리즘을 이용해 54, 20의 최대공약수를 구하는 예시입니다. (%는 나머지 구하기)
54 % 20 = 14
20 % 14 = 6
14 % 6 = 2
6 % 2 = 0

6 % 2가 0이 되기 때문에 최대공약수는 2가 됩니다.

이를 이용해 54*20/2=540를 계산하면 나오면 540이 최소공배수가 됩니다.

유클리드 알고리즘을 이용해 54, 24의 최대공약수를 구하는 예시입니다.
54 % 24 = 6
24 % 6 = 0
24 % 6가 0이 되기 때문에 최대공약수는 6이 됩니다.

최대공약수(GCD)와 최소공배수(LCM) 알고리즘의 파이썬 코드입니다.

def gcd(a,b): # 최대공약수
    if b == 0:
        return a
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)

x=54
y=20

# 최대공약수(GCD)
# 출력>>2
print(gcd(x,y))

# 출력>>6
print(gcd(54,24))

# 최소공배수(LCM)
# 출력>>540
print(int(x*y/gcd(x,y)))

문제

명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.

먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.

각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다.

예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.

• S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다.
• S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다.
• S = 3, E = 3인 경우 1은 팰린드롬이다.
• S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다.

자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다.

둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거나 같은 자연수이다.

셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다.

넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하나씩 주어진다.

출력

총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍 

정답

import sys
input = lambda : sys.stdin.readline().strip()

n=int(input())
a=list(map(int,input().split()))
m=int(input())
dp=[[0]*n for i in range(n)]

for i in range(n): # 길이가 1인 경우
    dp[i][i]=1

for i in range(n-1): # 길이가 2인 경우 
    if a[i] == a[i+1]:
        dp[i][i+1]=1

for i in range(1,n): # 길이가 3 이상인 경우
    for j in range(2,i+1):
        if a[i] == a[i-j] and dp[i-j+1][i-1] == 1:
            dp[i-j][i]=1
        
for i in range(m):
    s,e=map(int,input().split())
    print(dp[s-1][e-1])

백준 알고리즘 10942번 : https://www.acmicpc.net/problem/10942

문제

N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.

각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다.

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다.

출력

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 문제의 규칙에 맞게 갈 수 있는 경로의 개수를 출력한다. 경로의 개수는 263-1보다 작거나 같다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍

힌트

정답

import sys
input = lambda : sys.stdin.readline().strip()

n=int(input())
a=[list(map(int,input().split())) for i in range(n)]

dp=[[0]*n for i in range(n)] # 방문 횟수 
dp[0][0]=1

for i in range(n):
    for j in range(n):
        if i == n-1 and j == n-1:
            break
        
        d=i+a[i][j] # 아래쪽
        r=j+a[i][j] # 오른쪽 
        
        if d < n: 
            dp[d][j] += dp[i][j]
        if r < n:
            dp[i][r] += dp[i][j]

print(dp[n-1][n-1])

dp[i][j]는 해당 위치를 방문할 수 있는 횟수입니다.

백준 알고리즘 1890번 : https://www.acmicpc.net/problem/1890

문제

비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.

• add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
• remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
• check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
• toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
• all: S를 {1, 2, ..., 20} 으로 바꾼다.
• empty: S를 공집합으로 바꾼다.

입력

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.

둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

출력

check 연산이 주어질때마다, 결과를 출력한다.

예제 입력과 출력

정답

import sys
input = lambda : sys.stdin.readline().strip()

m=int(input())
s=[]
for i in range(m):
    a=input().split()

    if a[0] == 'all':
        s.clear()
        s=[i for i in range(1,21)]
        continue
    elif a[0] == 'empty':
        s.clear()
        continue

    num=int(a[1])
    if a[0] == 'add':
        if num not in s:
            s.append(num)
    elif a[0] == 'remove':
        if num in s:
            s.remove(num)
    elif a[0] == 'check':
        if num in s:
            print(1)
        else:
            print(0)
    elif a[0] == 'toggle':
        if num in s:
            s.remove(num)
        else:
            s.append(num)

백준 알고리즘 11723번 : https://www.acmicpc.net/problem/11723

에라토스테네스의 체는 소수를 판별하는 알고리즘으로 많은 소수를 구하거나 특정 범위의 소수를 구할 때 유용합니다.

n=100
a=[]

for i in range(2,n+1):
    for j in range(2,i):
        if i%j == 0:
            break
    else:
        a.append(i)

# 출력>>[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
print(a)

기본적인 소수를 구하는 방법으로 특정 수보다 작은 모든 수로 나눠서 소수인지를 판단합니다.
위 방법은 정확하지만 범위의 소수를 모두 구할 때는 효율적이지 않습니다.

따라서 에라토스테네스의 체를 이용하면 시간을 줄이고 쉽게 소수를 구할 수 있습니다.

에라토스테네스의 체 알고리즘은

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열합니다.

2. 2부터 시작해서 나열된 수에서 지워지지 않은 수 중 가장 작은 2를 소수로 선택하고 2의 배수를 지웁니다.
3. 3도 지워지지 않았기 때문에 소수로 선택하고 3의 배수를 지웁니다.
4. 4는 지워졌기 때문에 넘어가고 5를 소수로 선택하고 5의 배수를 지웁니다.
5. 2, 3, 4와 같은 과정을 반복합니다.
6. 반복이 끝나면 지워지지 않은 수들을 소수로 출력합니다.

n=100
a=[True] * (n+1)
m = int(n ** 0.5)

for i in range(2,m+1):
    if a[i] == True:
        for j in range(i+i,n+1,i):
            a[j]=False

# 출력>>[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
print([i for i in range(2, n+1) if a[i] == True])

에라토스테네스의 체를 이용한 방법입니다.
에라토스테네스의 체를 구할 때는 또한 n의 약수가 sqrt(n) 이하여서 sqrt(n)까지 검사하면 시간을 더 줄일 수 있습니다.
(sqrt는 루트)

문제

1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 바로 이전에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

입력

첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

출력

첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다.

예제 입력과 출력

알고리즘 분류

순열

정답

n = int(input())
a = list(map(int, input().split()))

def _10973(a):
    n=len(a)-1
    i = n
    
    while i>0 and a[i-1]<=a[i]: 
        i-=1

    if i==0:
        return False
    
    j = n
    while a[i-1]<=a[j]:
        j-=1
    
    a[i-1],a[j]=a[j],a[i-1]
    
    j=n
    while i<j:
        a[i],a[j]=a[j],a[i]
        i+=1
        j-=1
    return True

if _10973(a) is True:
    for i in a:
        print(i, end=' ')
else:
    print(-1)

백준 알고리즘 10973번 : www.acmicpc.net/problem/10973