211201 파이썬 코딩테스트 수업 1일차

프로그래머스 - 코딩테스트 고득점 Kit

해시

Key-value 쌍으로 데이터를 빠르게 찾아보세요.

import hashlib
def sha1_hash(input_string):
    hash_object = hashlib.sha1(input_string.encode())
    hash_value = hash_object.hexdigest()
    return hash_value
 
##print(sha1_hash("서호준"))
 
hash_value1 = sha1_hash("서호준")
print(hash_value1, ", 길이:", len(hash_value1))
 
hash_value2 = sha1_hash("안동대학교")
print(hash_value2, ", 길이:", len(hash_value2))
 
hash_value3 = sha1_hash("1234")
print(hash_value3, ", 길이:", len(hash_value3))

HashTable(HashMap, Dictionary)의 특징

데이터 저장에 차례가 없음

Key를 통해서 Value 값에 접근

Value 값은 중복 가능, Key는 중복 불가능

수정 가능

스택/큐

LIFO, FIFO, push & pop! 스택과 큐를 이용해서 문제를 풀어보세요.

스택 : Last In First Out

파이썬의 List로 구현

Push : append()

Pop : pop()

a = [1, 2, 3, 4, 5]
a.append(6)
 
res = a.pop()
res
 
print(a)
print(res, a)

큐 : First In First Out

파이썬의 List로 구현

Enqueue : append()

Dequeue : pop()

a = [1, 2, 3, 4, 5]
a.append(6)
 
res = a.pop(0)
print(res, a)

힙(Heap)

힙은 특정한 규칙을 가지는 트리로, 힙을 이용해서 우선순위 큐를 구현할 수 있습니다.

트리

  A

 B D

C E

-> 이진트리

최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리가 기본

A가 B의 부모노드이면 A의 키 값과 B의 키 값 사이에는 대소 관계

최소 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙

최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙

     10       

 15     30

40 50 100 40

   최소 힙

import heapq
heap = []
heapq.heappush(heap, 50)
print(heap)
 
 
heapq.heappush(heap, 10)
print(heap)
 
heapq.heappush(heap, 20)
print(heap)

=>

 50

10 20

heapq.heappop(heap)
print(heap)
 
heapq.heappop(heap)
print(heap)
 
heap = [50, 10, 20]
heapq.heapify(heap)
res = heapq.heappop(heap)
print(res, heap)

기본 힙은 최소힙

heap_contents = [1, 3, 5, 7, 9]
max_heap = []
for item in heap_contents:
    heapq.heappush(max_heap, item)
print(max_heap)
res = heapq.heappop(max_heap)
print(res, max_heap)

이렇게 그냥 사용하면 최대힙이 아니라 최소힙임

기본 힙을 최대힙으로 사용하기 위해서는 꼼수가 필요

heap_contents = [1, 3, 5, 7, 9]
max_heap = []
for item in heap_contents:
    heapq.heappush(max_heap, [-item, item])
print(max_heap)
res = heapq.heappop(max_heap)
print(res[1], max_heap)

이렇게 하면 최대힙 사용가능

트리인 것에 연연하지 않아도 됨

넣고 큰 것부터 빠지는구나

넣고 작은 것부터 빠지는구나만 알면 됨

정렬

정렬을 이용해서 문제를 효율적으로 풀어보세요.

a = [10, 2, 8, 3, 1]
a.sort()
print(a)
 
a = [10, 2, 8, 3, 1]
b = sorted(a)
print(b)

a = [10, 2, 8, 3, 1]
a.sort(reverse = True)
print(a)
 
a = [10, 2, 8, 3, 1]
b = sorted(a, reverse = True)
print(b)

거꾸로 정렬

dict1 = {3:"D", 2:"B", 5:"B", 4:"E", 1:"A"}
print(sorted(dict1))

dict1 = {3:"D", 2:"B", 5:"B", 4:"E", 1:"A"}
key1 = sorted(dict1)
print(dict1[key1[0]])

students = [ ("서호준", "F", 20211201), ("김동영", "A", 20211202), ("오명균", "A", 20211203)]
print(sorted(students))

students = [ ("서호준", "F", 20211201), ("김동영", "A", 20211202), ("오명균", "A", 20211203)]
print(sorted(students, key = lambda s : s[2]))

완전탐색

무식해 보여도 사실은 최고의 방법일 때가 있지요.

-> 안 놓치는 게 중요

모든 후보 검사하기

brute force 전략은 문제 해결을 위한 가장 단순하고도 확실한 전략

exhaustive search라고도 부름

