📙 자료구조

정의: 데이터를 메모리에 저장하기 위한 구조(Structure). 데이터가 어떻게 조직되어 있는지 말하는 것.

• 어떤 자료구조든 트레이드 오프(trade-off)가 존재한다.
• 프로그램의 목적에 적합한 자료구조를 고르는 것이 핵심.

ex)
사용자 대기열 시스템을 구현 - 큐(Queue), 선입선출 메커니즘을 활용
코드 에디터의 Undo 기능 - 스택(Stack), 후입선출(LIFO) 메커니즘을 활용
GPS 시스템을 구현 - 그래프(Graph), 복잡한 네트워크 관계를 모델링하는데에 적합
사용자 인증 및 조회 - 해시 테이블 (Hash Table), 키-값 쌍으로 데이터를 저장하고, 빠른 검색 속도를 제공.

📗 메모리(RAM)

정의: 메모리(RAM)는 CPU가 즉시 읽고 쓸 수 있는 휘발성 주기억장치(volatile memory)다.

• 모든 주소에 동일한 속도로 접근 (랜덤 엑세스)
• 각 바이트가 고유 주소를 가지고 있고, 프로그램은 주소로 직접 읽기 & 쓰기.
• 실행 중인 코드, 데이터를 임시로 보관하고 영구저장은 SSD/HDD가 담당

✔ 스택 메모리(stack memory)

정의: 함수 호출마다 생기는 호출 프레임(Call Frame)이 쌓이다가 (LIFO) 함수 반환 시 사라지는 주기억장치 영역.

• 운영체제가 최대 한도를 정해 둔다. (넘어서면 Stack Overflow 발생)
• 원시 타입(Primitive types) 값과 객체 참조가 저장된다.

장점:

• 매우 빠름: 메모리 할당 및 해제가 간단한 포인터 이동으로 이루어져 속도가 빠르다.
• 자동 관리: 함수 호출이 끝나면 해당 프레임의 메모리가 자동으로 정리된다. 개발자가 직접 관리할 필요가 적다.

단점:

• 크기 제한: 운영체제가 정한 크기 이상으로 사용할 수 없다.
• 유연성 부족: 컴파일 시 크기가 결정되어야 하므로 동적인 데이터 저장에는 부적합하다.

✔ 힙 메모리(heap memory)

정의: 실행 중에 필요에 따라 동적으로 할당·해제되는 메모리 영역.

• new, malloc 등 명시적 할당 혹은 가비지 컬렉터(GC)가 관리
• 객체, 동적 배열처럼 크기가 가변적인 데이터를 저장하며, 스택 한계를 넘어서는 큰 구조도 담을 수 있다

장점:

• 유연한 할당: 런타임에 요구되는 만큼 메모리를 확보할 수 있다
• 대용량 처리: 스택 크기 제한을 초과하는 큰 데이터 구조를 저장 가능
• 수명 제어: 스코프와 무관하게 참조가 살아 있는 동안 데이터가 유지된다

단점:

• 할당·해제 오버헤드: 스택보다 느리고, GC가 개입하면 추가 지연이 발생할 수 있다
• 단편화(Fragmentation): 빈 영역이 늘어나 메모리 효율이 떨어질 수 있다
• 메모리 누수 위험: 수동 언어(C/C++)는 해제 누락, GC 언어는 불필요 참조로 해제가 지연될 수 있다

📗 배열 (Array)

정의: 인덱스로 순서를 관리하는 자료구조. JS의 배열은 객체의 특별한 형태로, 인덱스를 키(문자열 형태)로 사용하며 동적으로 크기가 조절될 수 있다. 메모리 상에서는 반드시 연속적이지 않을 수 있지만, 논리적으로는 연속된 구조처럼 동작한다.

• 인덱스(Index): 배열 내 요소의 위치를 나타내는 0부터 시작하는 숫자.
• 인덱스를 통해 요소에 접근하는 것은 매우 빠르다. (O(1) 시간 복잡도).

장점:

• 빠른 접근: 인덱스를 알고 있다면 해당 요소에 상수 시간(O(1)) 으로 즉시 접근하여 읽고 쓸 수 있다.
• 순차적 데이터 관리 용이: 데이터를 순서대로 저장하고 관리하기 편리하다.

