일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
- 유니온-파인드
- 외적
- 디자인패턴
- Unreal Collision
- BFS
- Trie
- Abstract Factory pattern
- Union-Find
- 동적 계획법
- 트리
- 정렬 알고리즘
- flyweight pattern
- 스택
- Queue
- 명령패턴
- command pattern
- 두 직선사이 교점
- 비교 기반 정렬 알고리즘
- 깊이 우선 탐색
- 팩토리패턴
- 분포 기반 정렬 알고리즘
- Set
- C++ STL 정리
- 자료구조
- 관찰자(Observer) 패턴
- 경량 패턴
- object channel
- 트리순회
- Factory method pattern
- 생성패턴
- Today
- Total
목록자료구조 & 알고리즘 (2)
KimMK
내부 탐색: 주기억 장치에 모두 적재 후 탐색 순차 이진 이진 트리 해싱 외부 탐색 균형 트리 순차 탐색 첫 번째 레코드부터 시작해서 마지막 레코드까지 차례로 탐색 키를 비교하는 알고리즘 비교 횟수는 성공적이지 않은 탐색에 대해 N + 1회 비교, 성공적인 탐색에는 평균적으로 N/2회 비교 정렬된 연결 리스트로 구현된 순차 탐색은 항상 평균적으로 N/2회 비교 이진 탐색 성공적인 탐색과 그렇지 않은 탐색 모두 logN + 1회 이상의 비교를 하지 않음 리스트가 정렬되어 있어야 하므로 정렬된 상태를 유지하는데 추가적인 비용을 소비함 이진 트리 탐색 작은 키를 가지고 있는 레코드는 왼쪽 부분트리, 같거나 큰 키를 가진 레코드는 오른쪽 부분트리 과정: 루트와 키를 비교하고 키가 루트보다 작다면 왼쪽 서브 트리..
정렬 알고리즘 비교 기반 선택(Selection) 버블(Bubble) 삽입(Insertion) 쉘(Shell) 퀵(Quick) 병합(Merge) 힙(Heap) 분포 기반 계수(Counting) 기수(Radix) 버킷(Bucket) 비교 기반 정렬 알고리즘 선택 정렬 배열에서 가장 작은 원소를 찾아 첫 번째 원소와 교환하고 두 번째 작은 원소를 찾아 두 번째 원소와 교환하는 방식으로 전체를 정렬하는 알고리즘 전체 데이터(N)에 대해서 비교 횟수는 N(N-1)/2가 되고 시간 복잡도는 O(N2)이 되므로 입력 데이터의 수에 따라 시간이 오래 걸리는 알고리즘이고 [1,2’,2]와 같은 입력 배열을 정렬하면 [1,2,2’]와 같이 크기가 같음에도 상대적인 위치가 변경될 수 있다는 단점을 보유 (불안정) 하지만 ..