답이 될 수 있는 후보를 전부 조사

역추적(back tracking)

불필요한 탐색 그만두기

더 이상 진행해도 조건에 맞는 해를 찾을 수 없는 경우에 가장 최근에 둔 수를 포기하고 다른 수를 두는 탐색을 계속 하기

실제적 구현

BFS

DFS

탐욕법(Greedy)

문제를 해결하는 과정에서 순간순간마다 최적의 결정하는 방식

전체를 보지 않고 근시안 적이기 때문에 최적의 해를 찾지 못하지만 처리 속도가 빨라서 완전 탐색의 복잡도가 너무 클 때, 의미를 갖음

만약 동전의 단위가 600 500 100원인 나라에서 1000원을 최소 개수의 동전으로 바꾼다면?

Greedy : 큰 단위부터 -> 600, 100 X 4개 -> 5개

완전 탐색 : 500 X 2개 -> 2개

BFS(너비 우선 탐색)

1. 깊이를 하나씩 내려가면서

2. 그 레벨에 있는 노드를 전부 탐색하고

3. 다음 레벨로 내려가면서 탐색

-> 큐를 이용

DFS(깊이 우선 탐색)

1. 가장 위에 있는 부모 노드의 깊숙한 방향

2. 모든 자식 노드들을 순서대로 탐색

-> 스택 또는 재귀적 함수 호출을 이용

스택 -> 소프트웨어에서 스택 사용

재귀적 함수 호출은 CPU 자체에서 스택을 이용 -> 하드웨어에서 스택 사용

=> 속도가 차이가 많이 나서 재귀적 함수 호출을 많이 사용한다.

그러나 만능열쇠처럼 재귀적 함수 호출을 쓰다보면 변형 문제를 스택을 이용하여 풀지 못하게 된다.

완전탐색, 백트래킹, BFS, DFS 이런 게 사실 하나

백준을 보면 유형이 너무 나뉘어져 있음

BFS 구현

from collections import deque
# 인접 행렬 방식
graph = [[], # 0번 인덱스
         [2, 3, 8], # 1번 인덱스
         [1, 7], # 2번 인덱스
         [1, 4, 5], # 3
         [3, 5], # 4
         [3, 4], # 5
         [7], # 6
         [2, 6, 8], # 7
         [1, 7] # 8
         ]
 
# 파이썬은 사실상 인접 행렬이 인접 리스트
# 다른 언어라면 인접 리스트보단 인접 행렬이 편할 것
 
visited = [False] * len(graph)
 
def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True
 
    while queue:
        v = queue.popleft()
        print(v, end = " ")
        for i in graph[v]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)
 
bfs(graph, 1, visited)

보통 코딩테스트 문제에선 1차원 배열이 아니라 격자 즉, 2차원 배열일 것이다.

DFS 구현

from collections import deque
# 인접 행렬 방식
graph = [[], # 0번 인덱스
         [2, 3, 8], # 1번 인덱스
         [1, 7], # 2번 인덱스
         [1, 4, 5], # 3
         [3, 5], # 4
         [3, 4], # 5
         [7], # 6
         [2, 6, 8], # 7
         [1, 7] # 8
         ]
 
# 파이썬은 사실상 인접 행렬이 인접 리스트
# 다른 언어라면 인접 리스트보단 인접 행렬이 편할 것
 
visited = [False] * len(graph)
 
def dfs(graph, v, visited):
    visited[v] = True
    print(v, end = " ")
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
 
dfs(graph, 1, visited)

동적 계획법(Dynamic Programming)

불필요한 계산을 줄이고, 효율적으로 최적해를 찾아야만 풀리는 문제들입니다.

-> 제한된 경우에서만 적용됨

Memoization(메모이제이션)

문제를 잘게 쪼개 동일 계산 반복 시, 이전 계산 값을 메모리에 저장하여, 매번 다시 실행하지 않도록 해서 실행 속도를 높이는 기술

피보나치 수열!

1 1 2 3 5 8 13

def fibo(num):
    if num == 1:
        return 1
    if num == 0:
        return 0
    return fibo(num-1) + fibo(num-2)
print(fibo(7))

재귀

시간 측정

import time
 
def fibo(num):
    if num == 1:
        return 1
    if num == 0:
        return 0
    return fibo(num-1) + fibo(num-2)
start_time = time.time()
res = fibo(34)
end_time = time.time()
spent_time = end_time - start_time
print(res, "time:", spent_time * 1000, "ms")

3초 정도 걸림

-> Memoization을 사용하면 빨라짐