Min9uk's Blog

Chapter 5 해시 테이블 (Hash table) 해시 함수 - 자료구조 해시 테이블을 구현하기 위한 함수 - 문자열(string)을 받으서 숫자를 반환하는 함수 - 문자열에 대해 숫자를 할당(mapping) 해시 테이블 - 해시 함수 + 배열을 결합하여 만듬 - 충돌을 줄이는 해시 함수가있어야한다 - 해시 테이블은 키(key)와 값(value)를 가진다 - 해시 맵(hash maps), 맵(maps), 딕셔너리(dictionaries), 연관 배열(associative arrays) 라는 이름으로도 알려져 있음 - 속도가 빠르다, 평균적인 해시 테이블의 성능은 O(1) 상수시간이다 - 주요 프로그래밍 언어에서 구현되어 있음, 파이썬에는 딕셔너리라고 불리는 해시 테이블이 있다 - 사용률이 0.7보다 커지면 해시 테이블을 리사이징 하는 편 해시 테이블 사용 예 - 데이터 저장과 조회 ex) 전화번호부, 인터넷 주소와 ip주소 - 중복항목 방지 - 데이터 캐시로 사용 (자주 사용되는 정보를 다시 계산하지 않고 저장했다가 사용) Chapter 5 정리 해시 테이블은 빠르고 여러가지로 모형화 할 수 있기 때문에 아주 강력한 자료 구조 이다 해시 테이블의 평균적인 성능은 상수 시간이다 (정말 빠르다) 해시 테이블을 위해서는 잘 짜여진 해시 함수(좋은 분포를 가진)와 사용율에 따른 리사이징이 필요하다 다양한 프로그래밍 언어에서 구현되어 지원한다 다양한 용도로 사용되고 있다 SHA 라는 해시 함수를 공부 해보면 좋다

