[1주차] 자료구조

자료구조?

데이터를 효율적으로 저장하고, 관리하고, 처리하기 위한 구조

어떻게 담고, 꺼내고, 수정할지를 설계

 

필요한 이유?

▶ 효율성 : 같은 연산이라도 자료구조에 따라 속도가 다르다.

▶ 편리성 : 상황에 맞는 자료구조를 쓰면 코드가 단순해진다.

 

분류

선형 자료구조 (Linear) 데이터가 일렬로 나열된 구조	비선형 자료구조 (Non-Linear) 데이터가 계층적/네트워크적으로 연결된 구조
배열(Array) : 빠른 인덱스 접근	트리(Tree) : 부모-자식 관계 (예: 이진 탐색 트리, 힙)
연결 리스트(Linked List) : 삽입/삭제 용이	그래프(Graph) : 노드와 간선으로 연결된 구조 (예: 지도, SNS 친구 관계)
스택(Stack) : LIFO (후입선출)	해시(Hash Table) : 키(key)로 데이터에 빠르게 접근
큐(Queue) : FIFO (선입선출)
덱(Deque) : 양쪽에서 넣고 뺄 수 있음

 

선형 자료구조 (Linear)

1. 배열(Array)

 

• 인덱스를 이용해 O(1)로 접근 가능
• 하지만 크기가 고정되어 있고, 중간 삽입/삭제는 O(n)

 

 

1 - (1) 구간합 (= 누적합, Prefix Sum)

• 배열의 구간 합을 빠르게 계산하는 방법
• 미리 누적합 배열을 만들어두면 O(1)로 구간 합 계산 가능

 

1 - (2) 투 포인터 (Two Pointers)

• 두 개의 포인터(인덱스)를 움직이면서 문제 해결
• 정렬된 배열에서 두 수의 합, 부분 배열 문제 등에 자주 사용

 

1 - (3) 슬라이딩 윈도우 (Sliding Window)

• 일정한 크기의 창(윈도우)을 이동시키면서 연속된 부분 구간을 다루는 방식
• 예: 연속된 K개 원소의 최대합

 

2. 연결 리스트 (Linked List)

 

 

• 각 원소가 데이터 + 다음 노드 주소를 저장하는 구조
• 장점: 삽입/삭제 O(1) (포인터 변경만 하면 됨)
• 단점: 인덱스로 접근 불가 → 탐색 O(n)

 

3. 스택 (Stack)

 

• LIFO (Last In First Out) 구조 → 나중에 들어온 게 먼저 나감
• 주요 연산: push, pop, peek
• 주로 괄호 검사, DFS, 실행 취소 기능(Undo)

 

4. 큐 (Queue)

 

• FIFO (First In First Out) 구조 → 먼저 들어온 게 먼저 나감
• 주요 연산: enqueue, dequeue
• 주로 프로세스 스케줄링, BFS 탐색

 

5. 덱, 디큐 (Deque, Double-Ended Queue)

 

• 양쪽 끝에서 삽입/삭제 가능한 큐
• 스택+큐 기능을 모두 가짐
• 주로 슬라이딩 윈도우 최댓값 문제, 양방향 탐색

 

마치며

정처산기를 준비하면서 스택과 큐는 많이 본 것도 있고,

배열에서, 구간합이나, 투포인터, 슬라이딩 윈도우는 새롭게 느껴졌다.

다음에는 비선형도 이해하지