모두를 위한 알고리즘(예제)
1부터 n까지 연속한 숫자의 합을 구하는 알고리즘 1¶
In [1]:
# 입력: n
# 출력: 1부터 n까지의 숫자를 더한 값
def sum_n(n):
s = 0 # 합을 계산할 변수
for i in range(1, n + 1): # 1부터 n까지 반복 (n+1은 제외)
s = s + i
return s
print(sum_n(10)) # 1부터 10까지 합(입력:10, 출력:55)
print(sum_n(100)) # 1부터 100까지 합(입력:100, 출력:5050)
1부터 n까지 연속한 숫자의 합을 구하는 알고리즘 2¶
In [2]:
# 입력: n
# 출력: 1부터 n까지의 숫자를 더한 값
def sum_n(n):
return n * (n + 1) // 2
print(sum_n(10)) # 1부터 10까지 합(입력:10, 출력:55)
print(sum_n(100)) # 1부터 100까지 합(입력:100, 출력:5050)
최댓값 구하기¶
In [3]:
# 입력: 숫자가 n개 들어 있는 리스트
# 출력: 숫자 n개 중 최댓값
def find_max(a):
n = len(a) # 입력 크기 n
max_v = a[0] # 리스트의 첫 번째 값을 최댓값으로 기억
for i in range(1, n): # 1부터 n-1까지 반복
if a[i] > max_v: # 이번 값이 현재까지 기억된 최댓값보다 크면
max_v = a[i] # 최댓값을 변경
return max_v
v = [17, 92, 18, 33, 58, 7, 33, 42]
print(find_max(v))
최댓값의 위치 구하기¶
In [4]:
# 입력: 숫자가 n개 들어 있는 리스트
# 출력: 숫자 n개 중에서 최댓값이 있는 위치(0부터 n-1까지의 값)
def find_max_idx(a):
n = len(a) # 입력 크기 n
max_idx = 0 # 리스트 중 0번 위치를 일단 최댓값 위치로 기억
for i in range(1, n):
if a[i] > a[max_idx]: # 이번 값이 현재까지 기억된 최댓값보다 크면
max_idx = i # 최댓값의 위치를 변경
return max_idx
v = [17, 92, 18, 33, 58, 7, 33, 42]
print(find_max_idx(v))
두 번 이상 나온 이름 찾기¶
In [5]:
# 입력: 이름이 n개 들어 있는 리스트
# 출력: 이름 n개 중 반복되는 이름의 집합
def find_same_name(a):
n = len(a) # 리스트의 자료 개수를 n에 저장
result = set() # 결과를 저장할 빈 집합
for i in range(0, n - 1): # 0부터 n-2까지 반복
for j in range(i + 1, n): # i+1부터 n-1까지 반복
if a[i] == a[j]: # 이름이 같으면
result.add(a[i]) # 찾은 이름을 result에 추가
return result
name = ["Tom", "Jerry", "Mike", "Tom"] # 대소문자 유의: 파이썬은 대소문자를 구분함
print(find_same_name(name))
name2 = ["Tom", "Jerry", "Mike", "Tom", "Mike"]
print(find_same_name(name2))
연속한 숫자의 곱을 구하는 알고리즘¶
In [6]:
# 입력: n
# 출력: 1부터 n까지 연속한 숫자를 곱한 값
def fact(n):
f = 1 # 곱을 계산할 변수, 초깃값은 1
for i in range(1, n + 1): # 1부터 n까지 반복(n+1은 제외)
f = f * i # 곱셈 연산으로 수정
return f
print(fact(1)) # 1! = 1
print(fact(5)) # 5! = 120
print(fact(10)) # 10! = 3628800
연속한 숫자의 곱을 구하는 알고리즘¶
In [7]:
# 입력: n
# 출력: 1부터 n까지 연속한 숫자를 곱한 값
def fact(n):
if n <= 1:
return 1
return n * fact(n - 1)
print(fact(1)) # 1! = 1
print(fact(5)) # 5! = 120
print(fact(10)) # 10! = 3628800
최대공약수 구하기¶
In [8]:
# 입력: a, b
# 출력: a와 b의 최대공약수
def gcd(a, b):
i = min(a, b) # 두 수 중에서 최솟값을 구하는 파이썬 함수
while True:
if a % i == 0 and b % i == 0:
return i
i = i - 1 # i를 1만큼 감소시킴
print(gcd(1, 5)) # 1
print(gcd(3, 6)) # 3
print(gcd(60, 24)) # 12
print(gcd(81, 27)) # 27
최대공약수 구하기¶
In [9]:
# 입력: a, b
# 출력: a와 b의 최대공약수
def gcd(a, b):
if b == 0: # 종료 조건
return a
return gcd(b, a % b) # 좀 더 작은 값으로 자기 자신을 호출
print(gcd(1, 5)) # 1
print(gcd(3, 6)) # 3
print(gcd(60, 24)) # 12
print(gcd(81, 27)) # 27
하노이의 탑¶
In [10]:
# 입력: 옮기려는 원반의 갯수 n
# 옮길 원반이 현재 있는 출발점 기둥 from_pos
# 원반을 옮길 도착점 기둥 to_pos
# 옮기는 과정에서 사용할 보조 기둥 aux_pos
# 출력: 원반을 옮기는 순서
def hanoi(n, from_pos, to_pos, aux_pos):
if n == 1: # 원반 한 개를 옮기는 문제면 그냥 옮기면 됨
print(from_pos, "->", to_pos)
return
# 원반 n - 1개를 aux_pos로 이동(to_pos를 보조 기둥으로)
hanoi(n - 1, from_pos, aux_pos, to_pos)
# 가장 큰 원반을 목적지로 이동
print(from_pos, "->", to_pos)
# aux_pos에 있는 원반 n-1개를 목적지로 이동(from_pos를 보조 기둥으로)
hanoi(n - 1, aux_pos, to_pos, from_pos)
print("n = 1")
hanoi(1, 1, 3, 2) # 원반 한 개를 1번 기둥에서 3번 기둥으로 이동(2번을 보조 기둥으로)
print("n = 2")
hanoi(2, 1, 3, 2) # 원반 두 개를 1번 기둥에서 3번 기둥으로 이동(2번을 보조 기둥으로)
print("n = 3")
hanoi(3, 1, 3, 2) # 원반 세 개를 1번 기둥에서 3번 기둥으로 이동(2번을 보조 기둥으로)
리스트에서 특정 숫자 위치 찾기¶
In [11]:
# 입력: 리스트 a, 찾는 값 x
# 출력: 찾으면 그 값의 위치, 찾지 못하면 -1
def search_list(a, x):
n = len(a) # 입력 크기 n
for i in range(0, n): # 리스트 a의 모든 값을 차례로
if x == a[i]: # x 값과 비교하여
return i # 같으면 위치 돌려줍니다.
return -1 # 끝까지 비교해서 없으면 -1을 돌려줍니다.
v = [17, 92, 18, 33, 58, 7, 33, 42]
print(search_list(v, 18)) # 2(순서상 세 번째지만, 위치 번호는 2)
print(search_list(v, 33)) # 3(33은 리스트에 두 번 나오지만 처음 나온 위치만 출력)
print(search_list(v, 900)) # -1(900은 리스트에 없음)
쉽게 설명한 선택 정렬¶
In [12]:
# 입력: 리스트 a
# 출력: 정렬된 새 리스트
# 주어진 리스트에서 최솟값의 위치를 돌려주는 함수
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) # 찾은 최솟값을 빼내어 value에 저장
result.append(value) # value를 결과 리스트 끝에 추가
return result
d = [2, 4, 5, 1, 3]
print(sel_sort(d))
선택 정렬¶
In [13]:
# 입력: 리스트 a
# 출력: 없음(입력으로 주어진 a가 정렬됨)
def sel_sort(a):
n = len(a)
for i in range(0, n - 1): # 0부터 n-2까지 반복
# i번 위치부터 끝까지 자료 값 중 최솟값의 위치를 찾음
min_idx = i
for j in range(i + 1, n):
if a[j] < a[min_idx]:
min_idx = j
# 찾은 최솟값을 i번 위치로
a[i], a[min_idx] = a[min_idx], a[i]
d = [2, 4, 5, 1, 3]
sel_sort(d)
print(d)
쉽게 설명한 삽입 정렬¶
In [14]:
# 입력: 리스트 a
# 출력: 정렬된 새 리스트
# 리스트 r에서 v가 들어가야 할 위치를 돌려주는 함수
def find_ins_idx(r, v):
# 이미 정렬된 리스트 r의 자료를 앞에서부터 차례로 확인하여
for i in range(0, len(r)):
# v 값보다 i번 위치에 있는 자료 값이 크면
# v가 그 값 바로 앞에 놓여야 정렬 순서가 유지됨
if v < r[i]:
return i
# 적절한 위치를 못 찾았을 때는
# v가 r의 모든 자료보다 크다는 뜻이므로 맨 뒤에 삽입
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
d = [2, 4, 5, 1, 3]
print(ins_sort(d))
삽입 정렬¶
In [15]:
# 입력: 리스트 a
# 출력: 없음(입력으로 주어진 a가 정렬됨)
def ins_sort(a):
n = len(a)
for i in range(1, n): # 1부터 n-1까지
# i번 위치의 값을 key로 저장
key = a[i]
# j를 i 바로 왼쪽 위치로 저장
j = i - 1
# 리스트의 j번 위치에 있는 값과 key를 비교해 key가 삽입될 적절한 위치를 찾음
while j >= 0 and a[j] > key:
a[j + 1] = a[j] # 삽입할 공간이 생기도록 값을 오른쪽으로 한 칸 이동
j -= 1
a[j + 1] = key # 찾은 삽입 위치에 key를 저장
d = [2, 4, 5, 1, 3]
ins_sort(d)
print(d)
쉽게 설명한 병합 정렬¶
In [16]:
# 입력: 리스트 a
# 출력: 정렬된 새 리스트
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]: # 두 그룹의 맨 앞 자료 값을 비교
# g1의 값이 더 작으면 그 값을 빼내어 결과로 추가
result.append(g1.pop(0))
else:
# g2의 값이 더 작으면 그 값을 빼내어 결과로 추가
result.append(g2.pop(0))
# 아직 남아 있는 자료들을 결과에 추가
# g1과 g2 중 이미 빈 것은 while을 바로 지나감
while g1:
result.append(g1.pop(0))
while g2:
result.append(g2.pop(0))
return result
d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
print(merge_sort(d))
병합 정렬¶
In [17]:
# 입력: 리스트 a
# 출력: 없음(입력으로 주어진 a가 정렬됨)
def merge_sort(a):
n = len(a)
# 종료 조건: 정렬할 리스트의 자료 개수가 한 개 이하이면 정렬할 필요가 없음
if n <= 1:
return
# 그룹을 나누어 각각 병합 정렬을 호출하는 과정
mid = n // 2 # 중간을 기준으로 두 그룹으로 나눔
g1 = a[:mid]
g2 = a[mid:]
merge_sort(g1) # 재귀 호출로 첫 번째 그룹을 정렬
merge_sort(g2) # 재귀 호출로 두 번째 그룹을 정렬
# 두 그룹을 하나로 병합
i1 = 0
i2 = 0
ia = 0
while i1 < len(g1) and i2 < len(g2):
if g1[i1] < g2[i2]:
a[ia] = g1[i1]
i1 += 1
ia += 1
else:
a[ia] = g2[i2]
i2 += 1
ia += 1
# 아직 남아 있는 자료들을 결과에 추가
while i1 < len(g1):
a[ia] = g1[i1]
i1 += 1
ia += 1
while i2 < len(g2):
a[ia] = g2[i2]
i2 += 1
ia += 1
d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
merge_sort(d)
print(d)
쉽게 설명한 퀵 정렬¶
In [18]:
# 입력: 리스트 a
# 출력: 정렬된 새 리스트
def quick_sort(a):
n = len(a)
# 종료 조건: 정렬할 리스트의 자료 개수가 한 개 이하이면 정렬할 필요가 없음
if n <= 1:
return a
# 기준 값을 정하고 기준에 맞춰 그룹을 나누는 과정
pivot = a[-1] # 편의상 리스트의 마지막 값을 기준 값으로 정함
g1 = [] # 그룹 1: 기준 값보다 작은 값을 담을 리스트
g2 = [] # 그룹 2: 기준 값보다 큰 값을 담을 리스트
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)
d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
print(quick_sort(d))
퀵 정렬¶
In [19]:
# 입력: 리스트 a
# 출력: 없음(입력으로 주어진 a가 정렬됨)
# 리스트 a의 어디부터(start) 어디까지(end)가 정렬 대상인지
# 범위를 지정하여 정렬하는 재귀 호출 함수
def quick_sort_sub(a, start, end):
# 종료 조건: 정렬 대상이 1개 이하면 정렬할 필요 없음
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_sub(a, start, i - 1) # 기준 값보다 작은 그룹을 재귀 호출로 다시 정렬
quick_sort_sub(a, i + 1, end) # 기준 값보다 큰 그룹을 재귀 호출로 다시 정렬
# 리스트 전체(0 ~ len(a)-1)를 대상으로 재귀 호출 함수 호출
def quick_sort(a):
quick_sort_sub(a, 0, len(a) - 1)
d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
quick_sort(d)
print(d)
리스트에서 특정 숫자 위치 찾기(이분 탐색)¶
In [20]:
# 입력: 리스트 a, 찾는 값 x
# 출력: 찾으면 그 값의 위치, 찾지 못하면 -1
def binary_search(a, x):
# 탐색할 범위를 저장하는 변수 start, end
# 리스트 전체를 범위로 탐색 시작(0 ~ len(a)-1)
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 # 찾지 못했을 때
d = [1, 4, 9, 16, 25, 36, 49, 64, 81]
print(binary_search(d, 36))
print(binary_search(d, 50))
주어진 문장이 회문인지 아닌지 찾기(큐와 스택의 특징을 이용)¶
In [21]:
# 입력: 문자열 s
# 출력: 회문이면 True, 아니면 False
def palindrome(s):
# 큐와 스택을 리스트로 정의
qu = []
st = []
# 1단계: 문자열의 알파벳 문자를 각각 큐와 스택에 넣음
for x in s:
# 해당 문자가 알파벳이면(공백, 특수문자, 숫자가 아니면)
# 큐와 스택에 각각 그 문자를 추가
if x.isalpha():
qu.append(x.lower())
st.append(x.lower())
# 2단계: 큐와 스택에 들어 있는 문자를 꺼내면서 비교
while qu: # 큐에 문자가 남아 있는 동안 반복
if qu.pop(0) != st.pop(): # 큐와 스택에서 꺼낸 문자가 다르면 회문이 아님
return False
return True
print(palindrome("Wow"))
print(palindrome("Madam, I’m Adam."))
print(palindrome("Madam, I am Adam."))
두 번 이상 나온 이름 찾기¶
In [23]:
# 입력: 이름이 n개 들어 있는 리스트
# 출력: n개의 이름 중 반복되는 이름의 집합
def find_same_name(a):
# 1단계: 각 이름의 등장 횟수를 딕셔너리로 만듦
name_dict = {}
for name in a: # 리스트 a에 있는 자료들을 차례로 반복
if name in name_dict: # 이름이 name_dict에 있으면
name_dict[name] += 1 # 등장 횟수를 1 증가
else: # 새 이름이면
name_dict[name] = 1 # 등장 횟수를 1로 저장
# 2단계: 만들어진 딕셔너리에서 등장 횟수가 2 이상인 것을 결과에 추가
result = set() # 결괏값을 저장할 빈 집합
for name in name_dict: # 딕셔너리 name_dict에 있는 자료들을 차례로 반복
if name_dict[name] >= 2:
result.add(name)
return result
name = ["Tom", "Jerry", "Mike", "Tom"] # 대소문자 유의: 파이썬은 대소문자를 구분함
print(find_same_name(name))
name2 = ["Tom", "Jerry", "Mike", "Tom", "Mike"]
print(find_same_name(name2))
친구 리스트에서 자신의 모든 친구를 찾는 알고리즘¶
In [24]:
# 입력: 친구 관계 그래프 g, 모든 친구를 찾을 자신 start
# 출력: 모든 친구의 이름
def print_all_friends(g, start):
qu = [] # 기억 장소1: 앞으로 처리해야 할 사람들을 큐에 저장
done = set() # 기억 장소2: 이미 큐에 추가한 사람들을 집합에 기록(중복 방지)
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) # 집합에도 추가
# 친구 관계 리스트
# A와 B가 친구이면
# A의 친구 리스트에도 B가 나오고, B의 친구 리스트에도 A가 나옴
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']
}
print_all_friends(fr_info, 'Summer')
print()
print_all_friends(fr_info, 'Jerry')
친구 리스트에서 자신의 모든 친구를 찾고 친구들의 친밀도를 계산하는 알고리즘¶
In [25]:
# 입력: 친구 관계 그래프 g, 모든 친구를 찾을 자신 start
# 출력: 모든 친구의 이름과 자신과의 친밀도
def print_all_friends(g, start):
qu = [] # 기억 장소 1: 앞으로 처리해야 할 (사람 이름, 친밀도) 튜플을 큐에 저장
done = set() # 기억 장소 2: 이미 큐에 추가한 사람을 집합에 기록(중복 방지)
qu.append((start, 0)) # (사람 이름, 친밀도) 정보를 하나의 튜플로 묶어 처리(자기 자신 친밀도: 0)
done.add(start) # 집합에도 추가
while qu: # 큐에 처리할 사람이 남아 있는 동안
(p, d) = qu.pop(0) # 큐에서 (사람 이름, 친밀도) 정보를 p와 d로 각각 꺼냄
print(p, d) # 사람 이름과 친밀도를 출력
for x in g[p]: # 친구들 중에
if x not in done: # 아직 큐에 추가된 적이 없는 사람을
qu.append((x, d + 1)) # 친밀도를 1 증가시켜 큐에 추가하고
done.add(x) # 집합에도 추가
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']
}
print_all_friends(fr_info, 'Summer')
print()
print_all_friends(fr_info, 'Jerry')
미로 찾기 프로그램(그래프 탐색)¶
In [26]:
# 입력: 미로 정보 g, 출발점 start, 도착점 end
# 출력: 미로를 나가기 위한 이동 경로는 문자열, 나갈 수 없는 미로면 물음표("?")
def solve_maze(g, start, end):
qu = [] # 기억 장소 1: 앞으로 처리해야 할 이동 경로를 큐에 저장
done = set() # 기억 장소 2: 이미 큐에 추가한 꼭짓점들을 집합에 기록(중복 방지)
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 "?"
# 미로 정보
# 미로의 각 위치에 알파벳으로 이름을 지정
# 각 위치에서 한 번에 이동할 수 있는 모든 위치를 선으로 연결하여 그래프로 표현
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']
}
print(solve_maze(maze, 'a', 'p'))
주어진 동전 n개 중에 가짜 동전(fake)을 찾아내는 알고리즘¶
In [27]:
# 입력: 전체 동전 위치의 시작과 끝(0, n - 1)
# 출력: 가짜 동전의 위치 번호
# 무게 재기 함수
# a에서 b까지 놓인 동전과
# c에서 d까지 놓인 동전의 무게를 비교
# a에서 b까지에 가짜 동전이 있으면(가벼우면): -1
# c에서 d까지에 가짜 동전이 있으면(가벼우면): 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
# weigh 함수(저울질)를 이용하여
# left와 right까지에 있는 가짜 동전의 위치를 찾아냄
def find_fakecoin(left, right):
for i in range(left + 1, right + 1): # left+1부터 right까지 반복
# 가장 왼쪽 동전과 나머지 동전을 차례로 비교
result = weigh(left, left, i, i)
if result == -1: # left 동전이 가벼움(left 동전이 가짜)
return left
elif result == 1: # i 동전이 가벼움(i 동전이 가짜)
return i
# 두 동전의 무게가 같으면 다음 동전으로
# 모든 동전의 무게가 같으면 가짜 동전이 없는 예외 경우
return -1
n = 100 # 전체 동전 개수
print(find_fakecoin(0, n - 1))
주어진 동전 n개 중에 가짜 동전(fake)을 찾아내는 알고리즘¶
In [28]:
# 입력: 전체 동전 위치의 시작과 끝(0, n - 1)
# 출력: 가짜 동전의 위치 번호
# 무게 재기 함수
# a에서 b까지에 놓인 동전과
# c에서 d까지에 놓인 동전의 무게를 비교
# a에서 b까지에 가짜 동전이 있으면(가벼우면): -1
# c에서 d까지에 가짜 동전이 있으면(가벼우면): 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
# weigh() 함수(저울질)를 이용하여
# left와 right까지에 놓인 가짜 동전의 위치를 찾아냄
def find_fakecoin(left, right):
# 종료 조건 : 가짜 동전이 있을 범위 안에 동전이 한 개뿐이면 그 동전이 가짜 동전임
if left == right:
return left
# left와 right까지에 놓인 동전을 두 그룹(g1_left~g1_right, g2_left~g2_right)으로 나눔
# 동전 수가 홀수면 두 그룹으로 나누고 한 개가 남음
half = (right - left + 1) // 2
g1_left = left
g1_right = left + half - 1
g2_left = left + half
g2_right = g2_left + half - 1
# 나눠진 두 그룹을 weigh() 함수를 이용하여 저울질함
result = weigh(g1_left, g1_right, g2_left, g2_right)
if result == -1: # 그룹 1이 가벼움(가짜 동전이 이 그룹에 있음)
return find_fakecoin(g1_left, g1_right) # 그룹 1 범위를 재귀 호출로 다시 조사
elif result == 1: # 그룹 2가 가벼움(가짜 동전이 이 그룹에 있음)
return find_fakecoin(g2_left, g2_right) # 그룹 2 범위를 재귀 호출로 다시 조사
else: # 두 그룹의 무게가 같으면(나뉜 두 그룹 안에 가짜 동전이 없다면)
return right # 두 그룹으로 나뉘지 않고 남은 나머지 한 개의 동전이 가짜
n = 100 # 전체 동전 개수
print(find_fakecoin(0, n - 1))
주어진 주식 가격을 보고 얻을 수 있는 최대 수익을 구하는 알고리즘¶
In [29]:
# 입력: 주식 가격의 변화 값(리스트: prices)
# 출력: 한 주를 한 번 사고팔아 얻을 수 있는 최대 수익 값
def max_profit(prices):
n = len(prices)
max_profit = 0 # 최대 수익은 항상 0 이상의 값
for i in range(0, n - 1):
for j in range(i + 1, n):
profit = prices[j] - prices[i] # i날에 사서 j날에 팔았을 때 얻을 수 있는 수익
if profit > max_profit: # 이 수익이 지금까지 최대 수익보다 크면 값을 고침
max_profit = profit
return max_profit
stock = [10300, 9600, 9800, 8200, 7800, 8300, 9500, 9800, 10200, 9500]
print(max_profit(stock))
주어진 주식 가격을 보고 얻을 수 있는 최대 수익을 구하는 알고리즘¶
In [30]:
# 입력: 주식 가격의 변화 값(리스트: prices)
# 출력: 한 주를 한 번 사고팔아 얻을 수 있는 최대 수익 값
def max_profit(prices):
n = len(prices)
max_profit = 0 # 최대 수익은 항상 0 이상의 값
min_price = prices[0] # 첫째 날의 주가를 주가의 최솟값으로 기억
for i in range(1, n): # 1부터 n-1까지 반복
profit = prices[i] - min_price # 지금까지의 최솟값에 주식을 사서 i날에 팔 때의 수익
if profit > max_profit: # 이 수익이 지금까지 최대 수익보다 크면 값을 고침
max_profit = profit
if prices[i] < min_price: # i날 주가가 최솟값보다 작으면 값을 고침
min_price = prices[i]
return max_profit
stock = [10300, 9600, 9800, 8200, 7800, 8300, 9500, 9800, 10200, 9500]
print(max_profit(stock))
최대 수익 문제를 푸는 두 알고리즘의 계산 속도 비교하기¶
In [31]:
# 최대 수익 문제를 O(n*n)과 O(n)으로 푸는 알고리즘을 각각 수행하여
# 걸린 시간을 출력/비교함
import time # 시간 측정을 위한 time 모듈
import random # 테스트 주가 생성을 위한 random 모듈
# 최대 수익: 느린 O(n*n) 알고리즘
def max_profit_slow(prices):
n = len(prices)
max_profit = 0
for i in range(0, n - 1):
for j in range(i + 1, n):
profit = prices[j] - prices[i]
if profit > max_profit:
max_profit = profit
return max_profit
# 최대 수익: 빠른 O(n) 알고리즘
def max_profit_fast(prices):
n = len(prices)
max_profit = 0
min_price = prices[0]
for i in range(1, n):
profit = prices[i] - min_price
if profit > max_profit:
max_profit = profit
if prices[i] < min_price:
min_price = prices[i]
return max_profit
def test(n):
# 테스트 자료 만들기(5000부터 20000까지의 난수를 주가로 사용)
a = []
for i in range(0, n):
a.append(random.randint(5000, 20000))
# 느린 O(n*n) 알고리즘 테스트
start = time.time() # 계산 시작 직전 시각을 기억
mps = max_profit_slow(a) # 계산 수행
end = time.time() # 계산 시작 직후 시각을 기억
time_slow = end - start # 두 시각을 빼면 계산에 걸린 시간
# 빠른 O(n) 알고리즘 테스트
start = time.time() # 계산 시작 직전 시각을 기억
mpf = max_profit_fast(a) # 계산 수행
end = time.time() # 계산 시작 직후 시각을 기억
time_fast = end - start # 두 시각을 빼면 계산에 걸린 시간
# 결과 출력: 계산 결과
print(n, mps, mpf) # 입력 크기, 각각 알고리즘이 계산한 최대 수익 값(같아야 함)
# 결과 출력: 계산 시간 비교
m = 0 # 느린 알고리즘과 빠른 알고리즘의 수행 시간 비율을 저장할 변수
if time_fast > 0: # 컴퓨터 환경에 따라 빠른 알고리즘 시간이 0으로 측정될 수 있음(이럴 때는 0을 출력)
m = time_slow / time_fast # 느린 알고리즘 시간 / 빠른 알고리즘 시간
# 입력 크기, 느린 알고리즘 수행 시간, 빠른 알고리즘 수행 시간, 느린 알고리즘 시간 / 빠른 알고리즘 시간
# %d는 정수 출력, %.5f는 소수점 다섯 자리까지 출력을 의미
print("%d %.5f %.5f %.2f" % (n, time_slow, time_fast, m))
test(100)
test(10000)
#test(100000) # 수행 시간이 오래 걸리므로 일단 주석 처리
댓글
댓글 쓰기