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