Hash Table이란?키 -> 값을 빠르게 찾기 위한 자료구조로, 배열의 빠른 접근(random access)과 원하는 키로 값을 찾는 맵(map) 개념을 합친 것이다. 다음과 같은 연산들을 보자.1. 키 k에 값 v를 저장2. 키 k에 해당하는 값 조회3. 키 k에 해당하는 값 삭제위 연산들 모두 일반적으론 키 k를 찾기위해 순회를 해야한다(O(n)). 하지만 해시 테이블은 이런 작업들을 O(1)에 수행할 수 있게 해준다.How?해시 테이블의 핵심 아이디어는 이름에서도 할 수 있듯이 해시 함수(Hash Function)이다. 그 중 기본은 나머지 연산을 활용한 해시 함수로 다음과 같이 작동한다. 1. 내부에 고정 길이 배열을 확보 (크기 m)2. 키 k가 들어오면 해시 함수로 k를 정수 h(= has..

Stack마지막에 넣은 게 먼저 나오는 LIFO(Last In First Out) 구조의 자료구조이다. LIFO가 전부 Stack은 아니고 삽입, 삭제, 조회는 무조건 Top에서만 이루어지고 중간 삭제/임의 접근 없음 제약을 지킬 때 Stack이라고 부른다. 배열 혹은 연결 리스트로 구현한다. top을 배열의 끝 혹은 연결리스트의 머리에 두고 push/pop 연산을 실행한다.연결리스트로 구현한 경우 노드 오버헤드/포인터 추적으로 인한 오버헤드가 생겨 일반적으로 배열을 기반으로 구현한다. Queue먼저 넣은 게 먼저 나오는 FIFO(First In First Out) 구조의 자료구조이다. Stack과 마찬가지고 FIFO면 모두 Queue가 아니라 삽입은 rear에, 삭제/조회는 front에서 이루어지고 우..

힙(Heap)이란?가장 큰 값 혹은 가장 작은 값을 빠르게 꺼내기 위한 자료구조이다(메모리의 Heap 아님). 대부분 완전 이진트리를 사용하며 배열 하나로 구현한다. 목적에 맞게 다음과 같은 두 가지의 구현이 있다. 최소 힙: 가장 작은 값이 항상 루트 노드에 있으며 모든 노드에서 부모는 자식보다 작거나 같다.최대 힙: 가장 큰 값이 항상 루트 노드에 있으며 모든 노드에서 부모는 자식보다 크거나 같다.이런 특징들로 우선순위 큐를 구현하는데 가장 많이 사용된다. 또한, 배열 하나로 구현하기 때문에 인덱스 매핑으로 완전이진트리를 구현한다.부모 노드: 자식 노드 idx // 2왼쪽 자식: 부모 노드 * 2오른쪽 자식: 부모 노드 * 2 + 1 Heap의 주요 연산모든 연산은 연산 이후 Heap의 불변식인 모든..

Array연속된 메모리에 같은 타입의 값들을 순서대로 저장하는 자료구조이다. 연속된 메모리에 값이 할당되기 때문에 arr[0]과 arr[1]은 메모리 상에서도 옆에 위치해있다.메모리에 저장하고자 하는 크기의 연속된 공간이 없다면 어떡할까? 그것은 Virtual Address를 통해 해결한다. OS는 페이지 단위로 매핑하므로, 물리적으로 불연속이어도 가상 주소가 연속이면 배열처럼 쓸 수 있다. C/C++의 malloc/mmap, 파이썬 리스트, 자바 배열 모두 “가상 주소상 연속”을 요구한다. 그럼 다시 말을 정리하자면 "가상 주소상에서 연속된 공간"에 저장하는 것이 Array다.왜 같은 타입만 저장 가능할까?연속된 메모리에 동일 크기의 원소이어야 인덱싱이 각 원소의 크기(int = 4byte 등등)를 계..