[백준/기본기 다지기(2)] 최대공약수(유클리드 호제)&최소공배수, 브루트포스, 피보나치 수(재귀)

피보나치 수 5

import sys
sys.setrecursionlimit(5000)
n = int(input())

def fibonacci(k):
    if k == 0:
        return 0
    if k == 1:
        return 1
    
    return fibonacci(k-2) + fibonacci(k-1)

print(fibonacci(n))

---

일곱 난쟁이 

• 브루트포스, 모든 조합 중 합이 100인 것만 출력
  • 리스트 원소 한 줄에 1개씩 출력하기 : print(*i, sep = '\n')
  • combinations 라이브러리의 결과는 튜플로 나온다 [(a, b), (a, b)]
    • 튜플 타입은 정렬이 필요하면 sorted(튜플)해야함

  import sys
  from itertools import combinations
  
  input = sys.stdin.readline
  
  for i in list(combinations([int(input()) for _ in range(9)], 7)):
      if sum(i) == 100:
          i.sort()
          print(*i, sep = '\\n')
          break
  

---

최대공약수와 최소공배수 

1) 최대공약수 - 유클리드 호제법

• x / y를 계속하면서 나머지가 0일 때의 y값이 최대 공약수
• x에는 y값을, y에는 나머지를 넣으며 계속 반복

2) 최소공배수 - x*y // 최대공약수

 

#1) 최대공약수 - 유클리드 호제법
# x / y를 계속하면서 나머지가 0일 때의 y값이 최대 공약수
# x에는 y값을, y에는 나머지를 넣으며 계속 반복

def gcd(x, y):
    while(y):
        x, y = y, x % y
    return x

#2) 최소공배수 - x*y // 최대공약수
def lcd(x, y):
    return (x * y) // gcd(x, y)

x, y = map(int, input().split())
print(gcd(x, y))
print(lcd(x, y))