NAIAHD

문제 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 파이썬