자료구조와 알고리즘 기초 완벽 정리

왜 자료구조와 알고리즘인가

자료구조는 데이터를 조직하는 방법이고, 알고리즘은 문제를 해결하는 절차입니다. 40년간 소프트웨어를 개발해온 저로서는 이 둘이 프로그래밍의 기초 체력이라고 확신합니다. 프레임워크는 바뀌어도 자료구조와 알고리즘은 변하지 않습니다. 이를 제대로 이해하면 어떤 문제든 효율적으로 해결할 수 있습니다.

기본 자료구조

배열(Array)은 연속된 메모리에 저장되어 인덱스 접근이 O(1)입니다. 연결 리스트(Linked List)는 삽입/삭제가 O(1)이지만 탐색은 O(n)입니다. 스택(Stack)은 LIFO(후입선출), 큐(Queue)는 FIFO(선입선출) 구조입니다. 해시맵(HashMap)은 키로 값을 O(1)에 조회합니다. 각 자료구조의 장단점과 적합한 상황을 이해하세요.

트리와 그래프

트리는 계층 구조를 표현합니다. 이진 탐색 트리(BST)는 정렬된 데이터를 O(log n)에 탐색합니다. 힙(Heap)은 최대/최소값을 빠르게 찾습니다. 그래프는 노드와 간선으로 관계를 표현합니다. 인접 리스트와 인접 행렬로 구현합니다. BFS(너비 우선 탐색)와 DFS(깊이 우선 탐색)는 그래프 탐색의 기본입니다.

정렬과 탐색

버블 정렬, 선택 정렬은 O(n²)로 느립니다. 퀵소트, 머지소트는 O(n log n)으로 실용적입니다. 이진 탐색은 정렬된 배열에서 O(log n)에 원소를 찾습니다. 정렬과 탐색 알고리즘을 직접 구현해보세요. 내장 함수를 사용하더라도 원리를 알면 적절히 선택할 수 있습니다.

시간 복잡도와 공간 복잡도

Big O 표기법으로 알고리즘의 효율성을 나타냅니다. O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n). 시간과 공간은 트레이드오프 관계인 경우가 많습니다. 문제의 크기(n)를 고려하여 알고리즘을 선택합니다. 실제 성능은 상수 계수와 캐시 효과도 영향을 줍니다. 이론과 실전의 균형을 유지하세요.