먹고 기도하고 코딩하라

기초 계산 공식과 알고리즘 본문

자료구조&알고리즘/이론

기초 계산 공식과 알고리즘

2G Dev 2021. 7. 23. 19:50
728x90
728x90

 

1. 1부터 n까지의 합 공식 : n * (n + 1) / 2

1-1. n부터 m까지의 합 공식 : ((m - n + 1) * (n + m)) / 2

2. 1부터 n까지의 제곱의 합 공식 : (n * (n + 1) * (2n + 1)) / 6

 

3. 팩토리얼 구하기

(1) 반복문

# 입력 : 팩토리얼을 구하고 싶은 정수 n
# 출력 : n! (정수)

def solution(n):
  res = 1
  for i in range(1, n+1):
    res *= i
  return res

print(solution(5))	# 120

(2) 재귀함수

# 입력 : 팩토리얼을 구하고 싶은 정수 n
# 출력 : n! (정수)

def solution(n):
  if n <= 1:
    return 1
  return n * solution(n-1)

print(solution(5))

 

4. 최대공약수 구하기 (유클리드 알고리즘)

  • x와 y의 최대공약수 gcd(x, y) == gcd(y, x%y)
  • x와 0의 최대공약수 gcd(x, 0) == x

즉, 재귀함수로 최대공약수를 구할 때면 x가 0이 되는 것을 종료 조건으로 둘 수 있다.

 

- 재귀함수

# 입력 : 최대공약수를 구하고 싶은 두 정수
# 출력 : 최대공약수

def solution(x, y):
  if y == 0:
    return x
  return solution(y, x%y)

print(solution(60, 24))

여기서 최소공배수는 x * y / gcd(x, y)로 구할 수 있다.

 

5. n번째 피보나치 수 구하기

피보나치 수열은 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... 이런 식으로 이어지는 수열이다.

특징으로는 1번째는 0, 2번째는 1, 그 뒤 n번째부터는 (n-2)+(n-1) 값이 n번째 값이 되는 특징이 있다.

if n == 0: return 0
if n == 1: return 1
else 재귀

(1) 재귀함수

# n번째 피보나치 수 구하기
# 입력 : n (정수)
# 출력 : n번째 피보나치 수

def solution(n):
  if n <= 1: return n
  return solution(n-1) + solution(n-2)

print(solution(10))	# 55

하지만 피보나치 수는 재귀로 푸는 것보다 반복문으로 푸는 것이 더 합리적이다. 이유인즉슨 n이 커질수록 solution 함수를 호출하는 횟수가 늘어나기 때문이다. 

 

(2) 반복문

def solution(n):
  if n <= 1: return n
  x = 1
  y = 1
  res = 0
  
  for _ in range(n):
    x = y
    y = res
    res = x + y
  
  return res

print(solution(10))	# 55

리스트에 append시키는 풀이도 있던데 나는 변수 3개를 써서 풀었다.

 

(3) 반복문

n번째 피보나치 수까지 수열을 출력하는 함수를 만들 수도 있다. 제너레이터를 이용했다. 제너레이터란 파이썬 시퀀스를 생성하는 객체로, 전체 시퀀스를 한 번에 메모리에 생성하고 정렬할 필요가 없다는 장점이 있다.

# 제너레이터를 만들어 n번째까지 피보나치 수 출력하기
def fib_generator(n):
  if n <= 2: return 1

  x = y = 1
  res = x + y

  for _ in range(n):
    yield x
    x = y
    y = res
    res = x + y

fib = fib_generator(10)
for i in range(10):
  print(next(fib), end=' ')

제너레이터 함수 안에서는 yield를 쓰고, yield를 쓰는 즉시 제너레이터가 중단된다. 생성된 제너레이터 객체는 yield된 부분을 기억하고 있다가 next()가 호출되면 그 위치에서부터 다시 함수를 시작한다. 

 

6. 하노이 탑

