알고리즘: 간단히 말해 '어떤 문제를 풀기 위한 절차나 방법'입니다.
입력 ->과정 -> 출력
문제: 어떤 숫자의 절댓값 구하기
입력 : 절댓값을 구할 실수 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
'책 > 모두의 알고리즘 with 파이썬' 카테고리의 다른 글
04. 자료구조,05. 응용문제 (0) | 2020.08.30 |
---|---|
셋째 마당 : 탐색과 정렬 (0) | 2020.08.27 |