자료구조? 알고리즘? 뭐가 다른거야??

코딩테스트 문제를 풀면서 자료구조&알고리즘을 합쳐서 이론 공부를 했더니 각각을 구별해서 알아둘 필요가 있겠다 싶었다. 스택, 큐, BFS, DFS, 연결 리스트 등 각각은 뭔지 아는데 어떻게 구분해야 하는지 헷갈렸다. 

어쨌든, 일단 자료구조와 알고리즘의 개념을 먼저 공부하고 각각의 예시를 분류해보자. 

 

 

 

자료구조

자료구조는 데이터를 효율적으로 저장하고 관리하기 위한 방법이다. 데이터를 어떤 방식으로 정리하느냐에 따라 접근 속도나 사용 편의성이 달라지므로 문제를 보고 어떤 자료구조로 입력 데이터를 저장/처리할지 결정해야 한다. 

 

 

📚 배열 (Array)

예시: 사물함

• 번호가 붙어 있는 사물함처럼, 데이터를 연속된 공간에 저장한다. 
• 인덱스(번호)만 알면 데이터를 빠르게 찾을 수 있다.

👉 특징:
✅ 인덱스를 이용해 조회가 빠름 (O(1))
❌ 크기를 변경하려면 새로운 배열을 만들어야 함

 

 

 

🔗 연결 리스트 (Linked List)

예시: 기차 칸

• 기차 칸(노드)이 하나씩 연결된 구조
• 배열처럼 연속된 공간이 아니라, 필요할 때 새 칸을 추가할 수 있다.
• 하지만 중간에 있는 칸을 찾으려면 처음부터 순서대로 봐야 해서 속도가 느릴 수 있다. 

👉 특징:
✅ 데이터 추가/삭제가 빠름
❌ 특정 위치 찾을 때 느림

 

 

 

🍽 스택 (Stack)

예시: 접시 쌓기

• 새로운 접시는 위에 쌓고, 꺼낼 때도 위에서부터 꺼낸다. 
• LIFO (Last In, First Out, 나중에 들어간 게 먼저 나옴) 구조

👉 특징:
✅ 최근에 추가된 데이터를 빠르게 제거할 수 있음
❌ 중간 데이터를 바로 찾기는 어려움

 

 

 

🚏 큐 (Queue)

예시: 버스 정류장 줄 서기

• 먼저 줄 선 사람이 먼저 버스를 타는 구조
• FIFO (First In, First Out, 먼저 들어간 게 먼저 나옴) 구조

👉 특징:
✅ 순서대로 처리해야 하는 작업(프린터 대기열, 고객 응대 등)에 유용함
❌ 중간 데이터를 바로 찾기는 어려움

 

 

 

🔑 해시 테이블 (Hash Table, 딕셔너리)

예시: 전화번호부

• 사람 이름(키)을 입력하면 전화번호(값)를 빠르게 찾을 수 있다. 
• 내부적으로 해시 함수를 사용해서 데이터를 빠르게 검색할 수 있도록 정리돼 있다. 
• 파이썬에서는 dict이 해시 테이블과 해시 맵의 역할을 한다. 

👉 특징:
✅ 검색 속도가 빠름 (평균 O(1))
❌ 충돌이 발생하면 성능이 저하될 수 있음

 

 

 

🌳 이진 트리 (Binary Tree)

예시: 가족 트리

• 부모가 있고, 그 아래 두 자식이 있는 구조 (자식 노드가 최대 두 개)
• 데이터가 계층적으로 정리돼 있어서, 상위-하위 관계를 표현하기 좋다. 

👉 특징:
✅ 계층 구조를 표현할 때 유용함
❌ 균형이 안 맞으면 성능이 떨어질 수 있음

 

 

 

🔍 이진 탐색 트리 (Binary Search Tree, BST)

예시: 사전(알파벳 순 정렬)

• 이진 탐색 + 연결 리스트를 결합한 이진트리
• 왼쪽에는 작은 값, 오른쪽에는 큰 값을 저장하는 트리
• 정렬된 상태에서 빠르게 검색할 수 있다. 

👉 특징:
✅ 검색, 추가, 삭제가 평균적으로 빠름 (O(log N))
❌ 트리가 한쪽으로 쏠리면 (불균형하면) 성능이 떨어짐

 

 

 

⛰ 힙 (Heap)

예시: 우선순위가 있는 대기열 (응급실)

• 최대 힙(Max Heap): 가장 큰 값이 맨 위에 있다. (우선순위 높은 게 먼저 나옴).
• 최소 힙(Min Heap): 가장 작은 값이 맨 위에 있다.

👉 특징:
✅ 최댓값 또는 최솟값을 빠르게 찾을 수 있음 (O(1))
❌ 중간에 있는 값을 찾는 건 느림

 

 

 

🌍 그래프 (Graph)

예시: 지하철 노선도

• 정점(Node, 역)과 간선(Edge, 노선)으로 이루어진 구조
• 각 정점이 여러 개의 간선으로 연결될 수 있다.

👉 특징:
✅ 복잡한 관계(네트워크, 길 찾기)를 표현할 때 유용함
❌ 데이터 구조가 복잡할 수 있음

 

 

 

 

 

 

알고리즘

알고리즘은 자료구조를 통해 정리되어 저장된 데이터를 활용해 주어진 문제를 효율적으로 해결하기 위한 단계적 절차나 방법으로, 문제를 논리적으로 풀어나가는 계획이다. 알고리즘을 선택할 때에는 특히 시간 복잡도를 잘 고려해서 풀어야 한다. 알고리즘은 각각 따로 포스팅하도록 하고 일단은 예시만 적어둔다. 

1. 정렬 알고리즘
   1. 버블정렬
   2. 삽입정렬
   3. 선택정렬
   4. 합병정렬
   5. 퀵정렬
2. 탐색 알고리즘
   1. 이진 탐색 (Binary Search)
   2. 깊이 우선 탐색 (DFS)
   3. 너비 우선 탐색 (BFS)
3. 다이나믹 프로그래밍 (DP)
4. 그리디 (Greedy)
5. 분할 정복 (Divide and Conquer)
6. 백트래킹 (Backtracking)
7. 해싱 (Hashing)