하노이 탑은 1학년 때부터 나를 지긋지긋하게 괴롭히던 문제였다. 피보나치, 팩토리얼 문제야 점화식 이해가 된다고 해도 하노이를 재귀로 푸는 걸 이해하는 게 정말 힘들었는데, 그냥 간단하게 생각하면 된다.

만약, n이 1이라면 start -> dest로 옮기고 종료한다. 
그렇지 않다면...
1. start -> aux로 n-1개의 고리를 전부 옮긴다.
2. start -> dest로 맨 밑에 깔린 1개의 고리를 옮긴다.
3. aux -> dest로 깔려 있던 n-1개의 고리를 옮긴다.

고리를 옮기는 것은 print문으로 표현하면 된다.

간단하게 정리했을 뿐 사실은 그렇게 간단하지는 않다... 왜냐하면 그 과정을 일일이 trace하다 보면 start, aux, dest가 한데 뒤섞이는 광경을 보게 되기 때문이다.

그러므로 큰 흐름만 갖고, 실제로 어떻게 움직이는지는 가급적 생각하지 말기로 하자. 이해가 안 될 때 외우다 보면 이해가 되기도 하는 법 아니던가?

def hanoi(n, start, dest, aux):
  if n == 1:
    print('{}번 고리 {} -> {}'.format(n, start, dest))
    return
  
  hanoi(n-1, start, aux, dest) # 1번
  print('{}번 고리 {} -> {}'.format(n, start, dest))  # 2번
  hanoi(n-1, aux, dest, start) # 3번

solution(4, 1, 3, 2)

'''
1번 고리 1 -> 2
2번 고리 1 -> 3
1번 고리 2 -> 3
3번 고리 1 -> 2
1번 고리 3 -> 1
2번 고리 3 -> 2
1번 고리 1 -> 2
4번 고리 1 -> 3
1번 고리 2 -> 3
2번 고리 2 -> 1
1번 고리 3 -> 1
3번 고리 2 -> 3
1번 고리 1 -> 2
2번 고리 1 -> 3
1번 고리 2 -> 3
'''

위에서 print문은 종료 조건과 종료 조건이 아닐 때가 모두 똑같음에 주목하라. print문은 항상 start에서 dest로 고리를 이동시킬 뿐이다. 그러나 실행된 결과를 보면 어떨 때는 1번 기둥(start)이 dest가 되기도 하고 2번 기둥(aux)가 start가 되기도 하는 등 재귀 함수를 실행하는 동안 기둥 관계가 계속 바뀌기 마련이다.

하노이 탑 문제는 O(2^n) 시간복잡도를 갖는다.

 

7. 소수 판별 알고리즘

어떤 수가 소수인지 알 수 있는 알고리즘을 알아본다. 소수(prime number)란 자신과 1 이외에는 약수를 아무것도 갖지 않는 수이다. 여기서는 제곱근을 사용하는 방법으로 풀어 본다. sqrt 함수를 사용해 제곱근을 구할 건데, sqrt 함수는 math 모듈 안에 들어 있다. 

(1) 일단 목표값의 절댓값을 구한다.
(2) 만약, 목표값이 4 이하라면 볼 것도 없이 소수이므로 True.
(3) 2부터 제곱근까지 1씩 더해가며 목표값이 i로 나뉘어지는지 확인한다. 만약 나뉘어진다면 소수가 아니므로 False. for 루프를 무사히 마치면 소수이므로 True이다.
# 소수 판별 알고리즘
# 입력 : n (int)
# 출력 : boolean
import math

def is_prime(n):
  n = abs(n)  # 먼저 절댓값을 구한다
  if n < 4: return True # 4보다 작으면 무조건 소수
  root = math.sqrt(n)
  for i in range(2, math.ceil(root)):
    if n % i == 0: return False
  return True

print(is_prime(505))

 

 

728x90
반응형
0 Comments
댓글쓰기 폼