자료구조에는 physical 한 것(실제 하드웨어 적용하는 것)과 logical(physical을 이용해서 구현하는 것)한 것 2가지로 나눌 수 있다.

physical 한 것에는 : Array와 linked list가 있고

logical 한 것에는 : stack, queue, list, tree, graph…등이 있다.

• 06-9 도수 정렬

1. 원소의 대소 관계를 판단하지 않는다. 분포수 세기(distribution counting) 정렬이라고도 한다.
2. 도수는 각 등급(=점수, 성적 등)에 속하는 자료의 개수이다
3. 만드는 순서 1) 도수 분포표 만들기(점수가 있는 원래 배열 A가 있고 index와 점수가 일치하는 도수분포용 배열 F가 있다.)
   • F의 index가 곧 A에서의 점수를 뜻한다. 2) F가지고 F를 누적 도수 분포표로 만든다. 3) 작업용 배열 b를 만든다.
   • 작업용 배열은 배열 a와 원소 수가 같다(여기에 정렬할꺼니까)
   • 배열 a의 원소를 맨 끝에서 맨 앞으로 스캔하면서 배열 F와 대조한다.
   • 원래 배열에서 a의 값을 F의 인덱스로 넣어주고. F인덱스에 해당하는 값을 하나 뺀다. 그리고 그 뺀 값을 b의 인덱스로 삼는다. b의 인덱스에는 배열 a의 원래 값을 넣어준다
4. 도수 정렬은 if 문 없이 for문만 반복해서 정렬할 수 있는 알고리즘

• 06-8 힙 정렬

1. 힙은 일정한 부모-자식 대소관계(부모 >= 자식 or 부모 <= 자식)을 만족하는 완전 이진 트리이다.
2. 힙에서 부모-자식 관계는 일정하지만 형제 사이의 대소 관계는 일정하지 않다.(오른쪽 노드가 왼쪽 노드가보다 꼭 클 필요가 없다는 뜻
3. 힙의 원소를 배열에 저장 할 때는 너비 우선 검색으로 저장한다.
4. 너비 우선 검색으로 저장하면 배열에서 다음과 같은 관계가 만족된다.
   • 배열의 원소 a[i]가 있다면
   • a[i]의 부모는 a[(i - 1) // 2]
   • a[i]의 왼쪽 자식은 a[i * 2 + 1]
   • a[i]의 오른쪽 자식은 a[i * 2 + 2] 이다.
5. 힙 정렬(heap sort)는 힙에서 최대값은 루트에 위치한다는 특징을 이용하여 정렬하는 알고리즘이다.
6. 힙 정렬 할 때 필요한 개념 6-1. 루트를 삭제한 힙의 재구성
   • 내가 이동시킬 원소 빼고는 나머지 원소들은 이미 힙 상태라는 것이 가정
   • 이동시킬 값의 왼쪽 자식, 오른쪽 자식을 비교해서 더 큰 값을 child에 저장
   • 이동시킬 원소 >= 이동시킬 원소의 자식 값 관계가 성립하지 않으면 두 값을 교체

• 6-2. 힙 정렬 알고리즘 보기
• 배열이 이미 힙 상태임을 가정한다.
• 루트가 최대 값이기 때문에 루트와 배열의 마지막 index에 있는 값을 교환한다
• 배열에서 힙이 깨졌으므로 다시 배열을 힙으로 만든다

• 위 과정을 반복한다

• 6-3. 배열을 힙으로 만들기
• 가장 아랫부분의 작은 서브트리부터 상향식(bottom-up)으로 진행해서 전체 배열을 힙으로 만든다. 오른쪽 -> 왼쪽 -> 오른쪽 이렇게

===> 함수를 짤 때 외부함수(인수 1개인거) 내부함수(인수 여러개인거) 이런식으로 짜는 것 같다.

7장 문자열 검색

• text(검색되는 쪽의 문자열)에서 pattern(찾아내는 문자열)을 찾는 것이 핵심

1. 브루트 포스법 => 계속 한 칸씩 밀어가면서 비교하는거
2. KMP법 ==> table 만드는데 실제적으로는 잘 쓰이지 않는 방법
3. 보이어-무어법 ==> pattern의 끝문자에서 시작해서 앞쪽을 향해 검사 수행. 미리 표를 준비한다.