WIL#3

5/23~5/28
keyword: 힙 정렬 이진탐색

알고리즘 학습 3주차
학습 언어: 파이썬

1. 힙 : [자료구조]
   -완전 이진트리의 일종으로 우선 순위 큐를 위하여 만들어진 자료구조.
   여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조

• 힙 트리에서는 중복된 값을 허용한다 (이진 탐색트리에서는 허용x)
  -힙의 종류 :
  최대 힙
  -부모 노드의 키값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
  최소 힙
  -부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리

• 구현 방법
  -배열로 구현
  -구현하기 쉽게 하기 위하여 첫번째 인덱스인 0은 사용하지 않는다
  (왼쪽 자식의 인덱스 =부모 인덱스2,오른쪽 자식의 인덱스 = 부모2+1)

2. 정렬(버블, 선택, 삽입, 병합) :
   -버블 : 0번째~끝까지 비교 후 정렬
   -선택 : 선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다.
   -삽입 : 두번째 자료부터 시작하여, 앞의 자료들과 비교하여 삽입할 위치를 지정한 후, 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘
   -병합 : 분할 정복 알고리즘으로, 2개의 문제로 분리하고 각각 해결한 다음, 모아서 원래의 문제를 해결하는 전략.
   리스트를 균등한 크기로 분할하고, 분할된 부분 리스트를 정렬한 다음, 두개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법

• 데이터의 크기가 큰 경우에는 이동 횟수가 많으므로 시간이 오래 걸림
• 데이터의 분포에 영향을 덜 받는다
• 연결 리스트로 구성하면 링크 인덱스만 변경되므로, 데이터의 이동은 무시할 수 있을정도로 작아진다.

3. 이진탐색 :
   데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘.

• 일상 생활에서 흔하게 사용하는 방법으로, 반을 나눠서 찾는값과 비교해보고
  작으면 비교하지 않은 앞의 값을 범위로 또 반을 나눠서 비교하는 식으로 탐색하는 방법이다.
  이진 탐색의 시간 복잡도는 O(logN)이며, 효율적인 탐색 알고리즘이다.