데이터 구조와 알고리즘 관련 개념 정리

키워드 : 스택, 큐, 해시맵, 트리, 그래프, 시간 복잡도, 정렬 알고리즘

1. Object의 특성에 따라 나뉘는 데이터 구조

   • 순서를 유지해야 하는 경우
     객체를 삽입한 순서대로 유지하거나 특정 순서대로 정렬해야 하는 경우 사용
     • 배열 (Array)
       • 고정 크기의 데이터 저장.
       • 빠른 인덱스 접근 가능.
       • 순서 유지, 중복 허용.
     • 리스트 (List)
       • 순서 유지, 중복 허용.
       • 가변 크기의 배열이나 연결 리스트로 구현됨.
       • 구현체: ArrayList, LinkedList.
     • 링크드리스트 (LinkedList)
       • 양방향 연결 리스트로 구현.
       • 삽입/삭제가 빈번한 경우 효율적.
       • 순서 유지, 중복 허용.
   • 중복을 허용하지 않는 경우
     객체가 고유해야 하는 경우 사용
     • 셋 (Set)
       • 중복 허용하지 않음.
       • 순서와 관계없이 유일한 요소를 저장.
       • 구현체: HashSet, LinkedHashSet, TreeSet.
     • 트리셋 (TreeSet)
       • 중복 허용하지 않고, 정렬된 순서로 저장.
   • 키-값 쌍으로 데이터를 저장해야 하는 경우
     객체를 키와 값의 쌍으로 저장하고, 키를 기준으로 데이터를 빠르게 검색해야 할 때 사용
     • 맵 (Map)
       • 키-값 쌍으로 데이터를 저장.
       • 키는 중복되지 않아야 하며, 값은 중복 가능.
       • 구현체: HashMap, LinkedHashMap, TreeMap.
     • 트리맵 (TreeMap)
       • 키를 기준으로 정렬된 상태로 유지.
   • 객체의 우선순위를 정의해야 하는 경우
     객체의 우선순위나 정렬 기준이 중요할 때 사용
     • 우선순위 큐 (PriorityQueue)
       • 우선순위를 기준으로 가장 높은 우선순위의 요소를 빠르게 검색 및 제거.
       • 내부적으로 힙(Heap) 구조를 사용.
   • 스택 또는 큐 구조가 필요한 경우
     후입선출(LIFO) 또는 선입선출(FIFO)의 구조가 필요할 때 사용
     • 스택 (Stack)
       • 후입선출(LIFO) 구조.
     • 큐 (Queue)
       • 선입선출(FIFO) 구조.
       • 구현체: LinkedList 또는 ArrayDeque.
     • 덱 (Deque)
       • 양방향 삽입 및 삭제 가능.
       • 구현체: ArrayDeque.

2. 스택(Stack)과 큐(Queue)의 차이점과 실제로 사용되는 사례

   • 스택 : 데이터를 쌓아올린 형태의 자료구조로, 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고 top을 통해서만 접근 가능. push/pop. 후입선출 구조(LIFO : last in last out)
     • 예시 : 웹 브라우저의 방문기록(뒤로가기), 역순 문자열 만들기, 실행 취소(가장 나중에 실행된 것부터 취소)
   • 큐 : 한쪽 끝에서 삽입이, 다른 쪽 끝에서 삭제가 양쪽으로 이루어진다. 선입선출 구조(FIFO : first in first out)
     • 예시 : 데이터가 입력된 시간 순서대로 처리해야할 필요가 있는 경우 → 은행 업무, BFS(너비 우선 탐색), 캐시 구현

3. 연결 리스트(Linked List)의 구조와 사용 사례

   • 배열 : 정적 자료구조로, 배열은 크기가 정해져 있어서 해당 크기만큼 연속된 메모리 주소를 할당받는다. 그러므로 인덱스를 갖는다. 크기를 수정이 불가능

   • 연결 리스트 : 동적 자료구조로, 크기를 정할 필요 없으며 배열처럼 연속된 메모리 주소를 할당받지 않는다. 대신 노드가 있고 그 노드안에 데이터가 있고 다음 데이터를 가리키는 주소를 가지고 있다. 데이터의 추가/삭제가 자유롭다. 데이터 탐색시 임의로 접근이 불가능하여 순차적으로 접근해야 한다.

     • 예시 : 웹 브라우저 앞/뒤로가기, 음악 스트리밍 사이트

