<모두의 알고리즘 with 파이썬> 문제 풀이 (1 ~ 5)

문제 1. 1부터 n까지 합 구하기
2021년 4월 2일

1. 1부터 n까지의 합

def sum(n):
  x = n * (n+1) // 2
  return x

print(sum(10))

예제. n까지의 제곱합

def sum(n):
  x = 0
  for i in range(1, n+1):
    x += i ** 2
  return x

print(sum(10))

문제 2. 최댓값 찾기
2021년 4월 2일

1. 최댓값 찾기

def max_a(a):
  m = 0
  for i in range(1, len(a)):
    if a[i] >= m:
      m = a[i]
  return m

print(max_a([1, 2, 3, 10, 100, 200]))

예제. 최댓값의 위치 찾기

def max_a(a):
  m = 0
  for i in range(1, len(a)):
    if a[i] >= m:
      m = i
  return m

print(max_a([1, 2, 3, 10, 100, 200]))

예제. 최솟값 찾기

def min_a(a):
  m = a[0]
  for i in range(1, len(a)):
    if a[i] <= m:
      m = a[i]
  return m

print(min_a([1, 2, 3, 10, 100, 200]))

문제 3. 동명이인 찾기
2021년 4월 2일

1. 동명이인 찾기

def name(a):
  s = set()
  x = set()
  for i in range(0, len(a)):
    if a[i] in s:
      x.add(a[i])
    else:
      s.add(a[i])
  return x

print(name(["가", "나", "다", "라", "가", "나"]))

예제. 두 명씩 짝 짓기

def combination(a):
  x = set()
  for i in range(0, len(a)):
    for j in range(i+1, len(a)):
      if a[i]!= a[j]:
        if (a[j], a[i]) not in x:
          x.add((a[i], a[j]))
  return x

group = ["a", "b", "c", "d", "e", "a"]
print(combination(group))

#예제 코드 - 리스트의 요소 중에 중복되는 것이 없다고 가정함
def print_pairs(a):
  n = len(a)
  for i in range(0, n-1):
    for j in range(i+1, n):
      print(a[i], "-", a[j])

name = ["a", "b", "c", "d", "a"]
print_pairs(name)

문제 4. 팩토리얼 구하기
2021년 4월 3일

1. 팩토리얼 구하기

def fact(n):
  if n == 1 :
    return 1
  return n * fact(n-1)

print(fact(5))

예제. 재귀함수로 n까지의 합 구하기

def sum(n):
  if n == 1:
    return 1
  return n + sum(n-1)

print(sum(10))

예제. 재귀함수로 최댓값 구하기

def max(a):
  if len(a) == 1:
    return a[0]
  else:
    if a[0] >= a[1]:
      del a[1]
    else:
      del a[0]
    return max(a)

a = [0, 5, 10, 3]
print(max(a))

문제 5. 최대공약수 구하기
2021년 4월 4일

1. 최대공약수 구하기

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

print(gcd(50, 4))

#이것도 된다
def gcd(a, b):
  if b == 0:
    return a
  return gcd(b, a % b)

print(gcd(4, 100))

#예시 코드
def gcd(a, b):
  i = min(a, b)
  while True:
    if a % i == 0 and b % i == 0:
      return i
    i = i - 1

예제. 재귀함수로 만드는 피보나치 수열

def fib(n):
  if n == 1:
    return 0
  if n == 2:
    return 1
  return fib(n-1) + fib(n-2)

print(fib(7))