문제 13: 회문 찾기
큐와 스택
큐: '줄 서기'에 비유할 수 있습니다. FIFO
스택: '접시 쌓기'에 비유할 수 있습니다. LIFO
def palindrome(s):
qu = []
st = []
for x in s:
if x.isalpha():
qu.append(x.lower())
st.append(x.lower())
while qu:
if qu.pop(0) != st.pop():
return False
return True
isalpha() : 주어진 문자가 알파벳 문자에 해당하는지 확인하는 기능
문제 14 . 동명이인 찾기 딕셔너리
def find_same_name(a):
name_dict = {}
for name in a:
if name in name_dict:
mame_dict[name] += 1
else:
mame_dict[name] = 1
result = set()
for name in name_dict:
if name_dict[name] >= 2:
result.add(name)
return result
문제 15. 친구의 친구 찾기 그래프
def print_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)
###친밀도 계산
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)
05. 응용문제
문제 16. 미로 찾기 알고리즘
모델링이란 주어진 현실의 문제를 정형화하거나 단순화하여 수학이나 컴퓨터 프로그램으로 쉽세 설명할 수 있도록 다시 표현한다는 것을 말합니다.
일단 미로 정보를 입력한다.
미로 찾기 알고리즘
그래프 탐색 과정에서 지금까지 지나온 경로를 문자열로 만들어 큐에 추가한 것과 탐색 중 목적지 에 도착하면 탐색을 멈추도록 한 것을 제외하면 그래프 탐색 알고리즘과 완전히 같은 알고리즘입니다.
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 "?"
17. 가짜 동전 찾기 알고리즘
겉보기에는 똑같은 동전이 n개 있습니다. 이 중에서 한 개는 싸고 가벼운 재료로 만들어진 가짜 동전입니다. 좌우 무게를 비교할 수 있는 양팔 저울을 이용해서 다른 동전보다 가벼운 가짜 동전을 찾아내는 알고리즘을 만들어 보세요.
방법 1: 하나씩 비교하기
이 방법은 원하는 값을 찾기 위해 자료를 차례로 하나씩 비교하는 순차 탐색과 비슷합니다.
def weigh(a,b,c,d):
fake = 29
if a <= fake and fake <= b:
return -1
if c<= fake and fake <=d:
return 1
return 0
def find_fakecoin(left, right):
for i in range(left+1, right+1):
result = weight(left, left, i,i)
if result == -1:
return left
elif result == 1:
return i
return -1
방법 2: 반씩 그룹으로 나누어 비교하기
def weigh(a,b,c,d):
fake = 29
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 = weight(g1_left, g1_right,g2_left, g2_right)
if result == -1:
return find_fakecoin(g1_left,g1_right)
elif result == 1:
return find_fakecoin(g2_left,g2_right)
else:
return right문제 18 최대 수익 알고리즘
어떤 수식에 대해 특정 기간 동안의 가격 변화가 주어졌을 때 , 그 주식 한 주를 한 번 사고 팔아 얻을 수 있는 최대 수익을 계산하는 알고리즘을 만들어 보세요.
방법 1: 가능한 모든 경우를 비교하기
def max_profit(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방법 2: 한 번 반복으로 최대 수익 찾기
def max_profit(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 = price[i]
return max_profit
출처 : 모두의 알고리즘 with 파이썬
'책 > 모두의 알고리즘 with 파이썬' 카테고리의 다른 글
| 셋째 마당 : 탐색과 정렬 (0) | 2020.08.27 |
|---|---|
| 00. 들어가는 글,첫째마당 알고리즘 기초,02. 재귀호출 (0) | 2020.08.22 |