같은 계산을 반복하는 것은 비효율적이다. 예를 들어 피보나치 수열에서 fib(5)를 계산할 때, fib(3)을 여러 번 중복 계산한다.한 번 계산한 결과를 저장해두면 훨씬 빠를 것이다.이것이 바로 동적 프로그래밍(Dynamic Programming)의 핵심 개념이다. 동적 프로그래밍 (Dynamic Programming)동적 프로그래밍은 복잡한 문제를 작은 부분 문제로 나누어 해결하고, 그 결과를 저장하여 중복 계산을 방지하는 알고리즘 기법이다.동적 프로그래밍은 크게 두 가지 방식으로 구현할 수 있다. 메모이제이션타뷸레이션방식하향식 (Top-down)상향식 (Bottom-up)구현재귀 + 캐싱반복문 + 테이블계산필요한 값만 계산모든 값을 미리 계산메모리스택 + 캐시 공간테이블 공간만문제: 피보나치 수열피..

책장에 있는 책들을 키 순서대로 정리한다고 생각해보자. 작은 책부터 큰 책 순서로 나열하는 방법은 여러 가지가 있다.어떤 방법은 간단하지만 느리고, 어떤 방법은 복잡하지만 빠르다. 이것이 바로 정렬 알고리즘이다.정렬 (Sort)정렬은 데이터를 특정 순서대로 배열하는 알고리즘이다.오름차순(작은 것부터 큰 것), 내림차순(큰 것부터 작은 것) 등 다양한 기준으로 정렬할 수 있다.정렬 알고리즘 비교 시간복잡도난이도특징버블 정렬 O(n²)쉬움인접한 원소를 교환선택 정렬 O(n²)쉬움최솟값을 찾아 교환삽입 정렬 O(n²)쉬움적절한 위치에 삽입병합 정렬 O(n log n)어려움분할 정복, 안정 정렬퀵 정렬 O(n log n) ~ O(n²)어려움분할 정복, 실정네서 빠름 버블 정렬 (Bubble Sort)인접한 두 ..

거울 앞에 거울을 놓으면 무한히 반복되는 모습을 볼 수 있다. 이처럼 자기 자신을 참조하는 것을 재귀라고 한다. 프로그래밍에서 재귀는 함수가 자기 자신을 호출하는 것을 의미한다. 재귀 (Recursion)재귀는 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다. 프로그래밍에서는 함수가 자기 자신을 호출하는 재귀 함수로 구현된다.재귀 함수의 필수 요소재귀 함수는 탈출 조건(기저 조건)이 없으면 무한히 자신을 호출하기 때문에, 결국 스택 메모리가 가득 차서 프로그램이 종료된다.(Stack Overflow). 따라서 재귀 함수에는 반드시 다음 두 가지가 필요하다. 설명기저 조건 (Base Case)재귀를 멈추는 조건재귀 호출 (Recursive Call)자기 자신을 호출하는 부분 간단한 재귀 함수 예시..

배열 [1, 2, 3, 2, 4, 1, 5]에서 중복을 제거하고 싶다고 생각해보자.일일이 확인하며 중복을 찾는 것보다, 중복을 자동으로 허용하지 않는 자료구조가 있다면 훨씬 편리할 것이다.이것이 바로 셋(Set)의 핵심 개념이다. SetSet은 데이터의 중복을 허용하지 않는 자료구조이다. 내부적으로는 일반적으로 해시 테이블을 기반으로 구현되며, 각 요소는 key만 존재하고 value가 없는 형태로 저장된다.이 때문에 **해시 셋(HashSet)**이라고도 부르며, 요소 자체가 key의 역할을 수행한다.Set vs Hash Table Hash TableSet저장 형태key-value 쌍key만 (value 없음)중복 허용key 중복 불가요소 중복 불가주 용도데이터 매핑중복 제거, 존재 여부 확인예시{ 1:..

전화번호부에서 이름으로 전화번호를 찾는다고 생각해보자. 전화번호부가 정렬되지 않았다면 처음부터 끝까지 찾아야 하지만, 이름을 특정 규칙으로 변환해서 바로 위치를 찾을 수 있다면 훨씬 빠를 것이다. 이것이 바로 해시 테이블(Hash Table)의 핵심 개념이다. 해시 테이블해시 테이블은 해시 함수와 테이블(배열)이 합쳐진 자료구조이다.키(Key)를 해시 함수로 변환하여 인덱스를 얻고, 그 위치에 값(Value)을 저장한다. 이를 통해 데이터의 저장과 검색을 매우 빠르게 수행할 수 있다.해시 테이블의 핵심 개념 설명키 (Key)데이터를 식별하는 고유한 값 (예: 1, 21)값 (Value)실제로 저장할 데이터 (예: "이운재", "박지성")해시 함수키를 인덱스로 변환하는 함수 (예: key % 10)버킷 ..

스택은 한쪽 끝에서만, 큐는 양쪽 끝이지만 각각 다른 작업(삽입/삭제)만 가능했다.그렇다면 양쪽 끝에서 삽입과 삭제를 모두 자유롭게 할 수 있다면 어떨까? 바로 그것이 덱(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(): 전체 아이템 개수 반환 사전 학습구현에 앞서 필요한 개념들을 먼저 정리했다.배열과 리스트배열은 메..