단점:

• 삽입/삭제 비효율: 배열의 중간에 데이터를 삽입하거나 삭제할 경우, 해당 위치 이후의 모든 요소들을 한 칸씩 뒤로 밀거나(삽입) 앞으로 당겨야(삭제) 한다. 이는 선형 시간(O(n)) 이 소요된다. (단, 배열 끝에서의 push/pop은 보통 O(1)).
• 탐색 비효율: 특정 값을 찾기 위해서는 배열의 처음부터 순차적으로 검색해야 할 수 있다. (정렬되지 않은 경우 O(n)).

주요 메서드 (JavaScript):

• push(): 배열의 끝에 요소를 추가한다. (일반적으로 O(1))
• pop(): 배열의 끝에 있는 요소를 제거하고 반환한다. (일반적으로 O(1))
• shift(): 배열의 앞에 있는 요소를 제거하고 반환한다. (O(n) - 나머지 요소 이동 필요)
• unshift(): 배열의 앞에 요소를 추가한다. (O(n) - 나머지 요소 이동 필요)
• slice(start, end): 배열의 일부를 새로운 배열로 복사하여 반환한다. (원본 배열 변경 없음)
• splice(start, deleteCount, item1, ...): 배열의 기존 요소를 삭제 또는 교체하거나 새 요소를 제자리 에 추가한다. (원본 배열 변경 있음, O(n))
• with(index, value): 특정 인덱스의 값을 새로운 값으로 교체한 새 배열 을 반환한다. (원본 배열 변경 없음, slice와 유사하게 불변성 유지에 유용)

📗 스택 (Stack)

정의: 데이터의 삽입과 삭제가 한쪽 끝(Top)에서만 이루어지는 후입선출(LIFO, Last-In, First-Out) 방식의 자료구조. 마지막에 들어온 데이터가 가장 먼저 나간다.

• Top: 데이터의 삽입(Push)과 삭제(Pop)가 일어나는 스택의 가장 윗부분.

핵심 연산:

• push(element): 스택의 Top에 데이터를 추가한다.
• pop(): 스택의 Top에서 데이터를 제거하고 반환한다.
• peek() (또는 top()): 스택의 Top에 있는 데이터를 제거하지 않고 확인한다.
• isEmpty(): 스택이 비어있는지 확인한다.
• size(): 스택에 저장된 데이터의 개수를 반환한다.

장점:

• 단순한 구조: 구현이 매우 간단하다.
• 빠른 연산: 주요 연산(push, pop)이 O(1) 시간 복잡도를 가진다. (배열 끝에서의 연산과 동일)
• 메모리 관리 효율: 데이터 접근 경로가 하나로 정해져 있어 관리가 용이하다. (함수 호출 스택 등에서 사용)

단점:

• 제한된 접근: 오직 Top을 통해서만 데이터에 접근할 수 있다. 중간의 데이터에 접근하려면 상위 요소들을 모두 제거해야 한다.
• 탐색 불가: 특정 데이터를 검색하는 기능에는 적합하지 않다.

구현 예시:

• 일반적으로 배열(Array)을 사용하여 스택을 구현한다.
• push() 메서드는 스택의 push 연산과 동일하게 동작한다.
• pop() 메서드는 스택의 pop 연산과 동일하게 동작한다.

활용 예시:

• 웹 브라우저의 뒤로 가기/앞으로 가기 기능 (방문 기록 스택)
• 코드 에디터의 실행 취소(Undo) 기능
• 함수 호출 스택 (Call Stack): 함수 호출 시 실행 컨텍스트를 저장
• 괄호 검사, 후위 표기법 연산 등

📗 큐 (Queue)

정의: 데이터가 한쪽 끝(Rear)에서 삽입되고 다른 쪽 끝(Front)에서 삭제되는 선입선출(FIFO, First-In, First-Out) 방식의 자료구조. 먼저 들어온 데이터가 가장 먼저 나간다.

• Rear: 데이터가 삽입(Enqueue)되는 큐의 뒷부분.
• Front: 데이터가 삭제(Dequeue)되는 큐의 앞부분.

핵심 연산:

