def sum_n(n):
a = 0
for i in range(1, n+1):
a = a + i
return a
print(sum_n(10))
print(sum_n(100))
55
5050
for문을 이용하여 a에 저장된 값을 하나씩 늘려가는 방법이다.
def sum_n(n):
return n * (n + 1) // 2
print(sum_n(10))
print(sum_n(100))
55
5050
등차수열의 합을 구하는 공식인
을 이용하여 간단하게 작성할 수 있다.
첫 번째 방법은 입력값 이 커질수록 덧셈을 많이 반복하지만, 두 번째 방법은 값의 크기와 관계없이 연산을 한번씩만 하면 답을 얻을 수 있기 때문에 더욱 좋은 방법이다.
이렇게 주어진 문제를 푸는 여러 가지 방법 중 어떤 방법이 더 좋은 것인지 판단할 때 필요한 것이 '알고리즘 분석' 이다
어떤 알고리즘이 문제를 풀기 위해 해야 하는 계산이 얼마나 복잡한지 나타낸 정도를 '계산 복잡도(complexity)' 라고 한다. 계산 복잡도를 표현하는 방법에는 여러가지가 있는데, 그 중 대문자 O표기법을 많이 사용한다(빅 오 표기법)
첫 번째 알고리즘은 입력크기 에 대해 사칙연산을 n번 해야한다. 이 때 이 알고리즘의 계산 복잡도를 이라고 표현한다. 필요한 계산 횟수가 입력 크기에 '정비례' 할 때 이라고 표현한다.
두 번째 알고리즘은 입력 크기 n과 무관하게 사칙연산을 세 번해야 한다. 이 때 알고리즘의 계산 복잡도는 로 표현한다.
def find_max(a):
max_v = a[0]
for i in range(1,len(a)):
if a[i] > max_v:
max_v = a[i]
return max_v
리스트의 첫 번째 값을 저장해놓고, 다음 값을 첫 번째 값과 비교해 크다면 max_v에 할당하여 최댓값을 찾는 알고리즘이다.
이 알고리즘 또한 입력 크기가 일 때 계산은 정비례관계에 있기 때문에, 계산복잡도를 으로 표현할 수 있다.
def find_max_idx(a):
max_idx = 0
for i in range(1,len(a)):
if a[i] > a[max_idx]:
max_idx = i
return max_idx
name = ["Tom", "Jerry", "Mike", "Tom"]
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
n번째 이름을 마지막까지 같은지 차례차례 비교하고, 같은 이름이 있다면 result 집합에 추가한다. 마지막은 비교하지 않아도 되기 따문에, 두 번째 for문의 범위는 range(i+1, n)이 된다.
이 경우 계산복잡도는, 입력크기(이름 숫자) 에 대해
번이다, 이를 등차수열의 합으로 계산하면
번이 된다. 결국 의 제곱에 비례해서 계산시간이 변하는 것이 핵심이기 때문에, 계산복잡도를 으로 표현할 수 있다.
#1부터 n까지 연속한 숫자의 제곱의 합을 구하는 프로그램
def pow_sum1(n):
a = 0
for i in range(1, n+1):
a = a + i ** 2
return a
def pow_sum2(n):
return n * (n + 1) * (2 * n + 1) // 6
#숫자 n개를 리스트로 입력받아 최솟값을 구하는 프로그램
lst = list(map(int, input().split()))
deffind_min(a):
min_v = a[0]
for i in range(1,len(a)):
if a[i] < min_v:
min_v = a[i]
return min_v
print(find_min(lst))
#n명 중 두 명을 뽑아 짝을 지을 수 있는 모든 조합을 출력하는 프로그램
lst = ["Tom", "Jerry", "Mike"]
def pair_name(a):
n = len(a)
for i in range(0, n - 1):
for j in range(i + 1, n):
print(a[i], "-", a[j])
print(pair_name(lst))
def fact_1(n):
f = 1
for i in range(1, n + 1):
f = f * i
return f
def fact_2(n):
if n <=1 :
return 1
return n * fact_2(n - 1)
fact_2 함수는 의 성질을 이용하여 작성한 재귀호출 코드이다. 반복문을 이용한 알고리즘과 재귀 호출을 이용한 알고리즘의 계산복잡도는 모두 이다.
def gcd_1(a, b):
i = min(a, b)
while True:
if a % i == 0 and b % i == 0:
return i
i = i - 1
def gcd_2(a,b):
if b == 0:
return a
return gcd_2(b, a 5 b)
gcd_1 코드는 두 수 중 더 작은 값을 놓고 1씩 줄여가며 공통된 약수인지 비교해보는 코드이다. gcd_2 코드는 유클리드 알고리즘을 이용한 코드인데, 수학자 유클리드가 생각해낸 최대공약수의 성질에 따라 작성한 코드이다.
a와 b의 최대공약수는 'b'와 'a를 b로 나눈 나머지'의 최대공약수와 같다.
원반이 n개인 하노이의 탑 옮기기 (출발점 from, 도착점 to, 보조 aux)
# 하노이이의 탑 알고리즘
def hanoi(n, from_pos, to_pos, aux_pos):
if n == 1:
print(from_pos, "->", to_pos)
return
hanoi(n - 1, from_pos, aux_pos, to_pos) # 원반 n-1개를 2번 기둥으로 이동
print(from_pos, "->", to_pos) # 가장 큰 원반을 3번 기둥으로 이동
hanoi(n - 1, aux_pos, to_pos, from_pos) # 2번 기둥에 있는 n-1개 원반을 3번 기둥으로 이동
탑의 층수가 높을수록 원반을 더 많이 움직여야 한다. 층의 탑을 옮기려면 원반을 모두 번 옮겨야 하는 것을 알 수 있으므로, 계산복잡도를 으로 나타낼 수 있다.
# 1부터 n까지의 합 구하기(재귀 호출)
def Q4_1(n):
if n <=1 :
return 1
return n + Q4_1(n-1)
# 숫자 n개 중에서 최댓값 찾기
def Q4_2(a):
n = len(a)
if n <= 1:
return a[0]
max_tmp = Q4_2(a[0:n-1])
if max_tmp > a[n-1]:
return max_tmp
else:
return a[n-1]
# 피보나치 수열
def Q5_1(n):
if n <= 1:
return n
return Q5_1(n-1) + Q5_1(n-2)
def serch_list(a,x);
n = len(a)
for i in range(0, n):
if x == a[i]:
return i
return -1
주어진 리스트에서 특정값의 위치를 찾아 돌려주는 알고리즘
#1
def find_min_idx(a):
n = len(a)
min_idx = 0
for i in range(1, n):
if a[i] < a[min_idx]:
min_idx = i
return min_idx
def sel_sort(a):
result = []
while a:
min_idx = find_min_idx(a)
value = a.pop(min_idx)
result.append(value)
return result
#2
def sel_sort(a):
n = len(a)
for i in range(0, n - 1):
min_idx = i
for j in range(i+1, n):
if a[j] < a[min_idx]:
min_idx = j
a[i], a[min_idx] = a[min_idx], a[i]
선택정렬은 리스트의 최솟값을 하나씩 빼서 새로운 리스트에 넣어 정렬하는 방법이다. 계산복잡도 :
#1
def find_ins_idx(r, v):
for i in range(0, len(r)):
if v < r[i]:
return i
return len(r) # 찾아서 없으면 맨 뒤
def ins_sort(a):
result = []
while a:
value = a.pop(0) # 리스트에서 한개 꺼내서
ins_idx = find_ins_idx(result, value) # 값이 들어갈 위치를 찾아
result.insert(ins_idx, value) # 찾은 위치에 삽입
return result
#2
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
삽입 정렬은 값을 하나 꺼내 새로운 리스트의 적당한 위치를 찾아 삽입해 정렬하는 방법이다. 계산복잡도 :
#1
def merge_sort(a):
n = len(a)
if n <= 1: # 종료 조건
return a
mid = n // 2
g1 = merge_sort(a[:mid])
g2 = merge_sort(a[mid:])
result = []
while g1 and g2:
if g1[0] < g2[0]:
result.append(g1.pop(0))
else :
result.append(g2.pop(0))
while g1:
result.append(g1.pop(0))
while g2:
result.append(g2.pop(0))
병합정렬은 리스트를 절반으로 나눈 다음, 서로 첫 번째 값들을 비교하며 재귀 호출로 풀어가는 방식이다. 계산복잡도 :
def quick_sort(a):
n = len(a)
if n <= 1:
return a
pivot = a[-1] # 기준값
g1 = []
g2 = []
for i in range(0, n -1): # 마지막 값은 기준값
if a[i] < pivot:
g1.append(a[i]) # 크면 g1
else:
g2.append(a[i]) # 작으면 g2
return quick_sort(g1) + pivot + quick_sort(g2)
퀵정렬은 기준값(pivot)을 정한 뒤, 그 값보다 큰 그룹과 작은 그룹을 나누어가며 재귀호출로 풀어가는 방식이다.
퀵 정렬의 경우, 기준값을 잘 못잡는 경우(가장 크거나 작은 값을 기준값으로 잡는 경우) 선택정렬이나 삽입정렬처럼 계산복잡도가 이 되어버리지만, 평균적일 때는 이다.
def binary_serch(a, x):
start = 0
end = len(a) - 1
while start <= end:
mid = (start + end) // 2
if x == a[mid]:
return mid
elif x > a[mid]:
start = mid + 1
else:
end = mid - 1
return -1
이분탐색이란 정렬된 리스트에서 특정값을 찾아 위치를 찾는 문제에서 리스트의 중간값과 특정값을 비교해보며 탐색하는 알고리즘이다.
계산복잡도 :
# 7_1
def serch_list_2(a,x):
n = len(a)
ans = []
for i in range(0, n):
if x == a[i]:
ans.append(i)
if ans != []:
return ans
else:
return -1
# 7_3
def serch_student(s_no, s_name, num):
for i in range(0, len(s_no)) :
if num == s_no[i]:
return s_name[i]
return "?"
# 11_1 거품정렬
def bubble_sort(a):
n = len(a)
while True:
changed = False
for i in range(0, n - 1):
if a[i] > a[i + 1]:
print(a)
a[i], a[i + 1] = a[i + 1], a[i]
changed = True
if changed == False:
return
# 12_1 재귀 호출을 이용한 이분탐색
def binary_serch_2(a, x, start, end):
if start > end:
return -1
mid = (start + end) // 2
if x == a[mid]:
return mid
elif x > a[mid]:
return binary_serch_2(a, x, mid + 1, end)
else :
return binary_serch_2(a, x, start, mid - 1)
return -1
큐와 스택은 컴퓨터 과학에서 다루는 여러 가지 자료 중 가장 기본것인 것으로, 자료를 넣는 동작과 빼는 동작을 할 수 있으며, 자료가 일렬로 보관된다는 공통점이 있지만, 자료를 넣고 뺄 때 동작하는 방식이 서로 다르다.
큐(queue)는 줄서기에 비유할 수 있다. 택시를 타기 위해 줄을 서는 과정에서, 택시가 도착하면 가장 먼저 줄을 선 사람이 가장 먼저 택시를 타게 되는 것처럼 큐도 같은 특징을 가지고 있다. First In First Out
큐에 자료를 한 개 집어넣는 동작을 인큐(enqueue), 꺼내는 동작을 디큐(dequeue)라고 표현한다.
스택(stack)은 접시 쌓기에 비유할 수 있다. 다 먹은 접시를 쌓을 때 접시를 차곡차곡 위로 쌓아 올리고, 설거지 하기위해 접시를 꺼낼 때도 가장 위에 있는 접시부터 꺼내는 것처럼, 스택은 가장 마지막에 들어간 자료를 가장 먼저 꺼내는 특징을 가지고 있다. Last In First Out
순서대로 읽어도 거꾸로 읽어도 그 내용이 같은 낱말을 회문(palindrome)이라고 한다. 어떤 문장이 주어졌을 때, 이 문장이 회문인지 아닌지 찾는 알고리즘을 작성한다.
def palindrome(s):
qu = []
st = []
for x in s:
if x.isalpha():
qu.append(x.lower())
st.append(x.lower())
while qu:
qu.pop(0) != st.pop
return False
return True
def find_same_name(a):
name_dict = {}
for name in a:
if name in name_dict:
name_dict[name] += 1
else:
name_dict = 1
result = set()
for name in name_dict:
if name_dict[name] >= 2:
result.add(name)
return result
문제3 에서 리스트를 이용해 작성했던 알고리즘은 모든 사람을 서로 비교하여 같은 이름이 있는지 찾아내는 방식으로, 사람수가 n명일 때 계산 복잡도는 이었지만, 딕셔너리를 이용해 알고리즘을 작성했을 땐 의 시간복잡도를 가지는 것을 알 수 있다.
친구관계를 이용하여 직접 아는 친구들과 그 친구들의 친구들, 직간접적으로 아는 모든 사람들을 출력하는 프로그램을 작성하려 한다. 친구 관계 문제를 풀기 위해 꼭지점들과 꼭지점 사이를 연결한 선의 집합을 이용한 그래프를 이용해 친구관계를 선으로 표현할 수 있다.
1. Summer와 John은 친구 관계 입니다.
2. Summer와 Justin은 친구 관계 입니다.
3. Summer와 Mike는 친구 관계 입니다.
4. Justion과 May는 친구 관계 입니다.
5. May와 Kim은 친구 관계 입니다.
6. John과 Justin은 친구 관계 입니다.
7. Justin과 Mike는 친구 관계 입니다.
8. Tom과 Jerry는 친구 관계 입니다.
(출처 : https://stricky.tistory.com/196)
fr_info = {
'Summer' : ['John', 'Justin', 'Mike'],
'John' : ['Summer', 'Justin'],
'Justin' : ['John', 'Summer', 'Mike', 'May'],
'Mike' : ['Summer', 'Justin'],
'May' : ['Justin', 'Kim'],
'Kim' : ['May'],
'Tom' : ['Jerry'],
'Jerry' : ['Tom']
}
def all_friends(g, start):
qu = []
done = set()
qu.append(start)
done.add(start)
while qu:
p = qu.pop(0)
print(p)
for x in g[p]:
if x not in done:
qu.append(x)
done.add(x)
처리할 사람을 저장할 큐qu
를 만들고, 큐에 이미 추가한 사람을 저장할 집합done
을 만들어 큐에사람이 남아 있다면 큐에서 처리할 사람을 꺼내 출력한 후, 큐에 추가된 적이 없는 사람을 골라 집합에 추가하는 과정을 반복하는 방식으로 코드를 구현할 수 있다.
A와 B가 친구이고, B와 C가 친구라고 가정할 때, A-B(1), B-c(1)의 친밀도를 가진다. A와 C는 B를 통해 친구의 친구가 되었으므로 A를 기준으로 C의 친밀도는 2라는 것을 알 수 있다. 이 성질을 이용해 친구들을 큐에 넣을 때 친밀도를 증가시키면서 친밀도 계산 알고리즘을 구현할 수 있다.
def print_all_friends(g, start):
qu = []
done = set()
qu.append((start, 0))
done.add(start)
while qu:
(p, d) = qu.pop(0)
print(p, d)
for x in g[p]:
if x not in done:
qu.append((x, d + 1))
done.add(x)
# 13_1
def solution(s):
s = s.upper()
size = len(s)
if s == s[::-1]:
return True
else:
return False
# 14_1
def solution(info, num):
if num in info:
return info
else:
return "?"
# 15_1
def sulution(g, start):
qu = []
done = set()
qu.append(start)
done.add(start)
while qu:
p = qu.pop(0)
print(p)
for x in g[p]:
if x not in done:
qu.append(x)
done.add(x)
미로의 형태와 출발점과 도착점이 주어졌을 때, 최단 경로를 찾는 것을 컴퓨터로 통해 구현하려면 어떻게 해야할까?
이때 필요한 것이 모델링
이다. 모델링이란 주어진 문제를 정형화라거나 단순화해서 수학이나 프로그램으로 설명할 수 있도록 다시 표현하는 것을 말한다.
미로 정보를 그래프로 나타내고, 이를 딕셔너리로 바꾸면 미로문제를 모델링
할 수 있다.
maze = {
'a' : ['e'],
'b' : ['c','f'],
'c' : ['b','d'],
'd' : ['c'],
'e' : ['a','i'],
'f' : ['b','g','j'],
'g' : ['f','h'],
'h' : ['g','l'],
'i' : ['e','m'],
'j' : ['f','k','n'],
'k' : ['j','o'],
'l' : ['h','p'],
'm' : ['i','n'],
'n' : ['m','j'],
'o' : ['k'],
'p' : ['l']
}
def solve_maze(g, start, end):
qu = []
done = set()
qu.append(start)
done.add(start)
while qu:
p = qu.pop(0)
v = p[-1]
if v == end:
return p
for x in g[v]:
if x not in done:
qu.append(p + x)
done.add(x)
return "?"
겉보기에는 같은 동전 n개에서 싸고 가벼운 재료로 만들어진 가짜동전을 양팔저울을 이용해 찾아내는 알고리즘
a부터 b까지 동전을 저울의 왼쪽, c에서 d까지 동전을 저울의 오른쪽에 올려 저울질하는 함수이다. 왼쪽이 가볍다면 왼쪽에 양팔저울이 있다는 것이고 -1을 리턴하고, 오른쪽에 있으면 1을 리턴한다. 양쪽 무게가 같다면 어느 쪽에도 가짜 동전이 없는 것이고 결과값을 0을 리턴하는데, 이는 저울에 올리지 않은 동전 중에 가짜 동전이 있다는 것이다.
def weigh(a, b, c, d):
fake = 29 # 가짜동전의 위치, 알고리즘은 weigh함수를 이용해 값을 맞춰야한다.
if a <= fake and fake <= b:
return -1
if c <= fake and fake <= d:
return 1
return 0
모든 동전을 하나씩 올려놓고 비교할 수 있지만, 이분 탐색을 활용해 반씩 그룹을 나누어 비교하면 더욱 효율적으로 알고리즘을 작성할 수 있다.
def find_fakecoin(left, right):
# 종료 조건 : 가짜 동전이 있을 범위 안에 동전이 한 개일때
if left == right:
return left
half = (right - left + 1) // 2
g1_left = left
g1_right = left + half - 1
g2_left = left + half
g2_right = g2_left + half - 1
result = weigh(g1_left, g1_right, g2_left, g2_right)
if result == -1: # 그룹 1이 가벼움
return find_fakecoin(g1_left, g1_right)
elif result == 1: # 그룹 2가 가벼움
return find_fakecoin(g2_left, g2_right)
else:
return right
동전을 하나씩 비교할 경우 계산복잡도는 이지만, 동전을 절반씩 나누어 후보를 좁히며 비교하면 으로 더욱 효율적으로 구현할 수 있다. 리스트 탐색에서의 이분탐색과 가짜동전문제는 겉으로 볼 때 다른문제로 보이지만, 잘 생각해보면 비슷한 문제임을 알 수 있다.
어떤 주식에 대해 특정 기간동안 가격 변화가 주어졌을 때, 그 주식 한 주를 한 번 사고 팔아 얻을 수 있는 최대 수익계산 알고리즘
가능한 모든 경우를 비교하면 직관적이지만, 불필요한 비교를 너무 많이해 비교횟수가 커지게 된다.
주식을 사는 날이 아닌 파는 날을 중심으로 이전 날들의 주가 중 최솟값을 알면 최대 수익을 쉽게 계산할 수 있다.
def max_profit(prices):
n = len(prices)
max_profit = 0
min_price = prices[0] # 첫째 날의 주가를 주가의 최솟값으로 기억
for i in range(1, n):
# 지금까지의 최솟값에 주식을 사서 i날에 팔 때의 수익
profit = prices[i] - min_price
if profit > max_profit:
max_profit = profit
if prices[i] < min_price:
min_price = prices[i]
return max_profit