스택은 한쪽 끝에서만, 큐는 양쪽 끝이지만 각각 다른 작업(삽입/삭제)만 가능했다.그렇다면 양쪽 끝에서 삽입과 삭제를 모두 자유롭게 할 수 있다면 어떨까? 바로 그것이 덱(Deque, Double-Ended Queue)이다.덱덱은 Double-Ended Queue의 약자로, 데이터의 삽입과 제거를 head와 tail 두 곳 모두에서 자유롭게 할 수 있는 자료구조이다. 스택과 큐의 기능을 모두 포함하는 더 유연한 구조라고 할 수 있다.스택, 큐, 덱 비교 스택 (Stack)큐 (Queue)덱 (Deque)삽입 위치한쪽 끝뒤쪽양쪽 끝 모두삭제 위치한쪽 끝 (같은 곳)앞쪽양쪽 끝 모두구조LIFOFIFO자유로움활용뒤로 가기, Undo대기열, BFS슬라이딩 윈도우 등 덱의 핵심 연산덱은 다음과 같은 기본 연산을 ..

은행 창구나 마트 계산대를 떠올려보자.먼저 온 사람이 먼저 처리를 받고, 나중에 온 사람은 뒤에서 기다린다. 이것이 큐(Queue)의 핵심 개념이다. 스택이 "가장 최근 것을 먼저"라면, 큐는 "먼저 온 것을 먼저" 처리하는 공정한 자료구조이다. 큐큐는 FIFO(First-In-First-Out) 구조를 가지는 자료구조이다.먼저 들어온 데이터가 먼저 나가는 구조로, 스택과 정반대의 특성을 가지고 있다.스택 vs 큐 스택 (Stack)큐 (Queue)구조LIFO (후입선출)FIFO (선입선출)비유접시 쌓기줄서기삽입push (한쪽 끝)enqueue (뒤쪽)삭제pop (같은 쪽 끝)dequeue (앞쪽) 큐의 핵심 연산큐는 다음과 같은 기본 연산을 제공한다.enqueue(): 큐의 뒤쪽에 데이터를 추가dequ..

접시를 쌓을 때를 생각해보자.아래에서부터 차곡차곡 쌓아 올리고, 사용할 때는 가장 위에 있는 접시부터 꺼내게 된다.이것이 바로 스택(Stack)의 핵심 개념이다. 스택스택은 FILO(First-In-Last-Out) 또는 LIFO(Last-In-First-Out) 구조를 가지는 자료구조이다.즉, 먼저 들어온 데이터가 나중에 나가고, 나중에 들어온 데이터가 먼저 나가는 구조이다.스택의 핵심 연산스택은 다음과 같은 기본 연산을 제공한다.push(): 스택의 맨 위에 데이터를 추가pop(): 스택의 맨 위에서 데이터를 제거하고 반환peek(): 스태그이 맨 위 데이터를 제거하지 않고 확인isEmpty(): 스택이 비어있는지 확인 연결 리스트로 스택 구현하기스택은 배열로도 구현할 수 있지만, 이전 글에서 다룬 ..

배열배열은 프로그래밍에서 가장 기본적이고 많이 사용되는 자료구조이다.하지만 배열에도 분명한 한계가 있다.배열의 장단점배열의 장점빠른 접근 속도: 인덱스를 통한 읽기/쓰기가 O(1)의 시간복잡도를 가진다.메모리의 연속성: 데이터가 연속적으로 저장되어 캐시 효율성이 좋다.배열의 단점고정된 크기: 배열을 선언할 때 크기를 미리 정해야 하므로, 필요한 크기를 예측하기 어려운 경우 메모리 낭비가 발생할 수 있다.비효율적인 삽입/삭제: 중간에 데이터를 삽입하거나 삭제할 때, 뒤에 있는 모든 요소를 이동시켜야 한다. 연결 리스트연결 리스트(Linked List)는 배열의 단점을 보완하기 위해 만들어진 자료구조이다.각 요소(노드)가 데이터와 다음 노드를 가리키는 포인터로 구성되어 있어, 메모리상에서 연속적으로 배치될 ..

자바스크립트의 Map을 배열만으로 직접 구현해보면서 해시맵의 동작 원리를 이해하는 과정을 정리했다. 구현 목표자바스크립트의 Map 기본 동작을 따라서 문자열 키-값 해시맵을 구현한다.단, Object, Map 등을 사용하지 않고 오직 배열로만 구현해야 한다.구현할 메서드clear(): 전체 맵 초기화containsKey(String): 키 존재 여부 반환get(String): 키에 해당하는 값 반환isEmpty(): 빈 맵 여부 반환keys(): 전체 키 목록을 배열로 반환put(String key, String value): 키-값 추가remove(String key): 키에 해당하는 값 삭제size(): 전체 아이템 개수 반환 사전 학습구현에 앞서 필요한 개념들을 먼저 정리했다.배열과 리스트배열은 메..

