달력

1

« 2021/1 »

  •  
  •  
  •  
  •  
  •  
  • 1
  • 2
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  •  
  •  
  •  
  •  
  •  
  •  
2017. 5. 1. 12:00

이진 검색(binary search) Development/Algorithm, DataStructure

반응형

 

 

이진 검색(binary search)

·       배열의 검색할 범위를 반복적으로 절반씩 줄여가면서 검색하기 때문에 검색속도가 상당히 빠릅니다.

·       배열의 길이가 많이 늘어나도 검색 횟수는 몇회 밖에 늘어나지 않으므로 큰 배열을 검색할 때 유용합니다.

·       하지만 배열이 정렬이 되어있어야 사용할 수 있습니다.

 

반응형
저작자표시비영리

'Development > Algorithm, DataStructure' 카테고리의 다른 글

Algorithm Visualizer  (0) 2017.05.15
이진 트리(Binary Tree), 이진 트리(Binary Tree)의 코드화  (0) 2017.05.01
이진 검색(binary search)  (0) 2017.05.01
이진 탐색 트리(Binary Search Tree), 이진 트리 구조 도식도, 이진 검색 트리 저장 원리  (0) 2017.05.01
Comparable의 compareTo 구현 사례 -Integer 랩퍼클래스  (0) 2017.04.29
The Sound of Sorting - "Audibilization" and Visualization of Sorting Algorithms - 15 Sorting Algorithms in 6 Minutes  (0) 2017.02.15
Trackback (0) : Comment (0)
Posted by codedragon codedragon

댓글을 달아 주세요

2017. 5. 1. 08:48

이진 탐색 트리(Binary Search Tree), 이진 트리 구조 도식도, 이진 검색 트리 저장 원리 Development/Algorithm, DataStructure

반응형

 

 

이진 탐색 트리(Binary Search Tree)

모든 노드는 최대 두 개의 자식노드를 가질 수 있습니다.

바이너리 서치 트리는 어느 노드에서든 그 노드의 왼쪽 부분 트리의 모든 원소는 그 노드의 값보다 작거나 같고, 오른쪽 부분 트리에는 해당 값보다 큰 값이 저장되어 있습니다.

정렬, 검색, 범위 검색(range search)에 높은 성능을 보여주는 자료구조입니다.

 

 

 

 

8, 5, 20의 순서로 저장된 이진 트리 구조 도식도

간단하게 도식화한 이진 트리 구조


 

실제로 저장되는 이진 트리 구조


 

 

 

 

이진 검색 트리 원리

첫번째로 저장되는 값은 root노드가 됩니다.

두번째 저장되는 값은 트리의 root부터 시작해서 값의 크기를 비교해서 트리를 따라 내려가게 됩니다. 비교해서 작은 값은 왼쪽에 큰 값은 오른쪽에 저장하게 됩니다.

모두 값이 트리에 저장되게되면 가장 왼쪽에 있는 노드는 제일 작은 값을 가지고 가장 오른쪽의 노드는 제일 큰 값을 가지게 됩니다.

 

 

8, 5, 20, 2, 6의 순서로 값 저장하기

8을 트리의 ‘루트’, 즉 맨 위 머리부분으로 배치했습니다. 8의 두 자식 노드는 5와 20이고, 5는 2와 6이라는 두 자식 노드를 갖습니다.

트리에서 루트 노드에는 8의 값이 저장돼 있고, 왼쪽 부분 트리의 모든 값은 5, 2, 6으로 8보다 작고, 20은 8보다 큽니다.

 


 

 

단계

도식도

8 저장


 

5 저장


 

20 저장


 

2 저장


 

6 저장


 

 

 


반응형
저작자표시비영리

'Development > Algorithm, DataStructure' 카테고리의 다른 글

Algorithm Visualizer  (0) 2017.05.15
이진 트리(Binary Tree), 이진 트리(Binary Tree)의 코드화  (0) 2017.05.01
이진 검색(binary search)  (0) 2017.05.01
이진 탐색 트리(Binary Search Tree), 이진 트리 구조 도식도, 이진 검색 트리 저장 원리  (0) 2017.05.01
Comparable의 compareTo 구현 사례 -Integer 랩퍼클래스  (0) 2017.04.29
The Sound of Sorting - "Audibilization" and Visualization of Sorting Algorithms - 15 Sorting Algorithms in 6 Minutes  (0) 2017.02.15
Trackback (0) : Comment (0)
Posted by codedragon codedragon

댓글을 달아 주세요

2017. 4. 29. 09:15

Comparable의 compareTo 구현 사례 -Integer 랩퍼클래스 Development/Algorithm, DataStructure

반응형

 

Comparable의 compareTo 구현 사례 -Integer 랩퍼클래스

 

Integer 클래스의 코드

C:\CodeLab\src\java\lang\Integer.java


 


Comparable의 compareTo(T o)추상메소드를 구현하고 있습니다.

두 Integer객체에 저장된 int값(value)을 비교해서 작으면 -1, 같으면 0, 크면 1을 반환하는 것을 알 수 있습니다.

TreeSet에 Integer인스턴스를 저장했을 때 정렬되는 기준이  compareTo()메소드에 의한 것입니다.

 

반응형
저작자표시비영리

'Development > Algorithm, DataStructure' 카테고리의 다른 글

Algorithm Visualizer  (0) 2017.05.15
이진 트리(Binary Tree), 이진 트리(Binary Tree)의 코드화  (0) 2017.05.01
이진 검색(binary search)  (0) 2017.05.01
이진 탐색 트리(Binary Search Tree), 이진 트리 구조 도식도, 이진 검색 트리 저장 원리  (0) 2017.05.01
Comparable의 compareTo 구현 사례 -Integer 랩퍼클래스  (0) 2017.04.29
The Sound of Sorting - "Audibilization" and Visualization of Sorting Algorithms - 15 Sorting Algorithms in 6 Minutes  (0) 2017.02.15
Trackback (0) : Comment (0)
Posted by codedragon codedragon

댓글을 달아 주세요

2017. 2. 15. 05:52

The Sound of Sorting - "Audibilization" and Visualization of Sorting Algorithms - 15 Sorting Algorithms in 6 Minutes Development/Algorithm, DataStructure

반응형

 

 

The Sound of Sorting - "Audibilization" and Visualization of Sorting Algorithms

http://panthema.net/2013/sound-of-sorting/


 

 

Source code archive

http://panthema.net/2013/sound-of-sorting/sound-of-sorting-0.6.5/src/


https://github.com/bingmann/sound-of-sorting


 

 

 

 

15 Sorting Algorithms in 6 Minutes

https://www.youtube.com/v/kPRA0W1kECg

 


반응형
저작자표시비영리

'Development > Algorithm, DataStructure' 카테고리의 다른 글

Algorithm Visualizer  (0) 2017.05.15
이진 트리(Binary Tree), 이진 트리(Binary Tree)의 코드화  (0) 2017.05.01
이진 검색(binary search)  (0) 2017.05.01
이진 탐색 트리(Binary Search Tree), 이진 트리 구조 도식도, 이진 검색 트리 저장 원리  (0) 2017.05.01
Comparable의 compareTo 구현 사례 -Integer 랩퍼클래스  (0) 2017.04.29
The Sound of Sorting - "Audibilization" and Visualization of Sorting Algorithms - 15 Sorting Algorithms in 6 Minutes  (0) 2017.02.15
Trackback (0) : Comment (0)
Posted by codedragon codedragon

댓글을 달아 주세요

티스토리툴바