NAIAHD

알고리즘: 간단히 말해 '어떤 문제를 풀기 위한 절차나 방법'입니다.

입력 ->과정 -> 출력

문제: 어떤 숫자의 절댓값 구하기

입력 : 절댓값을 구할 실수 a

출력 : a의 절댓값

알고리즘 분석: 알고리즘의 성능이나 특징을 분석하는 것 

첫째마당 알고리즘 기초

문제 01: 1부터 n까지의 합 구하기

입력 : 1....2

출력 : 5050

입력 -> 알고리즘 -> 출력

def sum_n(n):

  s = 0

  for i range(1,n+1):

    s = s + i

  return s

알고리즘 분석: 

def sum_n(n):

  return n * (n+1) //2

계산복잡도 complexity:어떤 알고리즘이 문제를 풀기 위해 해야 하는 계산이 얼마나 복잡한지 나타낸 정도

02. 최댓값 찾기

def find_max(a):

  n = len(a)

  max_v = a[0]

  for i in range(1,n):

    if a[i] > max_v:

      max_v = a[i]

  return max_v

03. 동명이인 찾기

def find_same_name(a):

  n = len(a)

  result = set()

  for i in range(0,n-1):

    for j in range(i+1, n):

      if a[i] == a[j]

        result.add(a[i])

  return result

02. 재귀호출

재귀호출은 함수가 자기 자신을 다시 호출하는 것을 뜻합니다.

04. 팩토리얼 구하기

1부터 n까지의 곱 , 즉 팩토리얼 구하는 문제 

• 1.팩터리얼 

def fact(n):

  f = 1

  for i in range(1, n+1):

    f = f*i

  return f

• 2. 러시아 인형

• 3. 재귀호출 : 다시 돌아가 부르기

RecursionError:특정 조건이 되면 더는 자신을 호출하지 않고 멈추도록 설계하지 않으면 

계속 반복하다가 재귀 에러가 난다. 

• 4. 재귀호출 알고리즘

def fact(n):

   if n <= 1:

     return 1

   return n * fact(n-1)

• 5. 알고리즘 분석

계산 복잡도 O(n)

종료 조건이 없으면 재귀 에러 나 스택 오버플로 등 프로그램 에러가 발생해 비정상적인 

동작을 할 수 도 있다. 

05. 최대 공약수 구하기 

두 자연수 a와 b의 최대 공약수를 구하는 알고리즘

• 1. 최대 공약수 알고리즘

최대 공약수 성질

1. 두 수 중 더 작은 값을 i에 저장한다.

2. i가 두 수의 공통된 약수인지 확인한다.

3. 공통된 약수이면 이 값을 결괏값으로 돌려주고 종료한다.

4. 공통된 약수가 아니면 i를 1만큼 감소시키고 2번으로 돌아가 반복합니다.(1은 모든 

정수의 약수이므로 i가 1이되면 1을 결괏값으로 돌려주고 종료합니다.

def gcd(a,b):

  i = min(a,b)

  while True:

     if a % i == 0 and b % i ==0:

        return i

     i = i - 1

• 2. 유클리드 알고리즘 

def gcd(a,b):

  if b == 0:

    return a

  return gcd(b, a % b)

06. 하노이의 탑 옮기기 

• 1. 하노이의 탑 

간단한 원반 옮기기 퍼즐 이다.

크기가 다른 원반 n개를 출발점 기둥에서 도착점 기둥으로 전부 옮겨야 한다.

원반은 한 번에 한 개씩만 옮길 수 있다

원반을 옮길 때는 한 기둥의 맨 위 원반을 뽑아 , 다른 기둥의 맨 위로만 옮길 수 있다.

원반을 옮기는 과정에서 큰 원반을 작은 원반 위로 올릴 수 없다.

• 2. 하노이의 탑 
• 3. 하노이의 탑 알고리즘 

1-A: 원반이 한개면 그냥 옮기면 끝 (종료 조건)

1-B: 원반이 n개일 때

   1 : 1번 기둥에 있는 n개 원반 중 n-1개를 2번 기둥으로 옮깁니다.

   2 : 1번 기둥에 남아 있는 가장 큰 원반을 3번 기둥으로 옮깁니다.

   3 : 2번 기둥에 있는 n-1개 원반을 다시 3번 기둥으로 옮깁니다.

def hanoi(n , from_pos, to_pos, aux_pos)

   if n == 1:

     print(from_pos , "->", to_pos)

     return

   honoi(n-1, from_pos, aux_pos, to_pos)

   print(from_pos,"->", to_pos)

  honoi(n-1, aux_pos, to_pos, from_pos)

• 4. 알고리즘 분석 

O(1): n과 무관하게 일정한 시간이 걸림

O(n): n과 비례하여 계산 시간이 증가함

O(n^2): n의 제곱에 비례하여 계산 시간이 증가함

O(2^n): 2의 제곱에 비례하여 계산 시간이 증가함

출처: 모두의 알고리즘 with python