최대공약수, 최소공배수

최대공약수

def solution(a, b):
    min_num = a if a < b else b
    for i in range(min_num, 0, -1):
        if a % i == 0 and b % i == 0:
            answer = i
            break
    return answer

최소공배수

1.

def solution(a, b):
    max_num = a if a > b else b
    for i in range(max_num, a * b + 1):
        if i % a == 0 and i % b == 0:
            answer = i
            break
    return print(answer)

2.

def solution(a, b):
    min_num = a if a < b else b
    for i in range(1, min_num + 1):
        if not (a * i) % b:
            answer = a * i
            break
    return print(answer)

거듭제곱근 구하기

• 16의 거듭제곱근은 (2 이상): 2 4, 4 2.
• 이때 제곱근 구하는 식
  n ** (1.00 / 실수형 숫자)
• 실수형: float(숫자)

n = int(input())

for i in range(2, n + 1):
    if not n ** (1.00 / float(i)) % 2:
        print(int(n ** (1.00 / float(i))), i)

약수의 개수 판별하기

if int(n ** 0.5) == n ** 0.5:
	print('약수의 개수가 홀수 입니다')
else:
	print('약수의 개수가 짝수 입니다')

: 제곱수이면, 약수의 개수는 홀수이다.

소수 구하기

소수 판별하기

기본적인 방법

def is_prime_num(n):
    for i in range(2, n):
        if n % i == 0:
            return False # 소수가 아님
    return True # 소수

조금 더 빠른 방법: 약수 이용하기

• 아이디어: 어떤 수의 제곱근을 기준으로 약수들이 서로 대칭됨을 이용하자.
  • 제곱근의 왼쪽에 약수가 없다면, 오른쪽에도 없을 것이다.

def is_prime_num(n):
    for i in range(2, int(n**(1/2))+1): # n의 제곱근(정수화함) + 1 범위까지
        if n % i == 0:
            return False # 소수가 아님
    return True # 소수

특정 숫자까지의 수 중에서 소수 구하기

• 소요 시간 비교해보기

1. 이중 for문

n = int(input())
prime_num = []

for i in range(2, n + 1):
    prime = True
    for j in range(2, i):
        if i % j == 0:
            prime = False
            break
    if prime:
        prime_num.append(i)

print(prime_num)

2. 에라토스테네스의 체 (훨씬 빠름!)

1. 2 ~ N까지의 범위가 담긴 배열을 만든다.
2. 해당 배열 내의 가장 작은 수 i 부터 시작하여, i의 배수들을 해당 배열에서 지워준다. (i는 소수이기 때문에 i자체는 지우지 않는다.)
3. 주어진 범위 내에서 i의 배수가 모두 지워지면 i 다음으로 작은 수의 배수를 같은 방식으로 배열에서 지워준다.
4. 더 이상 반복할 수 없을 때까지 2, 3번의 과정을 반복해준다.

1. 배수가 아닌 수를 리스트에 추가하며..: 더 비효율적인가? 시간 체크하기!

prime_num = list(range(2, n + 1))
n_cnt_all = [] # 소수가 아닌 수를 담을 list

for num in range(2, n + 1):
    if not num in n_cnt_all: 
        n_cnt = [] # 초기화
        
        for cnt in range(2, n + 1):
            num_cnt = num * cnt # 배수 찾기
            
            if num_cnt in prime_num:
                n_cnt.append(num_cnt)
                
        n_cnt_all.append(n_cnt)
        # 배수인 수를 제외한 수만 담음
        prime_num = [i for i in prime_num if i not in n_cnt]
        
print(prime_num)

• 중복 계산을 피하기 위해 if num_cnt in prime_num: 추가

2. 특정 수가 지워졌는지 확인하며..(좀 더 효율적)

def is_prime_num(n):
    arr = [True] * (n + 1) # 특정 수가 지워졌는지 아닌지 확인하기 위한 배열
    arr[0], arr[1] = False, False

    for i in range(2, n + 1):
        if arr[i] == True: # 특정 수가 지워지지 않았다면 (소수여서)
            j = 2

            while (i * j) <= n:
                arr[i*j] = False # i의 배수의 값을 False로 지워준다.
                j += 1

    return arr

prime_num = []
arr = is_prime_num(100) # 0 ~ 50중 소수를 구하기 위한 함수

for i in range(len(arr)):
    if arr[i] == True:
        prime_num.append(i)
print(prime_num)

• 출처: 소수판별 알고리즘 - 파이썬 (Python)

가장 긴 증가하는 부분 수열(LIS)

• 오름차순 일 때

arr	5	20	10	40	30	50	60
dp	1	2	2	3	3	4	5

• 정렬하면

arr	5	10	20	30	40	50	60

• 내림차순 일 때

arr	60	50	30	10	40	20	5	70
dp	1	2	3	2	3	4	5	1

• 정렬하면

arr	70	60	50	40	30	20	10	5

응용 문제:

: 윗 문제가 내림차순에서 몇개를 제거하는지 물었다면, 이번에는 오름차순 수열에서 통채로 제거할 부분의 수를 물어본다면? 띄엄띄엄 제거 안됨.

• 단순히 띄엄띄엄 제거 가능하고 개수를 물었다면 len(arr) - max(dp) 였겠지만..
• 띄엄띄엄도 안되니까, 인덱스를 알아야하지 않을까?

1. sort를 이용하여 일일히 비교하기

import sys

a = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

arr2 = arr.copy()
arr2.sort()
start, end = 0, 0

for i in range(a):
    if arr[i] != arr2[i]:
        start = i
        break

for j in range(a - 1, -1, -1):
    if arr[j] != arr2[j]:
        end = j
        break
print(end - start + 1)

배수 판정법

• 13의 배수 판정법
  : (1의 자리 수 * 4 + 1의 자리수를 뺀 나머지)가 13의 배수라면, 원래 수도 13의 배수
  • 예: 156
    : 6 * 4 + 15 = 39는 13의 배수. 따라서 156은 13의 배수.
• 응용: 주어진 수를 마음대로 재배열 했을때, 13의 배수인지 판별하자

  import sys
from itertools import permutations
a=list(sys.stdin.readline().rstrip())
b=list(permutations(a, len(a)))
c=True
for i in b:
    if not (int(i[-1])*4 + int(''.join(i[:-1]))) % 13:
        c=False
        print('YES')
        break
if c:
    print('NO')

시:분:초

초를 시:분:초로

# time: 초가 주어짐
h = (time // 3600) % 24 # 시간
time %= 3600
m = time // 60 # 분
s = time % 60 # 초

시:분:초를 초로

# h:m:t가 주어짐
h*3600+m*60+s