반응형 개발4 우선순위 큐와 힙은 뭘까? 23.1 도입 우선순위 큐 선입선출이 아니고, 우선순위가 가장 높은 자료가 가장 먼저 꺼내진다. 연결 리스트나 동적 배열로 구현 가능하다 O(n) 시간 소요되며 비효율적이다. 힙을 통해 구현하는 것이 가장 적합하다. 힙 가장 큰 또는 가장 작은 원소를 찾는데 최적화된 형태의 이진 트리 O(lgN) 시간 소요 23.2 힙의 정의와 구현 특정한 규칙을 만족하는 이진 트리 대소 관계 규칙: 부모 노드가 가진 원소는 항상 자식 노드가 가진 원소 이상이다. 힙의 모양 규칙 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다. 마지막 레벨에 노드가 있을 때는 항상 왼쪽부터 순서대로 채워져 있어야 한다. 배열을 이용한 힙의 구현 트리에 포함된 노드의 개수만 알면 트리 전체의 구조를 알 수 있다. 배열을 제일.. 2024. 4. 17. 이진 검색 트리는 뭘까? 22.1 도입 일정한 순서에 따라 정렬한 상태로 저장해준 검색 트리 32비트 정수들을 작은 것부터 큰 것까지 정렬한 상태로 저장할 수도 있고, 문자열을 가나다순으로 정렬해서 저장할 수도 있다. 원소의 추가와 삭제만이 아니라 특정 원소의 존재 여부 확인 등을 할 수 있다. 대부분 표준 라이브러리에서 제공한다. 22.2 이진 검색 트리의 정의와 조작 이진 트리? 각 노드가 왼쪽과 오른쪽, 최대 두 개의 자식 노드만을 가질 수 있는 트리 자식 노드의 배열 대신 두 개의 포인터 left와 right를 담는 객체로 구현된다. 위의 트리는 왼쪽은 루트보다 작은 값, 오른쪽은 루트보다 큰 값으로 이뤄진 트리이다. 그러나 잘못된 예처럼 루트인 16보다 작은 원소인 15가 루트보다 작은 값으로 올 수는 없다. 순회 크기.. 2024. 4. 17. 트리의 구현과 순회는 뭘까? 21.1 도입 계층적 구조의 자료 구조 연결된 두 노드 중 상위에 있는 것이 부모 노드 , 하위는 자식 노드 부모 노드가 같은 두 노드는 형제 노드 부모 노드와 그의 부모들을 통틀어 선조 노드 자식 노드와 그의 자식들을 통틀어 자손 노드 모든 노드의 선조이고, 부모이면 뿌리 노드 , 루트(root) 자식이 하나도 없는 노드는 잎 노드 , 리프(leaf) 트리와 노드 속성 깊이 : 루트에서 어떤 노드까지 도달하기 위해 거쳐야하는 간선의 수 높이 : 트리에서 가장 깊숙히 있는 노드의 깊이 트리의 재귀적 속성 가장 유용하게 쓰이는 이유는 재귀적 속성때문이다. [상위-하위 개념으로 연결된 트리 구조] 에서 ‘탐색형 자료구조(=t)’에서 그 자손들로 구성된 트리를 ‘t’를 루트로 하는 서브트리 라고 한다. 모든 .. 2024. 4. 17. 선형 자료 구조는 뭘까? 18.2 동적 배열 배열을 이용해 만들어낸 별도의 자료 구조이기 때문에 배열의 특징을 그대로 받는다. 원소들은 메모리의 연속된 위치에 저장된다. 캐시의 효율성과 직결되어 중요한 포인트 주어진 위치의 원소를 반환하거나 변경하는 동작을 O(1)에 할 수 있다. O(1)? 시간복잡도 개념에서 상수를 의미한다. 입력에 관계없이 복잡도가 동일하게 유지된다. 동적 배열만의 특징은 아래와 같다. 배열의 크기를 변경하는 resize() 연산이 가능하다. 이 동작을 수행하는 데는 배열의 크기 N에 비례하는 시간이 걸린다. 주어진 원소의 배열의 맨 끝에 추가함으로써 크기를 1 늘리는 append() 연산을 지원한다. 이 동작을 수행하는 데는 상수 시간이 걸린다. 동적 배열의 크기가 바뀌는 과정은 아래와 같다. 새 배열을 .. 2024. 4. 17. 이전 1 다음 728x90 반응형
