~2023.02/자료구조

힙(Heap)

1. 힙(Heap) 이란? 힙 : 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 완전 이진 트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 힙을 사용하는 이유 배열에 데이터를 넣고, 최댓값과 최솟값을 찾으려면 O(n)이 걸림 이에 반해, 힙에 데이터를 넣고, 최대값과 최솟값을 찾으면, O(logn) 이 걸림 우선순위 큐와 같이 최대값 또는 최솟값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨 2. 힙(Heap) 구조 힙은 최대값을 구하기 위한 구조 (최대 힙, Max Heap) 와, 최솟값을 구하기 위한 구조 (최소 힙, Min Heap) 로 분류할 수 있음 힙은 다음과 같이 두 가지 조건을 가지고 있는 ..

스택(Stack)

0. 스택 데이터를 제한적으로 접근할 수 있는 구조 (큐와 동일) 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조 (큐와 차이) 큐 : FIFO 정책 (줄 서기) 스택 : LIFO 정책 (책 쌓기) 1. 스택 구조 스택은 LIFO(Last In, First Out) 또는 FILO(First In, Last Out) 데이터 관리 방식을 따름 LIFO : 마지막에 넣은 데이터를 가장 먼저 추출하는 데이터 관리 정책 FILO : 처음에 넣은 데이터를 가장 마지막에 추출하는 데이터 관리 정책 대표적인 스택의 활용 컴퓨터 내부의 프로세스 구조의 함수 동작 방식 주요 기능 push() : 데이터를 스택에 넣기 pop() : 데이터를 스택에서 꺼내기 Vi..

알고리즘 복잡도 표현 기법

알고리즘 복잡도 계산이 필요한 이유 하나의 문제를 푸는 알고리즘은 다양할 수 있음 정수의 절대값 구하기 방법1 : 정수값을 제곱한 값에 다시 루트를 씌우기 방법2 : 정수가 음수인지 확인해서, 음수일 때만, -1을 곱하기 다양한 알고리즘 중 어느 알고리즘이 더 좋은지를 분석하기 위해, 복잡도를 정의하고 계산함 알고리즘 복잡도 계산 항목 1. 시간 복잡도 : 알고리즘 실행 속도 2. 공간 복잡도 : 알고리즘이 사용하는 메모리 사이즈 가장 중요한 시간 복잡도를 꼭 이해하고 계산할 수 있어야 함 알고리즘 시간 복잡도의 주요 요소 반복문이 지배합니다. 알고리즘 성능 표기법 Big O (빅-오) 표기법 : O(N) 알고리즘 최악의 실행 시간을 표기 가장 많이/일반적으로 사용함 아무리 최악의 상황이라도, 이정도의 ..

큐(Queue)

1. 큐 구조 줄을 서는 행위와 유사 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조 음식점에서 가장 먼저 줄을 선 사람이 제일 먼저 음식점에 입장하는 것과 동일 FIFO(First-in, First-out) 또는 LILO(Last-in, Last-out) 방식으로 스택과 꺼내는 순서가 반대 2. 알아둘 용어 Enqueue : 큐에 데이터를 넣는 기능 Dequeue : 큐에서 데이터를 꺼내는 기능 Visualgo 사이트에서 시연해보며 이해하기 (enqueue / dequeue 만 클릭해보며) https://visualgo.net/en/list 3. 파이썬 queue 라이브러리 활용해서 큐 자료구조 사용하기 queue 라이브러리에는 다양한 큐 구조로 Queue(), LifoQueue(), Prior..

해쉬(Hash)

1. 해쉬 구조 해쉬 테이블 : 키(key)에 데이터(value)를 저장하는 데이터 구조 key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐 파이썬 딕셔너리 타입이 해쉬 테이블의 예 : key를 가지고 바로 데이터(value)를 꺼냄 보통 배열로 미리 hash table 사이즈만큼 생성 후에 사용 (공간과 탐색 시간을 맞바꾸는 기법) 단, 파이썬에서는 해쉬를 별도 구현할 이유가 없음 - 딕셔너리 타입을 사용하면 됨 2. 알아둘 용어 해쉬 : 임의 값을 고정 길이로 변환하는 것 해쉬 테이블 : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조 해쉬 함수 : 키에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수 해쉬 값 또는 해쉬 주소 : 키를 해싱 함수로 연산해서, 해..

배열

배열(Array) 데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조 파이썬에서는 리스트 타입이 배열 기능을 제공함 1. 배열은 왜 필요할까? 같은 종류의 데이터를 효율적으로 관리하기 위해 사용 같은 종류의 데이터를 순차적으로 저장 장점: 빠른 접근 가능 첫 데이터의 위치에서 상대적인 위치로 데이터 접근(인덱스 번호로 접근) 단점: 데이터 추가/삭제의 어려움 미리 최대 길이를 지정해야 함 [C 언어 예: 영어 단어 저장] #include int main(int argc, char * argv[]) { char country[3] = "US"; printf ("%c%c\n", country[0], country[1]); printf ("%s\n", country); return 0; }..