[자료구조 기초] 자료 구조란?

자료구조 (Data Structure)

자료 구조란 메모리 상 데이터를 저장·조직·액세스하는 방식과 그 위에서 수행할 연산의 집합(추상적 규약)이다. 쉽게 말해서, 메모리를 데이터를 저장하는 창고라고 한다면, 자료구조는 창고를 정리하기 위한 규칙서 정도이다.

단, 단순히 “저장 방식”이 아니라, 그 위에서 가능한 연산들의 집합(추상적 규약)까지 포함한다.

• 예: 배열은 "인덱스로 O(1) 접근 가능, 크기 고정"이라는 규약을 가진 구조.

왜 자료구조가 중요한가?

자료 구조가 중요한 이유는 다음 세 가지 차원에서 설명할 수 있다.

• 효율성: 같은 문제를 해결하더라도 어떤 자료 구조를 쓰느냐에 따라 실해행 시간이 달라지게 된다.
• 안정성: 잘못된 자료 구조 선택은 불필요한 메모리 낭비나 성능 저하를 유발할 수 있다.
• 확장성 및 유지보수성: 프로그램 규모가 커질수록 데이터 관리가 핵심이기에 , 개발 시 자료 구조에 대한 이해가 필요하다.

자료구조와 알고리즘의 관계

알고리즘은 문제를 푸는 절차이고, 자료 구조는 그 절차를 해 나가기 위해 필요한 데이터의 저장, 접근, 조작 방식이다. 실제로 코딩 테스트 문제를 해결하기 위해서는 "어떤 알고리즘을 사용할 것인지", "어떤 자료 구조를 사용할 것인지"만 해결 된다면 문제는 거의 푼 것인 다름 없다.

코딩 테스트 뿐만 아니라 실무에서도 역시 중요하게 고려되는 요소이다. 실무에서는 알고리즘 ↔ ADT ↔ 구체적 자료구조를 계층으로 나눠 고른다고 이해하면 쉽다.

• 문제 → ADT 파악: 필요한 연산 규약(삽입/삭제/탐색/우선순위 등)을 먼저 정한다.
• ADT → 자료구조 매핑: 그 연산을 평균적으로 가장 싸게 만드는 저장 방식 선택.
• 세부 최적화: 데이터 분포(균일/편향), 데이터 크기, 변경 빈도, 캐시/메모리 제약을 반영.

관련된 내용을 GPT한테 물어보니 다음과 같은 예시를 제시해 주었다:

Membership/탐색

• 정렬된 배열 + 이분 탐색: O(log n) 탐색, 연속 메모리라 캐시 친화적. 삽입/삭제 빈번하면 비추.
• 균형 이진트리(RB-tree 등): O(log n) 삽입/삭제/탐색 균형. 포인터 추적 → 캐시 미스 증가.
• 해시(해시맵): 평균 O(1) 탐색/삽입/삭제. 키 분포/해시 품질/리사이즈 비용, 메모리 오버헤드 고려.

스케줄링/가장 작은 값 자주 꺼내기

• 최소 힙(우선순위 큐): push/pop 모두 O(log n). 스캔 O(n)보다 일관되게 유리.

슬라이딩 윈도우 최대/최소

• 모노토닉 덱: 전체 O(n). 단순 매번 스캔(윈도우 크기 k)은 O(nk)로 급격히 느림.

그래프

• 인접 리스트: 희소 그래프에 유리. BFS(큐), DFS(스택) 기본.
• 인접 행렬: 밀집 그래프/빠른 간선 존재 확인에 유리. 메모리 O(n^2) 감수.
• 최단거리: 다익스트라(우선순위 큐), A*는 휴리스틱 + 우선순위 큐.

요약

정리하자면, 자료구조는 데이터를 저장·조직·접근하는 규칙이고, 알고리즘은 그 데이터를 활용해 문제를 푸는 절차이다. 효율적인 알고리즘을 구현하기 위해서는 반드시 적절한 자료구조가 뒷받침되어야 하며, 이는 단순한 코딩 테스트뿐만 아니라 실무 서비스의 성능과 안정성에도 직결된다.

앞으로의 시리즈에서는 배열, 연결 리스트, 스택, 큐 등 구체적인 자료구조를 하나씩 살펴보고, 각 자료구조가 어떤 상황에서 강점과 약점을 가지는지, 그리고 어떤 알고리즘과 결합될 때 최적의 성능을 발휘하는지 다뤄볼 예정이다.