파이썬으로 알고리즘 배우기
In [1]:
# 해법1
def sum_n(n):
s = 0
for i in range(1, n + 1):
s += i
return s
sum_n(1000)
Out[1]:
In [2]:
# 해법 2
def sum_n2(n):
return n * (n + 1) // 2
sum_n2(1000)
Out[2]:
입력 크기와 계산 횟수¶
입력의 크기(n)에 따라서 해법에 차이가 생깁니다.
- 해법1의 경우는: 덧셈 n 번
- 해법2의 경우 덧셈, 곱셈, 나눗셈 총 3번 입력의 크기가 작을때는 큰 차이가 없지만, n의 크기가 커질수록 속도에 엄청난 차이가 납니다.
O 표기법¶
계산복잡도를 표헌하는 방법 중 가장 많이 사용되는 방법입니다. 빅 오표기법이라고도 부릅니다. 간단한 예를 들면, 입력 크기 n에 대해 계산을 n번 한다면, 계산 복잡도를 O(n)이라고 표현합니다.
- O(n) : 필요한 계산 횟수가 입력크기 n과 비례할 때
- O(1): 필요한 계산 횟수가 입력크기와 무관할 때
- O(n^2) : n의 제곱에 비례하여 계산 시간이 증가함
- O(2^n) : 2의 n 제곱에 비례하여 계산 시간이 증가함
Jupyter notebook의 %%time 기능을 사용해 위의 두가지 해법의 속도를 비교해보겠습니다.
In [3]:
%%time
sum_n(100000)
Out[3]:
In [4]:
%%time
sum_n2(100000)
Out[4]:
위의 두가지 알고리즘은 같은 문제를 해결하지만 시간에서 약 열배의 차이를 보여 주고 있습니다. 더 많은 양의 입력이 들어오면 차이는 더욱더 커지게 될겁니다. 문제를 해결하는데 있어서 다양한 방법이 존재할 수 있지만 우리가 가능하면 빠른 알고리즘을 짜야할 이유는 이 때문입니다.
문제2. 최댓값 찾기¶
주어진 숫자 n개 중 가장 큰 숫자를 찾는 알고리즘을 만들어 보세요
In [5]:
def find_max(x):
n = len(x)
max_v = x[0]
for i in range(1, n):
if x[i] > max_v:
max_v = x[i]
return max_v
v = [1, 2, 3, 4, 5, 6]
find_max(v)
Out[5]:
최댓값의 위치를 구하는 알고리즘¶
In [6]:
def find_index(x):
n = len(x)
max_index = 0
for i in range(1, n):
if x[i] > x[max_index]:
max_index = i
return max_index + 1 # 0부터 시작되기때문에 1을 더해줌
v = [1, 2, 3, 4, 5, 6]
find_index(v)
Out[6]:
문제3. 같은 값 찾기¶
n개의 데이터 중에서 같은 이름을 찾아 집함으로 돌려주는 알고리즘
In [7]:
def find_same_data(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
data = ["C", "Cm", "D7", "E", "Cm"]
find_same_data(data)
Out[7]:
In [8]:
# 해법 1
def fact1(n):
result = 1
for i in range(1, n + 1):
result *= i
return result
fact1(10)
Out[8]:
In [9]:
# 해법2, 재귀 호출 사용
def fact2(n):
if n <= 1:
return 1
return n * fact2(n - 1)
fact2(10)
Out[9]:
1부터 n까지 합을 구하는 문제1을 재귀호출로 다시 한번 풀어보겠습니다.
In [10]:
def sum_n(n):
if n == 0:
return 0
return sum_n(n - 1) + n
sum_n(100)
Out[10]:
In [11]:
# 해법1
def gcd(a, b):
i = min(a, b)
while True:
if a % i == 0 and b % i == 0:
return i
i = i - 1
gcd(102, 414)
Out[11]:
In [12]:
# 해법2, 유클리드 알고리즘을 이용해 최대 공약수를 구하는 알고리즘
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
gcd(102, 414)
Out[12]:
문제6. 하노이 탑 옮기기¶
원반이 n개인 하노이 탑을 옮기기 위한 이동순서를 출력해보세요.
In [13]:
def hanoi(n, from_pos, to_pos, aux_pos):
if n == i:
print(from_pos, " >> ", to_pos)
return
hanoi(n - 1, from_pos, aux_pos, to_pos)
print(from_pos, " >> ", to_pos)
hanoi(n - 1, aux_pos, to_pos, from_pos)
In [14]:
# 해법 1
def search_list(a, x):
n = len(a)
for i in range(0, n):
if x == a[i]:
return i + 1
else:
pass
return "None" # 없으면 None을 출력합니다.
v = [14, 12, 512, 23, 15, 63, 84, 23, 6]
search_list(v, 23)
Out[14]:
In [15]:
# 해법2: 리스트에 같은 값이 여러개 있을 경우
# 모든 위치를 리스트로 돌려주는 알고리즘
def search_list(a, x):
n = len(a)
result = []
for i in range(0, n):
if x == a[i]:
result.append(i + 1)
else:
pass
return result
v = [14, 12, 512, 23, 15, 63, 84, 23, 6]
search_list(v, 23)
Out[15]:
문제8. 선택 정렬¶
리스트 안의 자료를 한 번씩 비교하는 방법과 거의 같습니다. 비교횟수가 입력 크기의 제곱에 비례하는 O(n^2) 알고리즘이므로 시간이 굉장히 오래 걸립니다.
In [16]:
def sel_sort(a):
n = len(a)
for i in range(0, n - 1):
min_index = i
for j in range(i + 1, n):
if a[j] < a[min_index]:
min_index = j
a[i], a[min_index] = a[min_index], a[i]
print(a)
d = [2, 4, 5, 1, 7]
sel_sort(d)
문제9. 삽입 정렬¶
삽입 정렬은 특정 굥우를 제외하면 선택정렬과 같인 O(n^2)알고리즘 입니다. 그래서 시간이 굉장히 오래 걸립니다.
In [17]:
def ins_sort(a):
n = len(a)
for i in range(1, n):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
d = [2, 4, 5, 1, 7]
ins_sort(d)
print(d)
문제10. 병합 정렬¶
주어진 문제를 절반으로 나눈 다음 각각을 재귀 호출로 풀어가는 방식입니다. 이런 기법을 분할 정복 이라고 부릅니다. 계산의 복잡도는 O(n*logn)으로 선택정렬이나 삽입정렬보다 빠릅니다.
In [18]:
def merge_sort(a):
n = len(a)
if n <= 1:
return
mid = n // 2
group1 = a[:mid]
group2 = a[mid:]
merge_sort(group1)
merge_sort(group2)
i1 = 0
i2 = 0
ia = 0
while i1 < len(group1) and i2 < len(group2):
if group1[i1] < group2[i2]:
a[ia] = group1[i1]
i1 += 1
ia += 1
else:
a[ia] = group2[i2]
i2 += 1
ia += 1
while i1 < len(group1):
a[ia] = group1[i1]
i1 += 1
ia += 1
while i2 < len(group2):
a[ia] = group2[i2]
i2 += 1
ia += 1
d = [6, 3, 2, 6, 10, 23, 1]
merge_sort(d)
print(d)
문제11. 퀵 정렬¶
그룹을 둘로 나눠 재귀호출을하는 방식으로 앞서본 병랍 정렬과 유사하지만, 그룹을 나눌 떄 미리 기준과 비교해서 나누는 것이 다릅니다.
In [19]:
def quick_sort(a, start, end):
if end - start <= 0:
return
pivot = a[end]
i = start
for j in range(start, end):
if a[j] <= pivot:
a[i], a[j] = a[j], a[i]
i += 1
a[i], a[end] = a[end], a[i]
quick_sort(a, start, i - 1)
quick_sort(a, i + 1, end)
def quick_sort_(a):
quick_sort(a, 0, len(a) - 1)
d = [6, 8, 3, 9, 10, 1, 2, 4]
quick_sort_(d)
print(d)
In [20]:
def binary_search(a, x):
start = 0
end = len(a) - 1
while start <= end:
mid = (start + end) // 2
if x == a[mid]:
return mid + 1 # 숫자1을 더해서 알기쉽게
elif x > a[mid]:
start = mid + 1
else:
end = mid - 1
return None # 찾지 못했을때
d = [6, 8, 3, 9, 10, 1, 2, 4]
print(binary_search(d, 8))
In [21]:
def palindrome(s):
que = []
stack = []
for x in s:
if x.isalpha():
que.append(x.lower())
stack.append(x.lower())
while que:
if que.pop(0) != stack.pop():
return False
return True
print(palindrome("Kayak"))
문제14. 딕셔너리로 같은 이름 찾기¶
파이썬의 딕셔너리라는 자료 구조를 사용해 풀어보겠습니다.
In [22]:
def find_name(a):
name_dic = {}
for name in a:
if name in name_dic:
name_dic[name] += 1
else:
name_dic[name] = 1
result = set()
for name in name_dic:
if name_dic[name] >= 2:
result.add(name)
return result
name = ["Jake", "Jim", "Jake"]
find_name(name)
Out[22]:
문제15. 친구의 친구찾기¶
친구관계를 이용해 직간접적으로 아는 모든 사람을 출력하는 알고리즘을 만들어 보세요.
In [23]:
def print_all_friends(g, start):
que = []
done = set()
que.append(start)
done.add(start)
while que:
p = que.pop(0)
print(p)
for x in g[p]:
if x not in done:
que.append(x)
done.add(x)
friends = {
"Summer": ["John", "Jake", "Mike"],
"John": ["Summer", "Mike"],
"June": ["Jake", "Tom"],
"Jake": ["Tom"],
"Tom": ["Summer"],
"Mike": ["Summer"],
}
print_all_friends(friends, "Summer")
끝으로¶
알고리즘이란 무엇인가? 라는 질문에서 시작해 15가지의 문제를 통해 알아보았습니다. 풀어 본 문제들은 쉬운 문제지만 알고리즘에 대한 접근법은 동일합니다. 앞으로도 여러분들이 더 많은 문제와 해답을 위한 노력을 기울이길 기원합니다.
