자료구조 알고리즘 목차/링크(algorithm toc & link)

1.기본 지식

최대 공약수(Greatest Common Divisor:GCD)

- 두 정수의 약수 중에서 가장 큰 공통의 약수(나누어 지는 수)
- 유클리드 호제법 (GCD 구하기)

최소 공배수 계산

- 두 정수 A,B 일때 A=GCD*a, B=GCD*b (a,b는 서로소)
- A*B = (GCD*GCD)*a*b, A*B/GCD = GCD*a*b (최소 공배수)

소수 구하기

- 2 ~ sqrt(N) 까지 정수로 나누어 보는 방법(에라토스테네스의 체 (Optimized Sieve of Erathosthenes))
- 기타 방법들 정리 : http://soyoja.com/160

미로 탐색

- Right hand on wall 오른손을 미로 벽에 대고 움직임
- 저장된 좌표리스트에서 중복되는 좌표 부분 잘라냄

재귀 호출

- 피보나치 수열(재귀) : Fn = Fn-1 + Fn-2, F1 = F2 = 1
- 하노이의 탑
- Flood Fill : 그래픽에서 색칠하기
- Fractal Tree : 일정패턴으로 반복으로 나무 모양 그리기
- 파일 찾기 : 파일을 찾기 시작하는데 서브 폴더 모두 뒤지기

서로소 집합(disjoint-sets)

해쉬(Hash)

2.자료구조

배열

-배열 : 연속된 메모리 공간
-C언어 2차원 배열 구조
-델타를 이용한 2차 배열 탐색

문자열 조작

스택

큐

트리

이진 트리

- 트리중에 자식이 2개 이하 가짐
- 용도 : 정렬, 검색 등에 사용됨

이진 탐색 트리

트리 순회

- stack 기반 : pre-order (+AB), post-order (AB+), in-order (A+B)
- queue 기반 : level-order (위에서 아래로, 좌에서 우로)

그래프

 - 구현방법 : 인접 행렬법, 인접 리스트법
    인접 행렬법 : 선이 있는 경우 행렬의 [i, j] = [j, i] = 1 로 설정
    인접 리스트법 : 선이 있는 경우 배열에 자식과 자신을 저장한다.
 -  탐색법 : 깊이 우선(DFS), 너비 우선(BFS)

최소 신장 트리

모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리
-프림(Greedy)
-크루스칼(Greedy)

그래프 최단 경로

-다익스트라(Greedy)
-플로이드 워샬

3.알고리즘

정렬

-버블 정렬
-선택 정렬
-삽입 정렬
-카운팅 정렬
-힙 정렬
-합병 정렬
-퀵 정렬

완전 검색(Brute-force)

-순열(loop)
 서로 다른 n개 중 r 뽑아 나열하는 것(순서가 있음)
 nPr = n*(n-1)*(n-2)*(n-r+1), 5P2 = 5*4
 생성 방법 loop, 재귀
-부분집합(power set)
 집합에 포함된 원소를 선택하는 것
 생성 방법 binary counting, 재귀
 또 다른 방법
 동전 거스름돈 탐색, 전체 탐색
 예) knapsack(Brute-force)
-조합
 서로 다른 n개 중 r개를 순서없이 골라 내는 것
 nCr = n!/((n-r!)*r!), nCr = n-1Cr-1+n-1Cr, nC0 = 1
 생성 방법 재귀
-외판원 문제(TSP)

탐욕(Greedy)

-허프만 트리

분할

-병합 정렬(Merge sort)
-퀵정렬(Quick sort)
-이진 탐색(Binary search)

백트랙킹(Back tracking)

-N-Queens 문제

동적 프로그래밍(Dynamic Programming)

-부분집합(DP)
-동전 거스름돈 문제
-피보나치 수열(DP)
-배낭 문제(Knapsack)(DP)

참고 사이트

http://ddmix.blogspot.kr/2014/11/cppalgo-1-introduction.html