1. 버블 정렬인접한 원소를 비교한 다음, 내가 원하는 정렬이 아니다! 하면 교환.처음부터 마지막까지 쌍 비교.이렇게.. n-1개의 쌍을 비교하면, 가장 큰 애는 가장 끝으로 이동하게 됨.그 후, n-2개의 쌍(젤 큰 애는 비교 안 함. 이미 제자리임.)을 비교하면, 두 번째로 큰 애가 가장 큰 애의 옆으로 위치하게 됨.즉, (n-1)+(n-2)+...+(1) = n(n-1)/2 번 비교. 2. 선택 정렬우선, 주어진 배열에서 최댓값 찾아서 맨 뒤로 보냄.최댓값 뺀 나머지 배열에서 최댓값 찾아서 맨 뒤에서 한 칸 앞으로 보냄.이런 식으로 진행되는 건데, 계속 교체하진 않으므로 버블 정렬보단 효율적. 3. 삽입 정렬얘는 우선 1번째 원소부터 비교를 시작한다.0번째 원소와 비교해서, 1번째 원소의 위치를 정..
전체 글
히프보통 힙(최대힙) : 리프-루트 경로를 따르는 모든 키가 오름차순으로 되어있는 완전 이진 트리어떤 키도 부모보다 크지 않음. * 최소힙 : 부모키가 자식키보다 작 히프화 연산히프 특성 만족하도록 시퀀스 원소들 재배열하는 것.리프-루트 경로 따라 인접한 두 개 이상의 원소를 회전 우선순위 큐원소의 우선순위에 삭제 연산이 수행되는 큐어떤 것이 높은 우선순위를 가지는지 결정하기 위해 원소들 간의 비교가 가능하다는 것을 가정하고 있음.일반적 큐 : 선입선출(FIFO), 우선순위 큐 : 최적입선출(BIFO)어떤 것을 먼저 넣느냐가 중요한 게 아니라, 그냥 우선순위인 것이 먼저 나감.따라서 힙을 이용하는 것이 편함! 즉, 연산이 어떻게 진행되냐면,삽입 : 주어진 원소를 넣으면, 트리의 말단에 넣어짐. 여기서 히..
오늘은.. 자료구조.. 총정리 완료..이전 내용에 빠진 것들도 추가하고, 새롭게 탐색트리 글도 작성함.사실 완벽하게 완료는 아니지만.. 이제 불가능..집에 가겠습니다..2024.06.08 - [자료구조(java)] - 탐색 트리
Binary Search Tree각각의 노드가 BST 특성을 만족하는 키-주소 쌍을 가진 이진 트리각 키에 대해,왼쪽 서브트리의 모든 키는 이보다 작고,오른쪽 서브트리의 모든 키는 이보다 크다.모든 요소는 키를 가지고 있는데, 이 키는 유일하다.만약, 이 BST를 중위순회(왼-루트-오)한다면 오름차순 방문하는 것. BST 검색(삽입)검색 : 만일 BST가 공백이면 null 반환. 삽입 : 만일 BST가 공백이면 단독 트리 만들고 true 반환 검색(삽입)하려는 key가 root.key보다 작으면 왼쪽 서브트리 순환 탐색, 아니면 오른쪽 서브트리 순환 탐색 해서 검색이면 그 값을 찾고,삽입이면 들어갈 자리를 찾음 검색 : 값 없으면 false 반환삽입 : 이미 BST에 있는 키면 false 반환 * BS..
조금 늦었지만.. 지난 6월 5일에 대한 TIL을 올려본다. 자료구조 공부를 하며 트리와 이진트리에 대해 공부를 하여 포스팅하였다.2024.06.05 - [자료구조(java)] - 트리2024.06.06 - [자료구조(java)] - 이진트리
이진트리란?공집합이거나, x가 루트이고 L/R 중 어느것도 x를 포함하지 않는 분리된 이진트리일 때, 삼원소 쌍(x, L, R)두 서브트리 L/R이 "왼쪽"과 "오른쪽"이라는 이름으로 구분이진트리의 모든 공백이 아닌 노드는 반드시 왼쪽 서브트리와 오른쪽 서브트리를 가져야 함.서브트리는 모두 공백 가능특성포화 이진트리 크기 = 2^(h+1) - 1이진트리 크기 범위 : h+1 이진트리 높이 : floor(lg(n)) 크기가 2인 2개의 이진 트리 : 노드 2개로 나타낼 수 있는 두가지크기 3인 5개 이진트리카탈로니아 수 : 이진 트리 개수 세는 데 사용되는 폐쇄형 공식 (2n)!/n!(n+1)! 수식 트리수식트리 표현법!수식트리를 표현한 후, 이 수식트리를..
트리란?공집합이거나 r이 노드이고, S가 서로 분리된 트리의 집합일 때, 어떤 트리도 r을 포함하지 않는 쌍 (r, S) 이다.노드 r : 트리의 루트 degree : subtree 집합의 크기. 즉, 자식노드 개수. degree가 0인 노드 == leaf node루트경로 : 루트로부터 해당 노드까지 유일한 경로루트-리프경로 : 루트에서 리프에 이르는 경로경로의 길이 : 부모자식 쌍의 개수. 즉, 노드개수 -1트리 경로길이 : 모든 노드의 깊이의 합공백트리 : 유일하게 크기 0인 트리단독트리 : 크기가 1인트리트리 높이 : 최장 루트경로 길이노드 깊이 : 노드까지의 루트경로 길이트리 너비 : 최대 레벨 크기레벨 : 주어진 깊이에서의 모든 노드노드 차수 : 자식들 개수트리 차수 : 최대 노드 차수포화 트리..
이제는. 찐으로. 자료구조를 시작해야할 시간자료구조 정리를 조금 해보았다. 리스트를 공부할 때 필요한 Iterator를 공부하며메소드들의 구조를 이해하면서 Iterator class를 구현해보았다. 해시테이블도 조금 공부하였다. 2024.06.03 - [자료구조(java)] - 리스트2024.06.03 - [자료구조(java)] - Iterator2024.06.03 - [자료구조(java)] - 해시테이블