4. 배열(Array)과 연결 리스트(Linked List)의 차이점과 시간 복잡도

   특징	배열(Array)	연결 리스트(Linked List)
   구조	메모리에 연속된 공간에 저장	각 노드가 포인터를 통해 연결된 구조
   크기 조정	고정 크기(크기 변경이 어렵다, 동적 배열 제외)	동적으로 크기 조정 가능
   메모리 사용	추가 메모리 필요 없음	각 노드에 데이터 + 포인터 저장 공간 필요
   데이터 접근	인덱스(index)를 통해 즉시 접근 가능	첫 노드부터 순차적으로 탐색해야 함
   삽입/삭제	중간에서 삽입/삭제 시 비용 높음 (데이터 이동 필요)	연결된 포인터만 수정하므로 비교적 효율적

   • 시간복잡도 비교

     연산	배열 (Array)	연결 리스트 (Linked List)
     접근 (Access)	O(1) (인덱스로 바로 접근 가능)	O(n) (순차 탐색 필요)
     검색 (Search)	O(n) (순차 검색)	O(n) (순차 검색)
     삽입 (Insert)	O(n) (중간 삽입 시 이동 필요)	O(1) (처음/끝에 삽입 시) O(n) (중간 삽입 시 탐색 포함)
     삭제 (Delete)	O(n) (중간 삭제 시 이동 필요)	O(1) (처음/끝에서 삭제 시) O(n) (중간 삭제 시 탐색 포함)

     → 배열은 빠른 접근과 간단한 메모리 구조일 경우 유리, 연결 리스트는 크기가 변동되거나 삽입/삭제가 빈번한 경우 적합하다.
     

5. 해시맵(HashMap)과 트리(Tree)의 차이점과 사용 사례

   • 해시맵 : 가장 흔히 쓰이는 map 컬렉션으로, 데이터를 key-value 쌍으로 저장하는 Entry 객체를 저장하는 자료구조. 해싱(hashing, 해시 함수에 문자열 입력값을 넣어서 특정한 값으로 추출하는 것)에서 알 수 있듯 많은 양의 데이터를 검색하는데 성능이 좋다.
     • 예시 : 데이터에 빠르게 접근해야하는 경우 → 캐싱 시스템, 데이터 매핑, 카운터/빈도 분석, 임시 저장소(데이터간 순서 중요하지 않은 빠른 조회가 필요할 때)
   • 트리 : 그래프의 일종으로, 노드와 간선으로 이루어진 비선형, 계층적 자료구조.
     • 예시 : 정렬이 필요하거나 범위검색이 필요한 경우 적합 → 파일이나 폴더, 힙, 효율적인 검색(인덱싱) 구현, 로그 시스템, 순위 관리(성적 순위표, 리더보드), 이벤트 스케줄링

6. 트리(Tree)와 그래프(Graph)의 차이점과 장단점

   특징	트리(Tree)	그래프(Graph)
   구조	계층적 구조(부모-자식 관계)	네트워크 구조(노드 간의 자유로운 연결)
   루트 노드	항상 하나의 루트 노드 존재	루트 노드 없음 (자유로운 연결 가능)
   엣지 개수	항상 n-1개의 엣지 (n은 노드 개수)	최대 (n(n-1))/2개의 엣지 가능
   사이클	사이클이 존재하지 않음	사이클이 존재할 수 있음
   연결 상태	항상 연결 그래프 (모든 노드가 연결됨)	연결될 수도 있고 연결되지 않을 수도 있음
   방향성	일반적으로 방향 그래프(Directed)	방향성 그래프 또는 비방향성 그래프 가능

   • 트리 : 그래프의 한 종류 → 트리는 사이클이 없는(=방향성이 없는) 하나의 연결그래프이다.
     • 장점 : 효율적 데이터의 탐색이 가능, 계층적/구조적으로 데이터를 표현하기 적합, 메모리 효율성
     • 단점 : 제약된 연결, 삽익과 삭제의 제한, 복잡한 재구성
   • 그래프 : 정점과 간선으로 이루어진 비선형 데이터 구조.
     • 장점 : 복잡한 관계 표현 가능, 다양한 알고리즘 활용 가능, 유연성(연결 제약 없는 형태)
     • 단점 : 복잡한 구현, 탐색 비용 증가, 사이클 관리 어려움

