[스터디11] 3. 자료구조

목차

CHAPTER 04 자료구조

: 어떠한 구조로 데이터를 다룰지에 대해 학습하는 과목

1. 자료구조의 큰 그림

• 자료구조(Data Structure): 데이터를 효율적으로 저장하고 관리하는 방법
• 알고리즘(Algorithm): 어떤 목적을 이루기 위해 필요한 일련의 연산 절차

어떤 자료구조를 사용하느냐에 따라 적용 가능한 알고리즘이 달라질 수 있기 때문에 둘은 깊은 연관성을 가진다.

시간 복잡도와 공간 복잡도

: 소스 코드나 프로그램이 얼마나 효율적인지를 판단하는 척도

• 시간 복잡도(Time Complexity) : 입력의 크기에 따라 프로그램 실행 시간이 어떻게 변하는지를 나타냄 (연산 횟수에 비례)
• 공간 복잡도(Space Complexity) : 프로그램 실행에 필요한 메모리 자원의 양

빅오 표기법(Big-O Notation)

: 입력 크기가 무한대로 커질 때 실행 시간(또는 메모리 사용량)이 증가하는 한계, 즉 점근적 상한을 나타낸다.

• 최고차항의 차수만을 고려
• 계수와 낮은 차수의 항은 무시
• 예: 실행 횟수가 3n² + 2n + 1 → 시간복잡도는 n²에 비례, O(n²)

2. 배열과 연결 리스트

1) 배열(Array)

: 일정한 메모리 공간에 여러 요소가 순차적으로 나열된 자료구조로, 각 요소는 인덱스(index)를 통해 식별된다.

연산	시간 복잡도	설명
접근 및 수정	O(1)	인덱스를 통해 직접 접근 가능
검색	O(n)	처음부터 순차적으로 탐색
삽입 및 삭제	O(n)	중간에 요소를 추가하거나 삭제하면 이후 요소들을 이동

 

장점

• 빠른 접근 속도 (인덱스 활용)
• 메모리 효율성

단점

• 크기가 고정적
• 중간 삽입/삭제 시 비효율적

2) 연결 리스트(Linked List)

: 데이터와 다음 노드의 위치 정보를 담고 있는 노드(node)들의 모음으로 구성된 자료구조로, 메모리상에 불연속적으로 저장될 수 있다.

연산	시간 복잡도	설명
접근 및 검색	O(n)	첫 번째 노드(헤드)부터 순차적으로 탐색
삽입 및 삭제	O(1)	특정 위치가 주어지면 포인터만 변경

 

연결 리스트의 종류

• 싱글 연결 리스트: 단방향으로만 탐색이 가능
• 이중 연결 리스트: 이전 노드의 정보도 포함하여 양방향 탐색이 가능
• 환형 연결 리스트: 마지막 노드가 첫 노드를 가리키는 원형 구조

3. 스택과 큐

1) 스택(Stack)

: 한쪽 끝에서만 데이터의 삽입과 삭제가 일어나는 자료구조로, 후입선출(LIFO, Last-In-First-Out) 구조를 가진다.

 

주요 연산

• push: 스택의 맨 위에 요소 삽입
• pop: 스택의 맨 위 요소 삭제 및 반환
• peek/top: 스택의 맨 위 요소 확인 (삭제하지 않음)

시간 복잡도: 모든 기본 연산이 O(1)

 

활용 예시

• 함수의 호출 정보 저장
• 웹 브라우저의 '뒤로가기' 기능
• 괄호 매칭 검사
• 계산기의 수식 계산

2) 큐(Queue)

: 한쪽 끝에서 데이터를 삽입하고 다른 쪽 끝에서 삭제하는 자료구조로, 선입선출(FIFO, First-In-First-Out) 구조를 가진다.

 

주요 연산

• enqueue: 큐의 뒤쪽에 요소 삽입
• dequeue: 큐의 앞쪽 요소 삭제 및 반환
• front: 큐의 앞쪽 요소 확인 (삭제하지 않음)

시간 복잡도: 모든 기본 연산이 O(1)

 

활용 예시

• 데이터 처리 대기열(버퍼)
• 프로세스 스케줄링
• BFS(너비 우선 탐색) 구현

4. 해시 테이블(Hash Table)

: 키(Key)와 값(Value)을 하나의 쌍으로 저장하는 자료구조로, 키를 해시 함수(Hash Function)에 입력하여 얻은 해시 값(인덱스)을 통해 값이 저장된 버킷(bucket)에 빠르게 접근할 수 있다.

장점

• 일반적인 상황에서 검색, 삽입, 삭제 연산의 시간 복잡도가 O(1)로 매우 빠름

단점

• 메모리 공간을 많이 소모
• 해시 충돌이 발생할 수 있음

해시 충돌(Hash Collision)

: 서로 다른 키가 같은 해시 값을 갖는 상황

 

해결 방법

• 체이닝(Chaining): 충돌이 발생한 데이터를 연결 리스트로 연결
• 개방 주소법(Open Addressing): 충돌 발생 시 다른 비어있는 버킷을 찾아 데이터를 저장
  • 선형 조사법
  • 이차 조사법
  • 이중 해싱

