※ Do it! 알고리즘 코딩테스트 c++편 교재와 강의로 공부한 내용을 정리했습니다.1-1. 배열배열은 메모리의 연속 공간에 값이 채워져있는 형태의 자료구조이다.인덱스를 통해 참조할 수 있으며, 선언한 자료형의 값만 저장할 수 있다. 배열의 특징1. 인덱스를 사용하여 값에 바로 접근할 수  있다.2. 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하려면 주변에 있는 값을 이동시켜야한다.3. 배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없다.4. 구조가 간단하므로 코딩 테스트에서 많이 사용한다. 1-2. 리스트 리스트는 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조이다.  리스트의 특징1. 인덱스가 없으므로 값에 접근하려면 Head포인터부터 순서..

※ Do it! 알고리즘 코딩테스트 c++편 교재와 강의로 공부한 내용을 정리했습니다. 코딩 테스트의 핵심 중 하나는 문제마다 주어진 시간복잡도를 고려해 적절한 알고리즘을 선택하는 것이다. 알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다. 일반적으로 1억번의 연산은 1초의 수행 시간으로 예측할 수 있다.  1-1. 시간 복잡도 유형빅-오메가 : best case빅 - 세타 : average case빅 - 오 : worst case 1~100 사이의 무작윗값을 찾아 출력하는 코드에서빅-오메가 표기법의 시간 복잡도는 1번,빅-세타 표기법의 시간 복잡도는 N/2번,빅-오 표기법의 시간 복잡도는 N번 이다. 코딩테스트에서는 빅-오 표기법을 기준으로 수행 시간을 계산하는 것이 좋다.다양..

정렬 (Sorting)정의n개의 요소를 오름차순으로 재배열하는 것입력: 7, 3, 6, 2, 1정렬 후 출력: 1, 2, 3, 6, 7정렬 방법내부 정렬 (Internal Sorting)PQ 기반 정렬 (PQ based sorting)선택 정렬 (Selection sort)삽입 정렬 (Insertion sort)힙 정렬 (Heap sort)외부 정렬 (External Sorting)Priority Queue(PQ)정의우선 순위가 부여된 요소들을 저장하는 추상 데이터 타입으로, 임의의 요소 삽입을 지원하지만 요소 제거는 우선 순위에 따라 이루어진다.특징스택, 큐, 리스트, 트리와 같은 위치 기반 데이터 구조와 근본적으로 다름.기존의 데이터 구조는 요소를 특정 위치에 저장하며, 이는 삽입 및 삭제 방법에 의..

(2,4) 트리에서 레드-블랙 트리로레드-블랙 트리 :노드가 빨간색 또는 검은색으로 색칠된 이진 트리를 통해 (2,4) 트리를 표현(2,4) 트리와 비교 :동일한 로그 시간 성능단순한 구현: 레드-블랙 트리는 단일 노드 타입을 사용하여 더 간단하게 구현 가능레드-블랙 트리 정의루트 속성(Root Property): 루트는 검은색외부 속성(External Property): 모든 잎(리프)은 검은색내부 속성(Internal Property): 빨간색 노드의 자식은 모두 검은색깊이 속성(Depth Property): 리프 노드의 black depth는 모두 같다레드-블랙 트리의 높이정리: n개의 항목을 저장하는 레드-블랙 트리는 높이는 O(log n)증명:레드-블랙 트리의 높이는 (2,4) 트리의 높이의 최..

multi-way search treebinarySearch Tree의 relationial특성은 같지만 구조적 특성은 다르다binary ≠ multi-way각 내부노드는 최소 2개 child 가져야함(2,4) Trees(2-3-4tree)다음 속성을 만족하는 multi-way 트리모든 내부 노드가 child를 2,3,4개만 갖는 트리깊이 속성 (Depth Property): 모든 외부 노드는 같은 깊이에 있음Searching in a (2,4) tree with n items takes O(log n) time삽입(Insertion)키 k를 탐색하여 도달한 잎 노드의 부모 노드 v에 새로운 항목 (k, o)를 삽입합니다.삽입 전후에도 깊이 속성을 유지합니다. 즉, 모든 외부 노드는 같은 깊이에 있어야 ..

AVL 트리 (AVL Tree)균형 속성 (Height Balance Property)AVL 트리는 균형 이진 검색 트리입니다.높이 균형 속성을 만족합니다:트리 T의 모든 내부 노드 v에 대해, v의 자식 노드들의 높이 차이는 최대 1입니다.AVL 트리의 높이사실: n개의 키를 저장하는 AVL 트리의 높이는 O(log n)증명: AVL 트리의 높이 h에 따른 최소 내부 노드 수 n(h)를 제한합니다.기본 사례n(1) = 1n(2) = 2일반적인 경우n > 2인 경우, 높이가 h인 AVL 트리는 루트 노드와 높이가 h-1인 AVL 서브트리와 높이가 h-2인 AVL 서브트리로 구성됩니다.따라서, n(h) = 1 + n(h-1) + n(h-2)대소관계n(h-1) > n(h-2) 이므로, n(h) > 2n(h-..

연산자firstEntry() : 값이 null인 가장 작은 키 엔트리lastEntry() 가장 키 값이 큰 엔트리floorEnrty(k) 키 ≤ k 인 가장 큰 엔트리ceilingEntry(k) 키 ≥ k 인 가장 작은 엔트리맵이 비어있으면 null 리턴Binary Search이진 검색은 key로 정렬된 배열 기반 순차열로 구현된 정렬된 맵에서 get, floorEntry 및 ceilingEntry 연산을 수행각 단계에서 후보 항목의 수가 절반으로 감소O(log n)get floorEntry ceilingEntry O(log n)putO(n)removeO(n)Binary Search Trees (ADT)구조적 특성 : 이진 트리관계적 특성내부 노드에 키(또는 키-값 항목)를 저장하는 이진 트리u, v, ..

Selection / Insertions Sort의 문제점1단계 : 입력 set에서 큐 구축2단계 : 우선순위 큐 구축Selection sort: Phase 1은 빠르지만 Phase 2는 매우 느리다.Insertion sort: Phase 1은 매우 느리지만 Phase 2는 빠르다.How can we balance the running times of the two phases?:효율적인 우선순위 큐의 구현은 heap이라는 데이터 구조를 사용Heap Data StructuresHeap(힙): 이진 트리 T는 관계적 속성과 구조적 속성을 만힙 순서 속성(Heap-order Property): 힙 T에서 루트가 아닌 모든 노드 v에 대해, v에 저장된 키는 v의 부모에 저장된 키보다 크거나 같다.완전 이진 ..

우선순위 큐정의우선순위가 지정된 요소들의 컬렉션을 저장하는 추상 데이터 타입임의의 요소 삽입을 지원하며,우선순위 순서에 따라 요소 제거 가능특징위치 기반 데이터 구조와는 다름이전 데이터 구조들은 요소를 특정 위치에 저장우선순위 큐는 우선순위에 따라 저장위치는 노출하지 않음첫번째 우선순위를 가진 요소는 언제든지 제거 가능용어키(Key)특정 요소에 지정된 속성요소를 식별하거나 가중치를 부여하는 데 사용고유하지 않아도 됨변경 가능엔트리(Entry)우선순위 큐에 저장되는 요소와해당 키의Total Order Relations 전체 순서 관계우선 순위 큐의 키들은 정렬이 정의된 임의의 객체가 될 수 있다키가 동일한 엔트리 두 개가 존재할 수 있다.Total Order Relations의 조건Reflexive pro..