앞서 설명한 자료구조 중 자주 쓰는 자료 구조의 최악의 시간 복잡도 Big O 스택과 큐의 경우 가장 앞에 있는 요소를 참조한다고 하면 O(1)이지만 중간에 있는 요소를 참조한다고 했을 때 랜덤접근이 아닌 순차접근만 되기 때문에 O(n)의 시간이 걸린다.

목차 팬윅 트리? 구현 업데이트 1. Fenwick Tree ? Segment Tree 처럼 구간에 대한 연산을 저장하는 트리 Segment Tree 보다 적은 메모리로 사용 가능하다!! 절반 정도의 메모리만으로 사용 가능 시간 복잡도 O(logN) 비트를 이용한 구간 연산을 진행한다. Q. 3~5번째 인덱스 구간 합을 구하기 A. 두 구간의 차를 구하면 된다. 5번 인덱스까지의 값을 구하려면 2진수 101 인덱스 값과 100 인덱스 값을 더하면 된다. 101 인덱스에서 마지막 1의 값을 제거해주면 100이 된다. Q. 마지막 2진수 1의 값을 제거하는 방법은? Answer. N = N - (N & -N) 5 - ( 5 & -5 ) = 4 4 - ( 4 & -4 ) = 0 2. 구현 Val = 1 ind..

지금까지 여러 자료 구조를 알아보았고, 아마 이번에 배우는 그래프가 마지막일 것이다! 목차 그래프란? 그래프 유형 그래프 표현 서로소 집합 1. 그래프란? 그래프는 아이템(사물 또는 추상적 개념)들과 이들 사이의 연결 관계를 표현 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료 구조 IVI : 정점의 개수 IEI : 그래프에 포함된 간선의 개수 무향 그래프 - IVI 개의 정점을 가지는 그래프는 최대 IVI (IVI - 1) / 2 간선이 가능 유향 그래프 - IVI 개의 정점을 가지는 그래프는 최대 IVI (IVI - 1) 간선이 가능 선형 자료구조나 트리 자료구조로 표현하기 어려운 N:N 관계를 가지는 원소들을 표현하기에 용이 2. 그래프 유형 1. 무향 그래프..

앞에서 봤던 트리의 종류 중 높이가 h이고 노드수가 n개 일 때, 포화 이진트리의 1번부터 n번까지 빈자리가 없는 트리였던 완전 이진 트리에 있는 노드 중 키 값이 가장 큰 노드 or 키 값이 가장 작은 노드를 찾기 위해 만든 자료 구조이다. 최대 힙 (max heap) 키 값이 가장 큰 노드를 찾기 위한 완전 이진트리 (부모 노드의 키값 > 자식 노드의 키값) 루트 노드 : 키값이 가장 큰 노드 최소 힙 (min heap) 키 값이 가장 작은 노드를 찾기 위한 완전 이진트리 (부모 노드의 키 값 < 자식 노드의 키 값) 루트 노드 : 키값이 가장 작은 노드 삽입 삭제 힙에서는 루트 노드만이 삭제 가능 루트 노드의 원소를 삭제하여 반환 힙의 종류에 따라 최솟값 또는 최댓값 구하기 가능 # 파이썬에서의 힙..

앞서 봤던 트리들에서 탐색 효율을 높이기 위해 사용하는 '이진 탐색 트리'에 대해서 알아보자. 목차 1. 이진 탐색 트리? 2. 연산 3. 성능 1. 이진 탐색 트리? 탐색 작업을 효율적으로 하기 위한 자료구조 모든 원소는 서로 다른 유일한 키를 가진다. key(왼쪽 서브 트리) < key(루트 노드) < key(오른쪽 서브 트리) 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리 중위 순회하면서 오름차순으로 정렬된 값을 얻을 수 있다. 2. 연산 탐색 연산 루트에서 시작한다. 탐색할 키 값 x를 루트 노드의 키 값과 비교한다. (키 값 x = 루트 노드의 키값)인 경우 : 원하는 원소를 찾았으므로 탐색연산 성공 (키 값 x < 루트 노드의 키값)인 경우 : 루트노드의 왼쪽 서브 트리에 대해서 탐색연..

