211202 파이썬 코딩테스트 수업 2일차

memoization 

import time
memo = [0, 1]
 
def fibo_memoi(num):
    global memo
    if num >= 2 and len(memo) <= num:
        memo.append(fibo_memoi(num-1) + fibo_memoi(num-2))
    return memo[num]
 
start_time = time.time()
res = fibo_memoi(34)
end_time = time.time()
spent_time = end_time - start_time
print(res, "time:", spent_time * 1000, "ms")

0.0ms 걸림

그렇다고 모든 문제에 memoization을 사용할 수는 없음

이분탐색

이분탐색 기법을 이용해 효율적으로 값을 찾아보세요

오름차순으로 정렬된 배열에서 원하는 숫자(target)을 찾는 알고리즘

1. 배열 전체의 중간 값을 target 값과 비교

2. 중간 값이 target 값보다 크면 왼쪽 부분만 비교

3. 왼쪽 부분의 중간 값을 다시 target과 비교

이분탐색 방법에는 2가지가 있다.

반복, 재귀

반복

target = 25
m_list = [30, 94, 27, 92, 21, 3, 37, 25, 47, 53, 98, 19, 32, 7]
length = len(m_list)
m_list.sort()
print(m_list)
 
#반복
left = 0
right = length - 1
while left <= right:
    mid = (right+left)//2
    if m_list[mid] == target:
        print(mid+1)
        break
    elif m_list[mid] > target:
        right = mid - 1
    else:
        left = mid + 1

재귀

#재귀
def binarySearch(array, target_value, left_index, right_index):
    mid_index = (left_index + right_index)//2
    print(mid_index)
    mid_value = array[mid_index]
    if target_value == mid_value:
        print("answer(index):", mid_index+1)
    elif target_value < mid_value:
        binarySearch(array, target_value, left_index, mid_index-1)
    else:
        binarySearch(array, target_value, mid_index+1, right_index)
 
target = 25
m_list = [30, 94, 27, 92, 21, 3, 37, 25, 47, 53, 98, 19, 32, 7]
length = len(m_list)
m_list.sort()
print(m_list)
 
 
left = 0
right = length - 1
binarySearch(m_list, target, left, right)

그래프

엣지를 지나 그래프의 노드를 탐험해봅시다.

dfs, bfs, 완전탐색, 그리디도 사실 그래프다.

그래서 출제 빈도가 낮다고 표시되어 있는 것

프로그래머스 문제 풀이

해시 문제

완주하지 못한 선수

https://programmers.co.kr/learn/courses/30/lessons/42576

https://blog.naver.com/sag120/222423219638

내 코드

def solution(participant, completion):
    dictmp = {}
    
    for i in participant:
        try:dictmp[i] += 1
        except:dictmp[i] = 1
    
    for i in completion:
        if i in dictmp:
            dictmp[i] -= 1
    
    for i in dictmp:
        if dictmp[i]==1:
            return i

남의 코드 1

def solution(participant, completion):
    answer = ''
    playerList = {}
    
    for i in participant:
        if i in playerList:
            playerList[i] = playerList.get(i)-1
        else:
            playerList[i] = 0
        
    for i in completion:
        if i in playerList:
            playerList[i] = playerList.get(i)+1
    
    for i in participant:
        if playerList.get(i) <= 0:
            answer=i
            break
    
    return answer

남의 코드 2

def solution(participant, completion):
    mydict={}
    for i in participant:
        mydict[i]=mydict.get(i,0)+1
    for i in completion:
        mydict[i]-=1
    answer=[x for x in mydict if mydict.get(x)>0]
    
    return answer[0]

남의 코드 3

def solution(participant, completion):
    participant.sort()
    completion.sort()
    for i in range(len(participant)):
        try:
            if participant[i] != completion[i]:
                return participant[i]
        except:
            return participant[i]

스택/큐 문제

기능개발

https://programmers.co.kr/learn/courses/30/lessons/42586