자료구조와 함께 배우는 알고리즘 입문 2

====================06-7 병합 정렬================================

1) 정렬을 마친 두 배열의 병합 과정을 살펴 보자 -배열의 정렬이 끝난 상태에서 어떻게 합칠 것인가를 보는거

변수 필요한거
- 커서 : pa, pb, pc ==> 배열 위를 움직이며 주목해주는 역할
- 배열크기 : na, nb, nc => 커서 움직이는 범위를 결정하기 위해서이다
필요한 기능
- 커서 이용해서 크기 비교한 후 더 작은 값을 병합용 배열 C에 값을 넣기
방법
- 커서를 전부 0으로 초기화
- 배열 a b c를 인수로 받고 길이 구하기
- while pa < na And pb < nb 안에 if문 넣어서 크기 비교하면서 배열 c에 값을 넣어주면 된다.

2) 진짜 병합 정렬(merger sort)를 만들자

변수 필요한거
- 배열 맨 왼쪽 : left
- 배열 맨 오른쪽 : right
- 배열 쪼갤 때 기준이 되는 중간 : center = (left + right) // 2
- 작업용 버퍼(위에서 치면 b 역할을 하는 버퍼) => a에서 앞쪽 반을 잘라서 만듬
- p,j == 작업용 버퍼의 맨 앞(index 0인 곳)을 가리키는 용도
- i == 병합하기 전 a의 index, k == 병합하는 a를 가리키는 용도(병합하는 a는 위에서 C 같은 역할이다)
함수 기능
- buff와 병합 전 a를 비교해서 작은 것을 a에 넣어서 병합한다
방법
- 함수를 재귀적으로 호출한다
- 변수 개수를 통일시키기 위해 가장 밖에있는 함수는 인자를 1개만 받고 함수안에 함수(내부함수)는 재귀용 함수(인자 여러개 받는거)를 또 써준다.
- 분할 정복(dividen and conquer)는 재귀호출을 사용하여 구현할 수 있다.

====================09-1 트리 구조==================================

-> 전위 순회(preorder) : 노드 방문 -> 왼쪽 자식 -> 오른쪽 자식 -> 중위 순회(inorder) : 왼쪽 자식 -> 노드 방문 -> 오른쪽 자식 -> 후위 순위(postorder) : 왼쪽 자식 -> 오른쪽 자식 -> 노드 방문

========================09-02 이진 트리와 이진 검색 트리=========================

분류 -> 이진트리{ (완전 이진트리), [이진 검색 트리(균형 검색 트리)] }
이진 트리의 특징은 왼쪽 자식과 오른쪽 자식을 구분한다는 점
완전 이진 트리는 1) 마지막 레벨 제외 모든 레벨에 노드가 가득 차 있다. 2)마지막 레벨에 한해서 왼쪽->오른쪽으로 노드를 채우되 반드시 끝까지 채우지 않아도 된다.
이진 검색 트리 : 키값이 같은 노드는 복수로 존재하지 않는다.
이진 검색 트리 구현

노드에서 필요한 변수 1) key : 이게 배열에서의 index 역할 2) value : 노드에 저장하는 실제 값 3) left : 왼쪽 자식 노드에 대한 참조 4) right : 오른쪽 자식 노드에 대한 참조
구현되는 함수

– serach 함수 1) p : 노드 사이를 돌아다니는 역할. p는 내가 지금 보고 있는 노드의 정보를 가지고 있는 역할이다.

– add 함수 => 검색하고 더하는 역할 1) node : p랑 같은 역할. 노드 사이를 돌아다니면서 지금 보고 있는 노드의 정보를 가지고 있다. 트리가 빈 상태가 아닐시 self.root로 root가 들어간다 2) 경우의 수는 5가지가 있다.

– remove 함수 => 검색하고 없애는 역할 1) 경우의 수 5가지 2) p : 돌아다니는 역할. 스캔 중인 노드 3) parent : 스캔 중인 노드의 부모 노드

– dump 함수

– min, max 함수.

Share this post