활용 예시

• 데이터베이스 인덱싱
• 캐시 시스템
• 중복 검사

5. 트리(Tree)

: 계층적인 구조를 표현하는 데 사용되는 자료구조로, 데이터가 저장된 노드(node)와 이를 연결하는 간선(edge)으로 구성된다.

 

트리의 구성 요소

• 루트 노드(Root Node): 트리 최상위 노드
• 리프 노드(Leaf Node): 자식이 없는 최하단 말단 노드
• 부모 노드(Parent Node): 특정 노드의 상위 노드
• 자식 노드(Child Node): 특정 노드의 하위 노드
• 형제 노드(Sibling Node): 같은 부모 노드를 공유하는 노드

트리 순회(Tree Traversal)

모든 노드를 한 번씩 방문하는 방법

• 전위 순회 : 루트 → 왼쪽 서브트리 → 오른쪽 서브트리
• 중위 순회 : 왼쪽 서브트리 → 루트 → 오른쪽 서브트리
• 후위 순회 : 왼쪽 서브트리 → 오른쪽 서브트리 → 루트

트리의 종류

1) 이진 트리(Binary Tree)

: 자식 노드가 2개 이하인 트리

 

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

: 왼쪽 서브트리는 부모보다 작은 값, 오른쪽 서브트리는 큰 값을 가지는 이진 트리

• 탐색 속도가 빠름 (평균 O(log n))
• 정렬된 상태를 유지

 

3) 힙(Heap)

: 최댓값이나 최솟값을 빠르게 찾기 위한 완전 이진 트리

• 최대 힙 : 부모 노드가 자식 노드보다 큰 값
• 최소 힙 : 부모 노드가 자식 노드보다 작은 값

 

4) RB 트리(Red-Black Tree)

: 삽입/삭제 시 스스로 균형을 맞춰 편향을 방지하는 자가 균형 이진 탐색 트리

 

5) B 트리

: 하나의 노드가 여러 자식 노드를 가질 수 있는 다진 탐색 트리

• 데이터베이스나 파일 시스템처럼 대용량 데이터 처리에 사용

6. 그래프(Graph)

: 정점(vertex)과 이를 연결하는 간선(edge)으로 이루어진 연결 관계를 표현하는 자료구조로, 데이터 간의 연결 관계를 표현하는 데 쓰인다.

트리와 일반적인 그래프의 차이

• 트리: 사이클을 형성하지 않고 연결된 노드 간 상하 관계를 갖음
• 일반적인 그래프: 사이클을 형성할 수 있으며, 이웃한 정점끼리 상하 관계를 갖지 않음

그래프 탐색

: 모든 정점을 한 번씩 방문하는 방법

 

1)깊이 우선 탐색(DFS, Depth First Search)

: 최대한 깊이 들어간 후, 더 이상 갈 곳이 없으면 돌아와 다른 경로를 탐색

• 구현 방법: 스택 또는 재귀 함수 사용
• 시간 복잡도: O(V + E) (V: 정점 수, E: 간선 수)
• 활용 예시: 미로 찾기, 경로 존재 여부 확인

 

2) 너비 우선 탐색(BFS, Breadth First Search)

: 시작 정점과 인접한 정점들을 먼저 모두 방문한 후, 그 다음 인접한 정점들을 방문하는 방식으로 넓게 탐색

• 구현 방법 : 큐 사용
• 시간 복잡도 : O(V + E)
• 활용 예시 : 최단 경로 문제, 네트워크 연결 확인

 

3) 최단 경로 알고리즘

: 한 정점에서 다른 정점까지 가는 경로 중 가중치의 합이 최소인 경로를 찾는 알고리즘

 

4) 다익스트라 알고리즘(Dijkstra's Algorithm)

: 간선의 가중치가 음수가 아닐 때, 특정 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘

• 동작 과정
  1. 최단 거리 테이블을 무한대로 초기화 (시작 정점은 0)
  2. 방문하지 않은 정점 중 최단 거리가 가장 작은 정점을 선택
  3. 선택한 정점을 거쳐 다른 정점으로 가는 비용 계산
  4. 최단 거리 테이블 갱신
  5. 모든 정점을 방문할 때까지 2~4 과정 반복
• 시간 복잡도: O(V²) 또는 O((V+E)logV) (우선순위 큐 사용 시)
• 활용 예시
  • 지도 서비스의 최단 경로 찾기
  • 네트워크 라우팅
  • 게임에서의 경로 탐색

기술 면접 질문

• 시간 복잡도와 빅오 표기법의 차이점을 설명해주세요.
• 배열 대신 연결 리스트를 쓰는 것이 유리한 경우에 대해서 설명해주세요.
• DFS와 BFS의 차이점을 설명해주세요.
• B 트리란 무엇이며 왜 사용하는지 설명해주세요.

 

이 글은 『 이것이 취업을 위한 컴퓨터 과학이다 with CS 기술 면접』 책을 읽고 학습한 내용을 정리한 것입니다.