• enqueue(element): 큐의 Rear에 데이터를 추가한다.
• dequeue(): 큐의 Front에서 데이터를 제거하고 반환한다.
• peek() (또는 front()): 큐의 Front에 있는 데이터를 제거하지 않고 확인한다.
• isEmpty(): 큐가 비어있는지 확인한다.
• size(): 큐에 저장된 데이터의 개수를 반환한다.

장점:

• 순서 보장: 데이터가 들어온 순서대로 처리되는 것을 보장한다. (공정성)
• 간단한 원리: FIFO 원리는 이해하기 쉽다.

단점:

• 배열로 구현시 Dequeue의 비효율성: 배열로 큐를 구현할 경우 dequeue 연산 시에 비효율성이 따른다. 예를 들어 shift() 메서드를 dequeue 로 사용하면, 앞 요소를 제거 후 나머지 요소들을 앞으로 당겨야 하므로 O(n) 시간 복잡도가 발생한다. (많은 양의 데이터 처리 시 성능 저하)
  • 💡 연결 리스트(Linked List) 등으로 구현하면 enqueue, dequeue 모두 O(1) 으로 만들 수 있으나 구현이 더 복잡해진다.
• 탐색 비효율: 특정 데이터를 검색하기 어렵다.

배열로 큐 구현하기:

• 배열의 push()를 enqueue로, shift()를 dequeue로 사용할 수 있다.

활용 예시:

• 프린터 인쇄 대기열
• 너비 우선 탐색 (BFS) 알고리즘
• 운영체제의 프로세스 스케쥴링
• 웹 서버의 요청 처리

📗 재귀 함수 (Recursion)

정의: 함수가 자기 자신을 다시 호출하는 함수. 복잡한 문제를 더 작고 동일한 구조의 문제로 나누어 해결할 때 유용하다.

• 모든 재귀 함수는 기저 사례(Base Case) 를 가져야 한다. 그렇지 않으면 무한 루프에 빠져 스택 오버플로우(Stack Overflow) 에러를 발생시킨다.

구성 요소:

1. 기저 사례 (Base Case): 재귀 호출을 멈추는 조건. 더 이상 자기 자신을 호출하지 않고 특정 값을 반환한다.
2. 재귀 단계 (Recursive Step): 함수가 자기 자신을 호출하는 부분. 호출 시 인자를 변경하여 점차 기본 단계에 수렴하도록 만든다.

동작 원리:

• 함수가 호출될 때마다 호출 스택(Call Stack) 에 해당 함수의 실행 컨텍스트(매개변수, 지역 변수 등)가 쌓인다.
• 재귀 호출이 발생하면 새로운 실행 컨텍스트가 스택의 맨 위에 쌓인다.
• 기본 단계에 도달하면, 함수는 값을 반환하고 스택에서 제거된다(pop).
• 스택이 빌 때까지 이 과정이 반복되며, 최종 결과가 반환된다.

장점:

• 코드 간결성: 특정 문제(특히 분할 정복, 트리 순회 등)에 대해 코드를 매우 간결하고 우아하게 작성할 수 있다.
• 가독성: 문제의 재귀적 구조를 코드로 직관적으로 표현할 수 있다.

단점:

• 성능 저하: 함수 호출에는 오버헤드가 발생하므로 반복문(Iteration)보다 성능이 느릴 수 있다.
• 스택 오버플로우 위험: 재귀 호출이 너무 깊어지면(종료 조건이 잘못되었거나 입력 크기가 매우 큰 경우) 호출 스택의 제한된 메모리를 초과하여 에러가 발생할 수 있다.
• 디버깅 어려움: 호출 스택을 추적해야 하므로 반복문에 비해 디버깅이 까다로울 수 있다.

JavaScript 예시 (팩토리얼 계산):

활용 예시:

• 팩토리얼(Factorial), 피보나치 수열(Fibonacci sequence) 계산
• 트리(Tree)나 그래프(Graph) 자료구조 순회 (깊이 우선 탐색 - DFS)
• 분할 정복(Divide and Conquer) 알고리즘 (ex: 병합 정렬, 퀵 정렬)
• JSON 파싱, DOM 탐색 등 중첩된 구조를 다룰 때