알고리즘
어떤 문제를 해결하기 위해 정해놓은 일련의 절차
배열
하나의 값을 저장하는 변수가 아니라 묶음 단위로 값을 저장하는 자료구조
리스트(list)
원소를 수정할 수 있는(mutable) 리스트형 객체.
num_list = [ 1, 2, 3, 4 ]
num_list = list([1, 2, 3, 4])
num_list = list(range(1, 5))튜플(tuple)
원소에 순서를 매겨 결합한 것으로 원소의 순서를 변경할 수 없는(immutable) 자료형
num_tuple = (1, 2, 3, 4)
num_tuple = 1, 2, 3, 4,
num_tuple = (1, ) # 원소가 1개인 경우 꼭 마지막에 ,를 표기한다
num_tuple = 1,
num_tuple = ()
num_tuple = tuple([1, 2, 3, 4])
num_tuple = tuple('ABC') # ('A', 'B', 'C')
num_tuple = tuple(range(5))배열 원소 풀기 ( Unpack )
num_list = [1, 2, 3]
a, b, c = [1, 2, 3]
print(a)
print(b)
print(c)Mutable, Immutable
- Mutable - 값을 변경할 수 있는
- Immutable - 값을 변경할 수 없는
| Mutable | 리스트(list), 딕셔너리(dict), 집합(set) |
|---|---|
| Immutable | 수(num), 문자열(str), 튜플(tuple) |
💡 파이썬은 변수에 값을 담는 방식이 아닌, 변수가 특정 값의 식별번호를 바라보게하는 방식을 사용한다.
자료구조
데이터 단위와 데이터 자체 사이의 물리적 또는 논리적인 관계, 데이터가 모여있는 구조
Python for-else, while-else
for-else
for i in range(10):
if i % 7:
print(i);
else:
break
else:
print('STOP!')
# 0
# 1
# 2
# 3
# 4
# 5
# 6for 반복문을 수행한후 else문을 수행한다. break문이 포함된 경우, break가 동작하면 else 문이 동작하지 않는다.
while-else
countdown = 5
while countdown > 0:
print(countdown)
if (countdown) == 1:
break
else :
print('Countdown is over!') # break문으로 인해 동작하지 않는다.소수판단 알고리즘
count = 0
ptr = 0
prime = [ None ] * 500
prime[ptr] = 2
ptr += 1
for n in range(3, 1001, 2):
for i in range(1, ptr):
count += 1
if n % prime[i] == 0:
break
else:
prime[ptr] = n
ptr += 1
print(prime)알고리즘 개선 - n의 제곱근 보다 작은 소수로 나누어 떨어지지 않으면 n은 소수다.
count = 0
ptr = 0
prime = [ None ] * 500
prime[ptr] = 2
ptr += 1
prime[ptr] = 3
ptr += 1
for n in range(5, 1001, 2):
i = 1;
while prime[i] * prime[i] <= n:
count += 2
if n % prime[i] == 0:
break
else:
prime[ptr] = n
ptr += 1
count += 1+ 소수찾기 - 에라토스테네스의 체
- 0 과 1을 제외한, 2부터 모든 정수의 배열을 만든다.
- 아래 로직을 반복한다.
- 배열 내 가장 작은 정수가 소수인 경우 해당 숫자의 배수를 배열 내에서 삭제한다.
import math
def sieve_of_eratosthenes(number):
is_prime_array = [ True for _ in range(number + 1)]
is_prime_array[0] = False
is_prime_array[0] = False
for index in range(2, int(math.sqrt(number)) + 1):
if is_prime_array[index] == True:
j = 2
while index * j <= number:
is_prime_array[index * j] = False
j += 1
for index in range(2, len(is_prime_array)):
if is_prime_array[index]:
print(index, end = " ")
sieve_of_eratosthenes(100)재귀 Recursion
자기 자신을 포함하고, 자신을 다시 사용하여 정의하는 경우를 재귀(Recursion)이라고 한다.
# 재귀 함수예시 factorial
def factorial(n):
if (n == 0):
return 1
return n * factorial(n - 1)직접 재귀와 간접 재귀
직접 재귀 - 자기 자신을 직접 호출 하는 방식 a() ⇒ a()
간접 재귀 - 함수내에서 다른 함수를 호출하고, 다른 함수 내에서 재호출 되는 경우 a() ⇒ b() ⇒ a()
유클리드 호제법
💡 두 정수값의 최대 공약수를 재귀적으로 찾는 방법def gcd (x, y):
if y == 0:
return x
return gcd(y, x % y)재귀 알고리즘 분석
하향식 분석
가장 위쪽의 함수호출을 시작으로 계단식으로 아래로 내려가며 하는 분석을 하향식 분석이라고 한다.
하향식의 경우 같은 함수를 여러번 호출할 수 있어 비효율적일 수 있다.
상향식 분석
반대로 쌓아 올리면서 분석하는 방법. 조건부의 마지막 부분부터 고려하여 상위 단계로 쌓아가는 방식
def recur(n):
if n < 0:
recur(n - 2)
print(n)
recur(n - 1)
recur(4)하향식의 경우 recur(4) 부터 실행해간다. 예시의 경우 print문을 중심으로 위 아래로 코드를 실행해야하다보니 결국 마지막 연산인 recur(0)을 여러번 해야했고, 결과 값을 조합하기 어렵게 느껴졌다.
상향식의 경우 조건부를 확인해서 recur(0)부터 시작해서 n을 늘려가며 실행한다. 예시에 한해서, 상위 결과 값을 도출할때 이전의 하위 결과 값을 그대로 가져다 붙이는 느낌의 계산이 많아서 비교적 편했다.
재귀 알고리즘의 비재귀적 표현
재귀의 특징은 자기 자신을 반복해서 return함으로서 이전 연산 값을 활용할 수 있다는 점이다.
재귀를 제거하려면 이전 연산에 대한 누적 데이터가 필요한데 이때 Stack이 선택지가 될 수 있다.
# before
def recur(n):
if n < 0:
recur(n - 2)
print(n)
recur(n - 1)
# after
from stack import Stack
def recur (n):
s = Stack(n)
while True:
if n > 0:
s.push(n)
n = n - 1
continue
if not s.is_empty():
n = s.pop()
print(n)
n -= 2
continue
breakif __name__ == '__main__' ?
__name__ 은 함수의 모듈 이름을 가지고 있는 내장 변수이다.
파일 이름이 ‘abc_string’인 경우 __name__ 변수에 ‘abc_string’이 저장된다.
실행기준에 따라 __name__ 변수의 이름이 바뀐다.
‘a.py’라는 파일에서 ‘b.py’ 모듈을 import해서 사용하는 경우, 각 파일 내 __name__ 값은 다음과 같아진다.
a.py => '__main__'
b.py => 'b'직접 실행된 파일의 경우 name이 '__main__' 으로 저장되고 import 되는 경우 모듈의 이름으로 변수에 할당된다.
따라서if __name__ == '__main__' 을 활용하는 이유는 해당 조건문을 통해 현재 모듈이 프로그램의 시작점인지 판단하기 위해서이다.
if __name__ == '__main__' 없는 ‘b.py’파일을 ‘a.py’ 에 Import하면 ‘b.py’의 코드가 실행되어 버린다.
시간복잡도, 공간복잡도
시간복잡도
문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 의미한다. 일반적인 효율적인 코드라는 것은 입력값이 커짐에 따라 증가하는 실행시간의 비율을 최소화한 알고리즘을 말한다.
시간 복잡도는 주로 빅-오(Big-O) 표기법을 사용한다.
Big-O 표기법
Big-O는 최악의 경우를 고려한 표기법이며, 프로그램 실행시 ‘이정도까지 시간이 소요된다.’를 고려한 표기법이다.
주요한 BIg-O표기법으로는 O(1), O(n), O(log n), O(2log n), O(n**2), O(2n)이 있다.
O(1)- 상수 복잡도 알고리즘의 입력 크기에 구애받지 않는 경우 상수시간으로 표시한다. ex) 정수(이진수로 표현되는)가 짝수이거나 홀수인지 결정
O(n)- 선형 복잡도 입력값이 증가함에 따라 시간도 같은 비율로 증가하는 것을 의미한다. ex) 정렬되지 않은 배열에서 가장 작은 수 또는 가장 큰 수를 탐색
O(log n)- 로그 복잡도 컴퓨터는 이진 시스템을 사용하기 때문에 로그 밑은 대부분 2이다. O(log n)의 경우 인스턴스 연산이 각 인스턴스에 대해서 최대한 줄어드는 것이 필요하기 때문에 높은 효율을 가지고 있다. ex) 이진탐색트리
O(n^2)- 다항 복잡도 입력값이 증가함에 따라 시간이 제곱수의 비율로 증가하는 것을 의미한다. 예) 버블 정렬, 삽입 정렬
O(2n)- 기하급수적 복잡도 가장 느린 시간 복잡도
공간 복잡도
프로그램의 실행과 완료에 얼마나 많은 메모리(공간)이 필요한지를 의미한다.
공간 복잡도 역시 Big-O로 표기할 수 있다.
예를 들어 중첩 for문을 사용하여 길이가 n인 배열을 n개 가지고 있는 2차원 배열을 생성하는 경우 이때 공간 복잡도는 n^2이다
