[문지의 알고리즘 강의 3강] 알고리즘 테스트 1단계 맛보기 2

• 완전 탐색

   

  설명 : 무식해 보여도 사실은 최고의 방법일 때가 있습니다. 가능한 모든 상황을 조사해 문제를 풀어보세요.

  무식하게 푼다(brute-force)는 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미한다. 가능한 방법을 전부 만들어보는 알고리즘을 의미한다.

  PS(Problem Solving)을 하는 데 가장 간단하고 쉬운 방법이 무엇일까요? 답은 가능한 경우를 다 해보는 것입니다. 이게 무슨 알고리즘이야? 할 수 있겠지만, 이것도 알고리즘에 일종입니다. 전산학에서는 이를 무식하게 푼다라는 뜻의 Brute-force라 하고, 전체를 확인한다고 해서 완전 탐색 알고리즘(exhaustive search algorithm)이라고 합니다.

  어디에 쓰이는가? 하지만 대부분의 문제들은 시간 초과등의 이유로 완전 탐색으로 풀리지 않습니다. 하지만 어려운 알고리즘을 생각할 필요 없이 완전 탐색으로 풀리는 문제도 있으며, 가끔 어려운 완전 탐색 문제도 존재합니다.

  따라서, 완전 탐색 알고리즘이라는 카드를 문제 풀이에 도구로 항상 준비해두고 있어야합니다.

• 솜씨좋은장씨
• TSP 알고리즘 1: 문제 소개 및 완전탐색 구현
• 프로그래머스

• 동적계획법

  설명 : 불필요한 계산을 줄이고, 효과적으로 최적해를 찾아야만 풀리는 문제

  동적 계획법이 뭔가요?

  DP는 알고리즘 문제로 자주 나오는 디자인 패러다임 중 하나입니다. Dynamic Programming이라는 말은 고안자인 벨만이 dynamic이라는 단어가 멋있어서(…) 선택한 단어라고 합니다. 따라서 이 방법은 전산학 전반에서의 동적(dynamic) 혹은 프로그래밍(programming)이라는 단어와는 관련이 없습니다. DP의 한글 번역도 동적 프로그래밍보다는 동적 계획법으로 번역됩니다.

  구현
  1. 주어진 문제를 완전 탐색으로 해결합니다.
  2. 중복된 문제를 한번만 계산하기 위해 메모제이션을 이용합니다.
  특징 1. 부분 문제(overlapping subproblems)특징 2. 메모제이션(memoization)

def fibo_dp(num): 
	cache = [ 0 for index in range(num + 1) ] 
    cache[0] = 0 
    cache[1] = 1 
    
    for index in range(2, num + 1): 
    	cache[index] = cache[index - 1] + cache[index - 2] 
    return cache[num] 
fibo_dp(5)

• 참고 사이트
• 프로그래머스
• [Python] 파이썬 다이나믹(동적) 프로그래밍 구현, 백준 관련 문제 모음
• 동적 계획법과 분할 정복

 

• 동적 계획법에서는 이 중복되는 부분을 저장하여 재활용함으로써 속도를 향상시킬 수 있습니다. 이미 계산한 값을 저장해 둔 **메모리의 장소를 캐시(cache)**라 부르고 이를 활용하는 **최적화 기법을 메모이제이션(memoization)**이라 부릅니다.
• 동적 계획법의 접근 방식은 분할 정복과 같습니다. 주어진 문제를 더 작은 문제로 나눈 뒤 이 문제의 답을 계산하고, 이 답을 토대로 원래 문제의 답을 도출해가기 때문입니다. 하지만 분할 정복과 문제를 나누는 부분에서 차이가 납니다. 동적 계획법에서 어떤 부분 문제가 두 개 이상의 문제를 푸는 데 사용되는 데 이를 중복되는 부분 문제(overlapping subproblems)라고 부릅니다.
• 일반적인 동적 계획법 알고리즘 구현 방법
• https://youtu.be/FmXZG7D8nS4
• 안경잡이개발자 : 네이버 블로그
• 피보나치 수

  • 설명 : 분할하고 정복하면서 필요한 내용은 버리고, 찾아가는 방식. (ex. 교과서 페이지 찾을때 380 ? 180 → 250 → 410 → 390 → 380

  • 장점 : 속도가 빠르다

  • 단점 : 자료구조와 내용들이 정렬 되어있어야 한다.

  • Best : O(1)

  • worst : log(n)

    이분 탐색

    [LECTURE] 3) 알고리즘 : edwith

    https://youtu.be/Vfg6-AWGsCw

    탐색/서치의 큰 분류

    • 선형 자료구조 내에서의 탐색

      (ex. 리스트, 어레이, 스택 혹은 큐 등)

    • 비선형 자료구조 내에서의 탐색

      (ex. 트리 혹은 그래프)

    선형 자료구조의 대표적인 탐색방법

    • 설명: 일반적으로 동일한 간격(1,2,~)에 의해서 쭉 찾는 방법. (ctrl + F)

    • 장점 : 구현이 쉬움, 직관적

    • 단점 : 느리다

    • Best : O(1)

    • Worst : O(n)

     

    2. binary search (이진 탐색) - 분할정복

• 3. Search by Hashing (해싱)

def binary_search_recursion(target, start, end, data):
    if start > end:
        return None

    mid = (start + end) // 2

    if data[mid] == target:
        return mid
    elif data[mid] > target:
        end = mid - 1
    else:
        start = mid + 1        

    return binary_search_recursion(target, start, end, data)

