알고리즘) 복습(26.3.26)

rank,

select

둘다 일치할때 어덯게 처리하던가 [  ]

 

 

(실제문풀)

코드부분

휴리스틱으로 푸는바업ㅂ

 

이해안됨

---

왜 new K[10]처럼 직접 만들 수 없나요?

자바에서 배열은 런타임에 자신의 타입 정보를 유지하지만, 제네릭은 컴파일 타임에만 존재하고 런타임에는 사라집니다(Type Erasure).

왜 new K[10]처럼 직접 만들 수 없나요?

자바에서 배열은 런타임에 자신의 타입 정보를 유지하지만, 제네릭은 컴파일 타임에만 존재하고 런타임에는 사라집니다(Type Erasure).

 

 

 자바의 **배열(Array)**은 생성되는 즉시 그 안의 모든 공간이 **기본값(Default Value)**으로 채워집니다

(그래서 그 과제할때, 배열로 해서 0000이 있엇잖아, 

그래서 리스트로 했던거고 

 

 

floor(Node x, K key)

두번재 매개변수가 헬퍼에서 ㅜ는 매개변수네 

(ㄷ충 헤퍼함수있으면 재귀쓰ㅕ나보다 생각해도 될디도/아니면 min처럼 오버로딩하던가 ) 

 

 

(우리가 궁금해 하는건 )floor(key)는 트리 안에 있는 키들 중 **"매개변수로 받은 key보다 🧡작거나 🧡같은 키들 중에서 가장 큰 키"**를 찾는 것입니다.

• 쉽게 말해: **"key를 안 넘으면서 최대한 가까운 놈"**을 찾는 거죠.
• 반대 개념은 ceiling(천장)입니다. (key보다 크거나 같은 것 중 가장 작은 것)

 

상황 A: key가 현재 노드(x)의 키보다 작을 때 (cmp < 0)

• 현재 노드(x)는 이미 key보다 큽니다. 우리가 찾는 건 key보다 작거나 같은 놈이죠?

 

상황 B: key가 현재 노드(x)의 키보다 클 때 (cmp > 0) 👈 여기가 핵심!

• 현재 노드(x)는 key보다 작습니다. 즉, 일단 floor의 후보가 됩니다!
• 하지만! 현재 노드보다 더 크면서 여전히 key보다 작은 놈이 오른쪽 자식 어딘가에 있을 수도 있습니다.

(그래서 이걸 어떻게 하냐면, 9복잡하니간 재귀로 구성0 

 

• 만약 t가 있다면? (t != null): "오, 오른쪽 동네에서 더 좋은 답을 찾아냈구나! 그게 진짜 답이다. t를 돌려보내자."

 

return 

아 그니깐 자신의 코드는 그내는데 부모로 돌아온다는 의밍니가

f{return a()  return a;} a(){return 2} <2출력만 되나 ㅇㅇ

 

 

t = floor(x.right, key)를 호출했을 때 t가 null로 돌아오는 경우는 크게 두 가지입니다.

1. 진짜로 오른쪽 자식이 없을 때: x.right가 null이면, 다음 방에서 if (x == null) return null;에 걸려 바로 null을 던져줍니다.
2. 오른쪽 동네 녀석들이 "전부 다" key보다 클 때:
   • 오른쪽으로 가서 조사를 시작했는데, 그 동네 대장부터 쫄병까지 전부 다 내가 찾는 key보다 커버리면, 계속 왼쪽(x.left)으로만 파고들다가 결국 막다른 길(null)에 도달하게 됩니다.

 

 

---

compareTo할때

기준은 대부분 key인듯

 

• rank의 정의는 "나보다 작은 키의 수"입니다.(시작이 0부터니깐)
• ()질무했던 이터러블로 구현>인덱스 0부터 시작이니간
• 현재 노드는 나랑 똑같기 때문에, "나보다 작은 놈"에 포함시키면 안 됩니다.

 

 

5보다 왼쪽에 있는 애들은 당연히 10보다 작겠죠? → size(x.left)

아 이건 5의 왼족인거고 

 

5보다 왼쪽에 있는 애들은 당연히 10보다 작겠죠? → size(x.left)

<이건 10의 왼족인가 

즉 10.left한다고 5가 나오는건 아니니간

 

 

 

 

rank,

select

둘다 size인데 뭐 어덯게 다른거지 [  ]

 

rank는 total을 반복문 박에서 선언하고잇네 

select는 닥 그 등수만 봅아오는게 목적이니간 안엣 

(댓ㅣㄴ slect는 매개변수로 받은 등수자체를 변경시키네 )

---

 

 

 

일반적인 이진 검색 트리(BST)는 데이터가 들어오는 순서대로 트리를 만듭니다. 하지만 어떤 단어는 아주 자주 검색되고(예: '네이버'), 어떤 단어는 1년에 한 번 검색될 수도 있습니다.

• 아이디어: "자주 검색되는 단어(값이 큰 단어)를 루트(위쪽)에 배치하면, 전체적인 검색 속도가 빨라지지 않을까?"
• pp
• 목표: 모든 검색의 **평균 비교 횟수(비용)**를 최소로 만드는 트리를 찾는 것입니다.

 

 

 

 

"확률을 안다"는 가정하에

 

a1​,a2​,…,an​

 (키 값): 트리 안에 저장될 단어들입니다. (예: do, for, while...) 항상 가나다순/알파벳순으로 정렬되어 있다고 가정합니다.

 

 

(아무튼 재귀적으로 들어가면 아무튼 해결된다니깐 뭐) 

 

 

 

 

 

---