지금까지는 단순 구조, 선형 구조에 대해서 알아보았다. 이번 글에서는 '비선형 구조' 중 하나인 '트리'에 대해 알아보자! 목차 1. 개념 및 정의 2. 이진트리 3. 순회 4. 표현 및 저장 5. 연결 리스트 1. 개념 및 정의 개념 비선형 구조 원소들 간에 1 : N 관계를 가지는 자료구조이다.ㅣ 또한 원소들 간 계층 관계를 가지는 계층형 자료구조 상위 원소에서 하위 원소로 내려가며 확장되는 나무(트리) 모양의 구조 정의 한 개 이상의 노드로 이루어진 유한 집합 노드 중 최상위 노드 -> 루트(root) 나머지 노드들은 n개의 분리 집합 T1... TN으로 분리될 수 있다. 이들 T1... TN은 각각 하나의 트리가 되며(재귀적 정의) 루트의 부 트리(subtree)라 한다. 용어 정리 노드(node..

해시 구조를 이해하기 위해서 먼저 해시 테이블에 대해 알아보자. 1. 해시 테이블? 연관 배열 구조를 이용하여 키(key)와 결과 값(value)를 저장하는 자료구조 연관 배열 구조란 - key와 value가 1:1로 연관 되어 있는 구조이다. 파이썬의 Dictionary! 지원하는 명령 key와 value 저장 key가 주어질 때, 연관 value를 얻는 명령 key와 value가 주어질 때, 원래 key의 value값 수정 key가 주어질 때, 연관 value 제거\ 구조 해시 테이블의 경우 키(Key), 해시 함수(Hash Function), 해시(Hash), 값(value), 저장소(Bucket, Slot)로 이루어져 있다. 위 그림에서 볼 수 있듯이 키(key)는 해시함수(hash functio..

OTT, 유튜브 등을 시청할 때 '버퍼링' 때문에 짜증났던 기억이 있을 것이다. 왜 일어나는 것일까? 배웠던 Queue 구조를 활용하여 버퍼에 대해 알아보자. 또한 queue를 파이썬에서 더 간편하고 빠르게 사용하게 해주는 deque에 대해서도 알아보자. 목차 1. 버퍼 2. deque 모듈 1. 버퍼 데이터를 한 곳에서 다른 한 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리 영역 버퍼링: 버퍼를 활용하는 방식 또는 버퍼를 채우는 동작 자료 구조 버퍼는 일반적으로 입출력 및 네트워크와 관련된 기능에서 이용 순서대로 입/출력/전달되어야 하므로 FIFO 방식의 자료구조인 큐가 활용 그림을 통해 키보드 버퍼의 수행 과정을 보자. Queue와 버퍼에 대해 '마이쮸 나눠주기'를 구현해보며 이해해보자..

이전에 배웠던 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조이다. 동적 자료형인 리스트 자료형을 사용한다 선입선출 구조(FIFO : First In First Out) 큐의 뒤에서는 삽입만 하고, 큐의 앞에서는 삭제만 한다. 즉, 삽입한 순서대로 원소가 저장되어, 가장 먼저 삽입된 원소가 가장 먼저 삭제된다. 기본 연산 삽입 : enQueue(item) - 큐의 뒤쪽(rear 다음)에 원소를 삽입하는 연산 삭제 : deQueue() - 큐의 앞쪽(front)에서 원소를 삭제하고 반환하는 연산 createQueue() - 공백 상태의 큐를 생성하는 연산 isEmpty() - 큐가 공백상태인지를 확인하는 연산 isFull() - 큐가 포화상태인지를 확인하는 연산 Qpeek() - 큐의 앞쪽(fro..