개발에 도움이 되는/자료구조 & 알고리즘 (11) 썸네일형 리스트형 스택(Stack), 큐(Queue) 스택(Stack)과 큐(Queue) 모두 선형 자료 구조이며, 추상 데이터 타입(ADT)이다. - ADT : 자료 구조의 방법이 코드로 정의 된 것이 아닌 그 구조의 행동 양식만 정의된 것 (일종의 규칙) - 스택 (Stack) LIFO (Last In First Out) 즉, 나중에 들어간 원소가 먼저 나온다. - 사용 사례 재귀 알고리즘, DFS, 실행 취소, 웹 브라우저 뒤로가기 등 - 큐 (Queue) FIFO (First In First Out) 즉, 먼저 들어간 원소가 먼저 나온다. - 사용 사례 어떠한 작업 및 데이터를 순서대로 실행 및 대시킬 때 사용 서로 다른 쓰레드 또는 프로세스 사이에서 자료를 주고 받을 때 자료를 일시적으로 저장하는 용도로 많이 사용함. 배열(Array), 연결 리스트(Linked List) - 배열 (Array) 물리적 순서와 논리적 순서가 같은 연속된 메모리 공간에 순차적으로 저장된 데이터 모음 따라서 Index로 해당 원소에 접근할 수 있다. 그렇기 때문에 원소의 Index를 알고 있으면 시간복잡도 O(1)에 해당 원소로 접근할 수 있다. 하지만 삭제 또는 삽입의 과정에서는 해당 원소에 접근하여 작업을 완료한 뒤, Shift를 해줘야 하는 상황이 발생할 수 있기 때문에 Shift하는 비용이 발생하고 이 경우의 시간 복잡도는 O(n)이 된다. 배열의 크기가 대부분 정적으로 결정된다. 배열은 순차적인 데이터를 저장하며 값보다는 순서가 중요하거나 다차원 데이터를 다룰 때, 어떤 특정 요소를 빠르게 읽어야할 때, 데이터 사이즈가 자주 바뀌지 않으며 요소가 자주 추가되거나 삭제되지 않을 때 사용.. 레드 블랙 트리(Red-Black Tree) Red-Black Tree : 기존 이진 탐색 트리에서 탐색, 삽입, 삭제의 시간 복잡도는 O(h)이다. 즉 , 트리의 높이에 비례한 만큼의 시간이 걸린다. 원소들이 트리에 잘 분산 되어 있다면 별 문제가 없지만, 한 쪽으로 치우친 트리 (skewed tree)의 경우에는 높이가 n이 되어 시간 복잡도가 O(n)이 된다. 이러한 이진 탐색 트리에 색(Red, Black)이라는 속성을 추가하여 최악의 상황이라도 시간 복잡도 O(log n)을 유지한다. - 조건 1. 모든 node는 Red 혹은 Black의 색을 갖는다. 2. root node는 항상 Black이다. 3. NIL node(= leaf node)는 Black이다. 4. Red node의 자식 node는 항상 Black node이다. (= Re.. 이전 1 2 다음