복잡한 프로그램을 구현하다 보면 기본적인 포인터 구조만 이용해서 메모리를 관리하기에는 다소 번거로울 때가 많다.메모리를 좀 더 효율적으로 관리하고 사용할 수 있는 데이터 구조의 개념과 연결 리스트를 알아보자.데이터 구조란데이터 구조(Data Structure)는 우리가 컴퓨터 메모리를 더 효율적으로 관리하기 위해 새로 정의하는 구조체다.일종의 메모리 레이아웃, 또는 지도라고 생각할 수 있다. 데이터 구조 중 하나인 연결 리스트에 대해 알아보자. 연결 리스트의 개념배열의 한계배열에서는 각 인덱스의 값이 메모리상에서 연이어 저장되어 있다.배열: [1][2][3]주소: 100 104 108 ← 연속된 메모리하지만 꼭 그럴 필요가 있을까? 연결 리스트의 아이디어각 값이 메모리상의 여러 군데 나뉘어져 있다고 ..

컴퓨터 안의 메모리는 마치 사물함 같은 구조다.우리가 사용하고자 하는 사물함의 개수를 한 번 정한 이후에는, 공간이 모자란다고 해서 주변의 사물함을 마음대로 더 사용할 수는 없다.이미 다른 목적으로 사용되고 있을 수도 있기 때문이다. 이미 일정한 크기의 메모리가 할당되어 있는 상황에서 그 크기를 늘리는 일은 생각만큼 단순하지 않다.포인터와 malloc의 개념을 응용해서 이미 정의된 배열의 크기를 바꿔보자.배열의 크기 조정하기배열 크기를 늘리는 방법일정한 크기의 배열이 주어졌을 때, 그 크기를 키우려면 어떻게 해야 할까? 단순히 현재 배열이 저장되어 있는 메모리 위치의 바로 옆에 덧붙이면 될 것 같지만, 실제로는 다른 데이터가 저장되어 있을 확률이 높다.따라서 새로운 공간에 큰 크기의 메모리를 다시 할당하..

사용자에게 입력을 받는 함수는 어떻게 구현할 수 있을까? 파일을 읽고 쓰는 방법을 알아보자. 메모리 구조를 다시 한 번 살펴보면,메모리 영역머신 코드: 프로그램이 컴파일된 바이너리글로벌: 프로그램 안에서 저장된 전역 변수힙: malloc으로 할당된 메모리의 데이터스택: 프로그램 내의 함수와 관련된 것들힙 영역에서는 malloc에 의해 메모리가 더 할당될수록 아래로 늘어나고, 스택 영역에서는 함수가 더 많이 호출될수록 위로 늘어난다. 제한된 메모리 용량 하에서 점점 늘어나다 보면 기존의 값을 침범하는 상황이 발생하는데, 이를 힙 오버플로우 또는 스택 오버플로우라고 한다. 사용자에게 입력 받기get_int 구현#include int main(void){ int x; printf("x: "); ..

각각 사이다와 콜라가 들어있는 컵 두 개가 있을 때, 사이다와 콜라를 바꿔 담고 싶으면 어떻게 해야 할까?아마 교환을 도와줄 새로운 컵이 잠시 필요할 것이다. 메모리에 저장된 값들을 교환할 때도 이와 비슷하게 할 수 있을까?잘못된 값 교환다음 코드를 보자.#include void swap(int a, int b);int main(void){ int x = 1; int y = 2; printf("x is %i, y is %i\n", x, y); swap(x, y); printf("x is %i, y is %i\n", x, y);}void swap(int a, int b){ int tmp = a; a = b; b = tmp;}// 출력// x is 1, y is 2..

메모리를 할당한 후에 저장한 값이 필요 없어지고 나면 어떻게 해야 할까?유한한 메모리를 효과적으로 관리하기 위해 할당한 메모리를 어떻게 관리해야 하는지 알아보자.메모리 해제의 필요성malloc 함수를 이용하여 메모리를 할당한 후에는 free 함수를 이용하여 메모리를 해제해야 한다.그렇지 않으면 메모리에 저장한 값은 쓰레기 값으로 남게 되어 메모리 용량의 낭비가 발생하는데, 이러한 현상을 메모리 누수(Memory Leak)라고 한다. 문제가 있는 코드다음 코드를 살펴보자.#include void f(void){ int *x = malloc(10 * sizeof(int)); x[10] = 0;}int main(void){ f(); return 0;}함수 f는 포인터 x에 int형의 크기..