if __name__ == '__main__':
    li = [i*3 for i in range(11)]
    target = 6
    idx = binary_search_recursion(target, 0, 10, li)

    print(li)
    print(idx)

• 정리
• 프로그래머스
• 강의노트 15-2. [탐색] 이진탐색(Binary Search) 알고리즘

 

• 1. Linear Search (선형 탐색)

• 해시

  https://youtu.be/xls6jEZNA7Y

  https://www.youtube.com/watch?v=Vi0hauJemxA&t=189s

  설명 : 해시는 Key-value쌍으로 데이터를 저장하는 자료구조입니다.

  • Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐
  • 파이썬 딕셔너리(Dictionary) 타입이 해쉬
  • 테이블의 예: Key를 가지고 바로 데이터(Value)를 꺼내는 거
  • 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용 (공간과 탐색 시간을 맞바꾸는 기법)
  • 단, 파이썬에서는 해쉬를 별도 구현할 이유가 없음 - 딕셔너리 타입을 사용하면 됨

  이해가 안된다면...아래를 한 번 더 복습

  • 해쉬(Hash): 임의 값을 고정 길이로 변환하는 것
  • 해쉬 테이블(Hash Table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
  • 해싱 함수(Hashing Function): Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수
  • 해쉬 값(Hash Value) 또는 해쉬 주소(Hash Address): Key를 해싱 함수로 연산해서, 해쉬 값을 알아내고, 이를 기반으로 해쉬 테이블에서 해당 Key에 대한 데이터 위치를 일관성있게 찾을 수 있음 (어려우니 실습에서 한번 더)
  • 슬롯(Slot): 한 개의 데이터를 저장할 수 있는 공간
  • 저장할 데이터에 대해 Key를 추출할 수 있는 별도 함수도 존재할 수

   

  예제)

  17. 해싱(hashing), 파이썬

   

  '이름'이라는 문자열을 '저장 공간의 주소'라는 숫자로 바꿔야 하니까,

  아스키 코드를 이용하면 될 것 같습니다.

  but, 고유 숫자(해시 값)가 겹치기 쉽겠죠?

  해시 값이 겹치는 걸 충돌(collision)이라고 합니다.

  우리가 만들 해시함수에서 ABC와 ACB는 충돌합니다. OTL

   

  해시값을 주소로 바로 쓰는 것을 Direct-address table이라고 부릅니다. 하지만, 고작 4개의 전화번호를 집어넣기 위해 691개 이상의 저장공간을 만들 수는 없는 일입니다. 적당한 배열의 크기를 정하고 해시값을 배열의 크기로 나눈 나머지(% modulo 연산)를 주소로 하겠습니다. 배열의 크기는 139로 합니다.

  출처: https://comdoc.tistory.com/entry/17-해싱hashing-파이썬 [ComDoc]

hash_table = list([0 for i in range(8)])

def get_key(data):
    return hash(data)

def hash_function(key):
    return key % 8

def save_data(data, value):
    hash_address = hash_function(get_key(data))
    hash_table[hash_address] = value
    
def read_data(data):
    hash_address = hash_function(get_key(data))
    return hash_table[hash_address]
save_data('Dave', '0102030200')
save_data('Andy', '01033232200')
read_data('Dave')
hash_table

• 4. 자료 구조 해쉬 테이블의 장단점과 주요 용도
  • 데이터 저장/읽기 속도가 빠르다. (검색 속도가 빠르다.)
  • 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉬움

  단점

  • 일반적으로 저장공간이 좀더 많이 필요하다.
  • 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요함

  주요 용도

  • 검색이 많이 필요한 경우
  • 저장, 삭제, 읽기가 빈번한 경우
  • 캐쉬 구현시 (중복 확인이 쉽기 때문)

  캐시란?

  기술의 발전으로 프로세서 속도는 빠르게 증가해온 반면, 메모리의 속도는 이를 따라가지 못했다. 프로세서가 아무리 빨라도 메모리의 처리 속도가 느리면 결과적으로 전체 시스템 속도는 느려진다. 이를 개선하기 위한 장치가 바로 캐시(Cache)다.
  캐시는 CPU 칩 안에 들어가는 작고 빠른 메모리다. (그리고 비싸다.) 프로세서가 매번 메인 메모리에 접근해 데이터를 받아오면 시간이 오래 걸리기 때문에 캐시에 자주 사용하는 데이터를 담아두고, 해당 데이터가 필요할 때 프로세서가 메인 메모리 대신 캐시에 접근하도록해 처리 속도를 높인다.

  💵 캐시가 동작하는 아주 구체적인 원리

  프로그래머스참고사이트

  해쉬 알고리즘(Hash Algorithm) 요약 정리, 테스트 코드

  여러분의 참고사이트
•  
• 17. 해싱(hashing), 파이썬
• 프로그래머스
• 장점
• 알아둘 것!!

강의노트 15-2. [탐색] 이진탐색(Binary Search) 알고리즘 · 초보몽키의 개발공부로그

 

 

파이썬과 컴퓨터 사이언스(기본 알고리즘): 동적 계획법과 분할 정복 - 잔재미코딩

 

 

파이썬과 컴퓨터 사이언스(기본 알고리즘): 동적 계획법과 분할 정복 - 잔재미코딩

 

 

파이썬과 컴퓨터 사이언스(기본 알고리즘): 동적 계획법과 분할 정복 - 잔재미코딩

 

파이썬과 컴퓨터 사이언스(기본 알고리즘): 동적 계획법과 분할 정복 - 잔재미코딩

 

프로그래머스