7. 빅오(Big-O) 표기법과 시간 복잡도
   알고리즘 성능을 분석할 때 사용되는 표기법으로, 입력 크기에 따라 알고리즘의 수행 시간이나 공간 사용량이 어떻게 증가하는지를 표현한다. 최악의 경우를 기준으로 표현하며 상수의 가장 큰 영향을 미치는 향으로 시간 복잡도를 나타낸다.

   • 빅오 표기법의 예시

     시간 복잡도	설명	예시
     O(1)	입력 크기에 상관없이 일정한 시간 소요	배열에서 특정 인덱스 접근
     O(log n)	입력 크기가 커질수록 느리게 증가	이진 탐색
     O(n)	입력 크기에 비례하여 수행 시간 증가	단순 반복문
     O(n log n)	반복문 안에 로그 성격의 작업이 포함됨	병합 정렬(Merge Sort), 퀵 정렬(Quick Sort)
     O(n²)	중첩된 반복문으로 인해 제곱에 비례	버블 정렬(Bubble Sort), 선택 정렬
     O(2ⁿ)	입력 크기가 커질수록 시간 폭발적으로 증가	피보나치 재귀 알고리즘

   • 배열

     연산	시간 복잡도
     접근	O(1)
     검색	O(n)
     삽입 (중간)	O(n)
     삭제 (중간)	O(n)

   • 연결리스트

     연산	시간 복잡도
     접근	O(n)
     검색	O(n)
     삽입 (처음/끝)	O(1)
     삭제 (처음/끝)	O(1)

   • 스택(Stack) & 큐(Queue)

     연산	시간 복잡도
     삽입	O(1)
     삭제	O(1)
     검색	O(n)

   • 해시 테이블(Hash Table)

     연산	평균 시간 복잡도	최악 시간 복잡도
     검색	O(1)	O(n)
     삽입	O(1)	O(n)
     삭제	O(1)	O(n)

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

     연산	평균 시간 복잡도	최악 시간 복잡도
     검색	O(log n)	O(n)
     삽입	O(log n)	O(n)
     삭제	O(log n)	O(n)

   • 힙(Heap)

     연산	시간 복잡도
     삽입	O(log n)
     삭제(최댓값/최솟값)	O(log n)
     검색	O(n)

   • 그래프(Graph)

     • 인접 행렬 (Adjacency Matrix)

       연산	시간 복잡도
       간선 추가/삭제	O(1)
       간선 확인	O(1)
       전체 탐색	O(V²)

     • 인접 리스트 (Adjacency List)

       연산	시간 복잡도
       간선 추가/삭제	O(1)
       간선 확인	O(V)
       전체 탐색	O(V + E)

8. 이진 탐색(Binary Search) 알고리즘과 시간 복잡도
   정렬된 자료를 반으로 계속해서 나눠서 탐색하는 방법, 시간 복잡도는 O(logN)이다.

9. 정렬 알고리즘 중 퀵 정렬(Quick Sort)과 병합 정렬(Merge Sort)의 차이점과 시간 복잡도
   퀵 정렬과 병합 정렬은 둘 다 분할 정복 방식을 사용하는 효율적인 정렬 알고리즘이다.

   • 퀵 정렬 : 분할 정복 기법과 재귀 알고리즘을 이용한 정렬 알고리즘. 기준값(pivot)을 중심으로 자료를 왼쪽 부분집합과 오른쪽 부분집합으로 분할한다. 왼쪽 부분집합으로 기준값보다 작은 원소를 이동시키고, 오른쪽 부분집합으로 기준값보다 큰 원소를 이동시킨다. 이렇게 분할과 정복을 반복하여 수행한다.
     1. 배열에서 기준점(pivot)을 하나 선택합니다.
     2. 기준점을 기준으로 작은 값들은 왼쪽, 큰 값들은 오른쪽에 배치합니다.
     3. 분할된 두 부분 배열에 대해 재귀적으로 동일한 작업을 수행합니다.
     4. 부분 배열의 크기가 1 이하가 되면 정렬이 완료됩니다.
     • 시간복잡도 : 평균(O(nlogn)), 최악 (O(n2)), 최선(O(nlogn))
   • 병합 정렬 : 퀵정렬과 마찬가지로 분할 정복 방법을 통해 정렬된다. 퀵 정렬과 비슷하지만 안정 정렬이다.
     1. 배열을 균등하게 두 부분으로 나눕니다.
     2. 각 부분을 재귀적으로 정렬합니다.
     3. 정렬된 두 부분 배열을 병합하여 하나의 정렬된 배열로 만듭니다.
     • 시간복잡도 : 평균, 최악, 최선 (O(nlogn))

10. 그래프에서 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)의 차이점과 사용 사례

    • 깊이 우선 탐색(DFS) : 한 경로를 끝까지 탐색한 후, 다른 경로를 탐색한다. 스택이나 재귀를 통해 구현한다.
      • 메모리가 효율적이며 경로를 탐색하는데 적합하다.
      • 예시 : 미로 탐색, 사이클 검출, 연결 요소 탐색
    • 너비 우선 탐색(BFS) : 현재 노드와 인접한 모든 노드를 방문한 뒤, 다음 깊이의 노드들을 탐색한다. 큐를 사용하여 구현한다.
      • 최단 경로가 보장되며, 메모리 소비가 커질 수 있고, 계층적 탐색에 적합하다
      • 예시 : 최단 경로 검색, 네트워크 분석, 차수 탐색, 검색 알고리즘