자료구조, 알고리즘 필수

배열(Array)

• 연속된 메모리 공간에 데이터 저장
• 인덱스를 통해 O(1) 시간에 빠른 조회 가능
• 중간 삽입/삭제는 뒤 요소들을 옮겨야 하기 때문에 O(n) 비용 발생

➕ 장점

• 인덱스 기반 빠른 접근
• 메모리가 효율적이고 CPU 캐시 친화적

➖ 단점

• 크기 고정(동적 배열은 내부적으로 재할당 과정 필요함)
• 삽입/삭제가 느림

연결 리스트(Linked List)

• 요소(Node)가 포인터로 연결된 구조
• 삽입/삭제가 포인터 연결만 변경하면 되기 때문에 O(1) (해당 노드 알 때)
• 임의 접근 불가능 → 조회는 O(n)

➕ 장점

• 삽입/삭제가 빠름
• 크기 제한 없음

➖ 단점

• 조회가 느림
• 추가 포인터 저장으로 추가 메모리 사용
• 캐시 효율 낮음

스택(Stack)

• LIFO(Last-In, First-Out, 후입선출). 가장 나중에 들어간 데이터가 가장 먼저 나옴.
• 주요 연산: Push(데이터 추가), Pop(가장 위 데이터 제거 후 반환)
• 활용: 웹 뒤로 가기 기능, 함수 호출 스택, 재귀, DFS

큐(Queue)

• FIFO(First-In, First-Out, 선입선출). 가장 먼저 들어간 데이터가 가장 먼저 나옴.
• 주요 연산: Enqueue(데이터를 큐 뒤(Rear)에 추가), Dequeue(큐의 앞(Front)에 추가)
• 활용: 프린터 인쇄 대기열, 작업 스케줄링, BFS

힙(Heap)

• 완전 이진 트리 기반으로 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나(최대 힙, Max Heap), 항상 작은(최소 힙, Min Heap) 구조
• 시간 복잡도: 삽입=O(log n), 삭제(루트 제거)=O(log n), 조회(최댓값/최솟값)=O(1)
• 활용: 우선순위 큐(Priority Queue)를 구현할 때 주로 사용, 다익스트라, 힙 정렬

정렬 알고리즘

데이터를 일정한 순서(오름차순 or 내림차순)로 배열하는 알고리즘. 효율성은 주로 시간 복잡도로 측정된다.

퀵 정렬(Quick Sort)

• 배열 내에서 기준 원소(Pivot)를 선택하고, 피벗보다 작은 요소는 왼쪽으로, 큰 요소는 오른쪽으로 분할한 뒤, 각 부분 배열을 재귀적으로 정렬한다.
• 시간 복잡도: 최선/평균=O(nlogn), 최악=O(n^2)(피벗 선택이 매번 극단적일 때)
• 특징: 분할 정복(Divide and Conquer) 방식이며, 일반적으로 가장 빠르다.

병합 정렬(Merge Sort)

• 배열을 계속해서 절반으로 나누어 더 이상 나눌 수 없을 때까지 분할한 뒤, 분할한 배열들을 다시 정렬하며 합병(Merge)한다.
• 시간 복잡도: 최선/평균/최악=O(nlogn)
• 특징: 분할 정복 방식이며, 안정적인 정렬(Stable Sort)을 한다.

힙 정렬(Heap Sort)

• 주어진 데이터를 힙(주로 최대 힙)으로 구성한 뒤, 가장 큰 원소(루트 노드)를 꺼내(Pop) 배열의 끝에 배치하는 과정을 반복하여 정렬한다.
• 시간 복잡도: 최선/평균/최약=O(nlogn)
• 특징: 추가적 메모리 공간이 거의 필요 없는 제자리 정렬(In-place Sort) 방식이다.

정리

정렬	평균	최악	메모리	특징
퀵	n log n	n²	O(1)	매우 빠르며 실무 자주 사용
병합	n log n	n log n	O(n)	안정적, 병합 필요
힙	n log n	n log n	O(1)	메모리 적음, 실무 정렬엔 덜 사용