Algorithm Study Repo.
- computer algorithm은 주어진 문제를 효율적으로 풀기 위한 방법을 단겨별로 기술해 놓은 것
- 기본적인 연산능력만 가지고 있다면 누구나 문제를 해결할 수 있도록 명확하게 기술되어야 함
- 문제 정의
- 알고리즘 설명
- 정확성 증명
- 성능 분석
-
탐색
- 선형 탐색(Liner Search) : 맨 앞부터 순서대로 찾음 Linear search wikipedia link
- 이진 탐색(Binary Search) : 범위를 절반씩 추려가면서 찾음 Binary search algorithm wikipedia link
- Hash 탐색 : 계산해서 저장 위치를 찾음 Hash function wikipedia link
-
정렬
- 단순 정렬법(선택 Sort) : maximum(minimum)을 선택해서 앞부터 순서대로 나열함 Selection Sort
- 단순 교환법(Bubble Sort) : 옆에 있는 Data를 교환하면서 자리를 바꿔 나열함
- 단순 삽입(Insert Sort) : 데이터를 올바른 위치에 삽입하면서 자리를 바꿔 나열
- Quart Sort : 기분 데이터를 기반으로 대소 분할을 반복하여 자리를 바꿔 나열
- Merge Sort : 이분할과 머지를 이용하여 자리를 바꿔 나열
- Heap Sort : Heap이라는 Data 구조를 이용하여 자리를 바꿔 나열
- 셸 정렬 : Group을 나누면서 자리를 바꿔 나열
-
수치 계산(수치 해석)
- 에라토스테네스의 체 : 소수를 구하는 알고리즘 Sieve of Eratosthenes wikipedia link
- 유클리드 알고리즘 : 최대 공약수를 구하는 알고리즘 Euclidean algorithm wikipedia link
- 가우스 소거법 : 연립 1차 방정식을 푸는 알고리즘
- 사다리꼴 법칙 : 정적분의 근삿값을 구하기 위한 알고리즘
- 다익스트라 알고리즘 : 그래프에서 최적 경로를 구하는 알고리즘
- 이분법 : 방정식을 푸는 알고리즘
- 뉴턴법(뉴턴 랩슨법) : 방정식을 푸는 알고리즘
-
문자열 탐색
- 무차별 검색법(부루트 포스 검색법) : 맨 압부터 한 문자씩 차례대로 탐색 Brute-force search wikipedia link
- KMP(커누스-모리스-프랫) 알고리즘 : 불일치 부분에 착목하여 탐색 Knuth–Morris–Pratt algorithm
- BM(보이어-무어) 알고리즘 : 부분 문자열의 끝에서부터 탐색 Boyer–Moore string-search algorithm
출처 : '처음 만나는 알고리즘' 이토 시즈카, Jpub