Chapter 4 퀵 정렬 (Quick Sort) 분할 정복 (Divide and conquer) - 분할 : 주어진 문제를 더 작은 크기의 동일한 문제로 분할 - 정복 : 분할된 각각의 작은 문제를 재귀적으로 해결 - 결합 : 분할된 문제의 해결책을 합쳐 원래 문제의 해결책을 얻음 장점 - 복잡한 문제를 간단한 문제로 나누어 해결 - 재귀적 구현을 통해 간결하게 구현할 수 있음 - 분할된 문제들을 병렬 처리할 수 있어 성능 향상에 도움 단점 - 재귀 호출에 따른 오버 헤드가 발생 할 수 있음 - 문제를 분할하는 과정에서 분할 비용이 발생할 수 있음 - 분할된 해결책을 합치는 과정에서 결합 비용이 발생할 수 있음 예시 - 퀵 정렬, 합병 정렬, 이진 탐색, 최대 공약수 구하기(유클리드 호체법) 유클리드 호제법 (Euclid's algorithm), 최대 공약수 (Greatest Common Divisor, GCD) - 두 개의 자연수의 최대공약수를 구하는 가장 효율적인 알고리즘 중 하나 - 큰 수를 작은 수로 나눈 나머지를 구함 - 나누는 수를 나머지로 바꾸고 나머지를 새로운 나누는 수로 하여 이전 과정 반복 - 나머지가 0이 되면 마지막으로 나눈 수가 최대공약수가 된다 퀵 정렬 (Quicksort) - 분할 정복 알고리즘의 대표적인 예시로, 평균적으로 매우 빠른 정렬 속도를 자랑하는 정렬 알고리즘 - 최악의 경우 시간 복잡도 O(n^2), 평균 O(n log n) 원리 - 피벗 선택 : 정렬할 배열에서 임의의 값 하나를 피벗(pivot)으로 선택 - 분할 : 피벗을 기준으로 배열을 두 부분으로 나눔(큰 값은 왼쪽, 작은 값은 오른쪽) - 재귀 호출 : 분할된 두 부분에 대해 각각 퀵 정렬을 재귀적으로 호출 - 결합 : 분할된 부분들이 정렬되면 전체 배열이 정렬된 상태가 됨 04_quicksort.py 작성 + 테스트 def quicksort ( array ):     # 기본단계 원소의 개수가 0이나 1이면 이미 정렬되어 있다     if len

  Chapter 3 재귀 (Recursion) 재귀 = 자기 자신을 참조(호출)하는 것 (함수에서 사용 => 재귀 함수) - 재귀 함수는 자기 자신을 호출하기 때문에 실수를 무한 반복하는 함수를 만들기 쉽다 - 기본 단계(base case) : 함수가 자기 자신을 다시 호출 하지 않는 경우, 무한 반복을 막는 부분 - 재귀 단계(recursion case) : 자기 자신을 호출하는 부분 - 재귀 함수는 기본단계와 재귀 단계 두 부분으로 나누어 작성 - 대표적 예로 팩토리얼이나 피보나치 수열 구현에 사용하는 예시가 있음 장점 - 복잡한 문제를 간결하게 표현 - 수학적인 문제 해결에 유용 단점 - 성능 저하 : 과도한 재귀 호출은 스택 오버플로우를 발생 시켜 프로그램이 비 정상적으로 종료 될 수 있음 - 로직이 잘못된 경우 무한루프에 빠질 수 있음 - 이해하기 어려울 수 있음 스택(Stack)과 호출 스택 (Call Stack) 스택 - 자료구조의 한 종류 - 후입선출 (LIFO Last In First Out), 가장 나중에 추가된 데이터가 가장 먼저 제거되는 구조 - 푸시(Push) : 삽입, 가장 위에 새로운 요소를 추가 - 팝(Pop) : 삭제, 가장 위에 있는 요소를 제거하고 반환 - 피크(Peek) 또는 톱(Top) : 맨위 데이터 조회, 가장 위에있는 요소를 제거하지 않고 반환 - 비어있는지 확인 (IsEmpty) : 스택이 비어있는지 확인 장점 - 간단한 구현, 후입선출(LIFO)의 특성, 재귀적 문제 해결 단점 - 랜덤 엑세스 불가능, 제한된 용도, 오버플로우나 오버헤드가 발생 할 수 있음 사용 예 - 브라우저의 뒤로 가기, Undo 기능, 재귀함수, 괄호 검사(괄호 짝) 호출 스택 - 프로그램에서 실행 중인 함수들의 정보(지역 변수, 매개 변수 등)를 저장하는 스택 - 여러 함수가 서로 호출하며 복잡한 작업을 수행하는데, 호출 스택으로 이를 관리, 제어 - 스택의 LIFO 형태로 인해 함수가 호출 될때 Push 하고, 실행이 완료 되면 P

  Chapter 2 선택 정렬 배열(array)과 연결 리스트(linked list) - 자료구조(Data structure)의 기본 - 메모리에 데이터가 어떻게 저장되는 지 미리 알아야 한다 - 데이터 저장을 위해서는 메모리의 주소를 할당 받고 나서 데이터가 저장됨 - 데이터 접근에는 임의 접근과 순차 접근이라는 두 가지 방식이 있다 (Random access, Sequential access) 배열 - 미리 원소의 갯수 만큼(초기화 단계에서) 메모리 주소를 할당 받고 원소를 각각의 주소에 저장하는 방식 - 인덱스(index)로 원소의 위치를 표시, 0부터 시작 - 읽기 O(1) 고정시간, 삽입 O(n) 선형시간, 삭제 O(n) 선형시간 - 임의 접근이 많은 경우 유리함 - 간단하고 빠른 데이터 접근이 가능하지만, 유연성이 부족하고 데이터 삽입/삭제에 비효율 적일 수 있음 - 배열의 모든 원소는 같은 자료형이여야 함 장점 - 미리 원소의 갯수를 알고 있을 때 유리 - 임의 접근에 유리하여(인덱스를 통한 빠른 접근) 특정 원소에 접근할 때 유리 (읽기) - 고정된 크기만큼 연속된 메모리 공간을 할당하여 사용되기 때문에 캐시 친화적이다 - 구현이 간단하며 대부분의 프로그래밍 언어에서 지원함 단점 - 원소를 추가하거나 삭제할 때 미리 할당 된 주소를 전부 옮겨야 하는 경우가 발생할 수 있음 - 따라서 처음 설정한 크기에서 원소를 추가/삭제하는 경우 불리함 (삽입, 삭제) - 실제 사용하는 데이터보다 더 큰 크기를 할당할 경우 메모리가 낭비 될 수 있음 활용 - 정렬된 데이터 저장 : 정렬된 데이터를 빠르게 검색해야 할 때 유리 - 행렬 연산 : 행렬을 표현하고 연산하는 데 사용 - 캐시 : CPU캐시는 배열과 유사한 구조로 작동하여 데이터에 빠르게 접근 - 단순한 데이터 목록 : 정적이거나 크기가 미리 예측 가능한 데이터 목록을 저장하는데 적합 연결 리스트 - 각 원소에서 그 다음 원소의 메모리 주소를 포인터로 연결되어 있는 방식 - 연속적인 메모리 공간을 차지

Chapter 1 알고리즘의 소개 이진 탐색 - 정렬이 되어있는 원소 리스트가 필요 - 원소리스트의 중간 값으로 원소리스트의 절반씩 탐색 범위를 좁혀 가는 방법 - 이진 탐색은 크기가 n 인 리스트를 확인하기 위해 log n 번의 연산이 필요 - 빅오 표기법 O(log n) 코드 실행을 위해 Visual Studio Code + Anaconda 설치 01_binary_search.py 작성 테스트 def binary_search ( list , item ):     low = 0     high = len ( list ) - 1     loopCnt = 0     while low <= high :         loopCnt = loopCnt + 1         mid = ( low + high ) // 2         guess = list [ mid ]         if guess == item :             print ( f "LoopCnt : { loopCnt } " )             return mid         if guess > item :             high = mid - 1         else :             low = mid + 1     print ( f "LoopCnt : { loopCnt } " )     return None     my_list = [ 1 , 3 , 5 , 7 , 9 ] print ( binary_search ( my_list , 3 )) # => 1 print ( binary_search ( my_list , - 1 )) # => None 빅오 표기법 주요 5개 속도 순서 (빠름 -> 느림) - O(log n) => 로그시간, 이진 탐색 - O(n) => 선형시간, 단순 탐색 - O(n * log n) => 퀵정렬