자료구조(배열, (연결)리스트, 스택, 큐), 시간 복잡도, 공간 복잡도 정리

자료구조, 시간 복잡도, 공간 복잡도 정리

알고리즘 효율성 분석과 주요 자료구조 총정리

1. 시간 복잡도와 공간 복잡도 설명

시간복잡도 (Time Complexity)

시간복잡도는 알고리즘이 실행되는 데 필요한 시간을 측정하는 방법으로, 입력 크기에 따른 연산 횟수를 나타냅니다.

점근적 표기법

표기법	의미	설명
빅오(Big-O)	최악의 경우/상한선	알고리즘이 실행되는 데 필요한 최대 시간을 나타냄 (가장 많이 사용)
빅오메가(Big-Ω)	최선의 경우/하한선	알고리즘이 실행되는 데 필요한 최소 시간을 나타냄
빅세타(Big-Θ)	평균/평균적 경우	알고리즘의 상한과 하한이 동일할 때 사용 (점근적으로 동일한 상한과 하한)

대표적인 시간 복잡도

복잡도	설명	예시
O(1)	상수 시간	배열의 인덱스 접근
O(log n)	로그 시간	이진 검색
O(n)	선형 시간	배열 순회
O(n log n)	선형로그 시간	효율적인 정렬 알고리즘
O(n²)	제곱 시간	이중 반복문
O(2ⁿ)	지수 시간	부분집합 생성
O(n!)	팩토리얼 시간	순열 생성

공간 복잡도 (Space Complexity)

공간 복잡도는 알고리즘이 실행되는 동안 필요한 메모리 공간을 측정하는 방법으로, 입력 크기에 따른 메모리 사용량을 나타냅니다.

공간복잡도	설명	예시
O(1)	상수 공간	변수 몇 개만 사용하는 알고리즘
O(log n)	로그 공간	이진 검색, 특정 분할 정복 알고리즘
O(n)	선형 공간	입력 크기만큼의 배열 사용
O(n log n)	선형로그 공간	특정 정렬 알고리즘(합병 정렬의 구현에 따라)
O(n²)	제곱 공간	2차원 배열, 인접 행렬
O(2ⁿ)	지수 공간	모든 부분집합 저장
O(n!)	팩토리얼 공간	모든 순열 저장

2. 배열 (Array)

정의 및 개념

배열은 동일한 타입의 데이터가 연속적인 메모리 공간에 저장되는 자료구조입니다. 인덱스를 통해 원소에 직접 접근이 가능합니다.

필수 연산

• 인덱스를 통한 접근 (Access)
• 원소 추가 (Insertion)
• 원소 삭제 (Deletion)
• 원소 검색 (Search)
• 원소 수정 (Update)

구현 방법 (Python)

Python - 배열 구현

# Python에서는 리스트가 동적 배열로 구현되어 있음
# 배열 선언
arr = [0] * 10  # 크기가 10인 배열 초기화

# 접근
element = arr[5]  # 인덱스 5의 요소 접근

# 삽입
arr.append(100)  # 배열 끝에 요소 추가
arr.insert(2, 50)  # 인덱스 2 위치에 50 삽입

# 삭제
arr.pop()  # 마지막 요소 제거
arr.pop(3)  # 인덱스 3의 요소 제거
arr.remove(50)  # 값이 50인 첫 번째 요소 제거

# 검색
index = arr.index(100)  # 값이 100인 요소의 인덱스 찾기
exists = 100 in arr  # 값이 100인 요소가 존재하는지 확인

# 수정
arr[4] = 200  # 인덱스 4의 요소를 200으로 수정
            

시간복잡도 및 공간복잡도

연산	시간복잡도 (최선)	시간복잡도 (평균)	시간복잡도 (최악)	공간복잡도
선언	O(n)	O(n)	O(n)	O(n)
접근	O(1)	O(1)	O(1)	O(1)
검색	O(1)	O(n/2)	O(n)	O(1)
삽입 (끝)	O(1)	O(1)	O(n) (재할당 시)	O(1)
삽입 (중간)	O(n)	O(n)	O(n)	O(1)
삭제 (끝)	O(1)	O(1)	O(1)	O(1)
삭제 (중간)	O(n)	O(n)	O(n)	O(1)
수정	O(1)	O(1)	O(1)	O(1)

다른 자료구조와의 비교

• 장점: 인덱스를 통한 빠른 접근(O(1)), 구현이 간단
• 단점: 크기가 고정되어 있거나 동적 확장 시 비용 발생, 중간 삽입/삭제가 비효율적
• 연결리스트와 비교: 접근은 빠르지만 삽입/삭제는 연결리스트가 더 효율적

3. 연결리스트 (Linked List)

정의 및 개념

연결리스트는 각 노드가 데이터와 다음 노드를 가리키는 포인터로 구성되어 있는 선형 자료구조입니다. 메모리에 연속적으로 저장되지 않고, 각 노드가 다음 노드의 위치를 가리키는 방식으로 연결됩니다.

필수 연산

• 노드 추가 (Insertion)
• 노드 삭제 (Deletion)
• 노드 검색 (Search)
• 노드 순회 (Traversal)

구현 방법 (Python)

Python - 연결리스트 구현

class Node:
    def __init__(self, data):
        self.data = data  # 노드 데이터
        self.next = None  # 다음 노드 참조

class LinkedList:
    def __init__(self):
        self.head = None  # 연결 리스트의 시작 노드(헤드)

    # 끝에 노드 추가
    def append(self, data):
        new_node = Node(data)

        if self.head is None:  # 빈 리스트인 경우
            self.head = new_node
            return

        current = self.head
        while current.next:  # 마지막 노드까지 이동
            current = current.next
        current.next = new_node

    # 중간에 노드 삽입
    def insert_at(self, position, data):
        if position == 0:  # 맨 앞에 삽입
            new_node = Node(data)
            new_node.next = self.head
            self.head = new_node
            return

        current = self.head
        for i in range(position-1):
            if current is None:
                return  # 위치가 리스트 범위를 벗어남
            current = current.next

        if current is None:
            return

        new_node = Node(data)
        new_node.next = current.next
        current.next = new_node

    # 노드 삭제
    def delete(self, data):
        if self.head is None:
            return

        if self.head.data == data:  # 삭제할 노드가 헤드인 경우
            self.head = self.head.next
            return

        current = self.head
        while current.next and current.next.data != data:
            current = current.next

        if current.next:  # 삭제할 노드를 찾은 경우
            current.next = current.next.next

    # 노드 검색
    def search(self, data):
        current = self.head
        position = 0

        while current:
            if current.data == data:
                return position
            current = current.next
            position += 1

        return -1  # 찾지 못한 경우

    # 리스트 출력
    def display(self):
        elements = []
        current = self.head

        while current:
            elements.append(current.data)
            current = current.next

        return elements
            

시간복잡도 및 공간복잡도

연산	시간복잡도 (최선)	시간복잡도 (평균)	시간복잡도 (최악)	공간복잡도
선언	O(1)	O(1)	O(1)	O(1)
접근	O(1)	O(n/2)	O(n)	O(1)
검색	O(1)	O(n/2)	O(n)	O(1)
삽입 (시작)	O(1)	O(1)	O(1)	O(1)
삽입 (끝)	O(1)	O(n)	O(n)	O(1)
삽입 (중간)	O(1)	O(n/2)	O(n)	O(1)
삭제 (시작)	O(1)	O(1)	O(1)	O(1)
삭제 (끝)	O(n)	O(n)	O(n)	O(1)
삭제 (중간)	O(1)	O(n/2)	O(n)	O(1)
수정	O(1)	O(n/2)	O(n)	O(1)

다른 자료구조와의 비교

• 장점: 동적 크기 조정, 효율적인 삽입/삭제(위치를 알고 있는 경우)
• 단점: 임의 접근 불가능, 순차적 접근으로 인한 검색 비효율, 추가 메모리 사용(포인터)
• 배열과 비교: 삽입/삭제는 효율적이지만 접근은 배열보다 느림
• 종류: 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트

4. 스택 (Stack)

정의 및 개념

스택은 Last-In-First-Out(LIFO, 후입선출) 방식을 따르는 선형 자료구조입니다. 데이터의 삽입과 삭제가 한쪽 끝(맨 위)에서만 이루어집니다.

필수 연산

• 삽입 (Push): 스택 맨 위에 요소 추가
• 삭제 (Pop): 스택 맨 위 요소 제거 및 반환
• 조회 (Peek/Top): 스택 맨 위 요소 반환(제거하지 않음)
• 비었는지 확인 (isEmpty): 스택이 비어있는지 확인

구현 방법 (Python)

리스트를 이용한 구현

Python - 리스트를 이용한 스택 구현

class Stack:
    def __init__(self):
        self.items = []  # 스택의 요소를 저장할 리스트

    def push(self, item):
        self.items.append(item)  # 요소 추가

    def pop(self):
        if not self.is_empty():
            return self.items.pop()  # 맨 위 요소 제거 및 반환
        return None

    def peek(self):
        if not self.is_empty():
            return self.items[-1]  # 맨 위 요소 반환 (제거하지 않음)
        return None

    def is_empty(self):
        return len(self.items) == 0  # 스택이 비어있는지 확인

    def size(self):
        return len(self.items)  # 스택 크기 반환
            

연결리스트를 이용한 구현

Python - 연결리스트를 이용한 스택 구현

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack:
    def __init__(self):
        self.top = None  # 스택의 맨 위 노드
        self.size = 0  # 스택 크기

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.top
        self.top = new_node
        self.size += 1

    def pop(self):
        if self.is_empty():
            return None

        data = self.top.data
        self.top = self.top.next
        self.size -= 1
        return data

    def peek(self):
        if self.is_empty():
            return None
        return self.top.data

    def is_empty(self):
        return self.top is None

    def get_size(self):
        return self.size
            

시간복잡도 및 공간복잡도

연산	시간복잡도 (최선)	시간복잡도 (평균)	시간복잡도 (최악)	공간복잡도
선언	O(1)	O(1)	O(1)	O(1)
Push	O(1)	O(1)	O(1)	O(1)
Pop	O(1)	O(1)	O(1)	O(1)
Peek	O(1)	O(1)	O(1)	O(1)
검색	O(1)	O(n/2)	O(n)	O(1)

다른 자료구조와의 비교

• 장점: 구현이 간단하고 빠른 삽입/삭제(O(1))
• 단점: 중간 요소에 직접 접근 불가, 검색에 비효율적
• 큐와의 비교: 스택은 LIFO, 큐는 FIFO 방식
• 활용: 함수 호출 스택, 괄호 검사, 역순 문자열, DFS 등에 사용

5. 큐 (Queue)

정의 및 개념

큐는 First-In-First-Out(FIFO, 선입선출) 방식을 따르는 선형 자료구조입니다. 한쪽 끝(rear)에서 삽입하고 다른 쪽 끝(front)에서 삭제가 이루어집니다.

필수 연산

• 삽입 (Enqueue): 큐의 뒤쪽(rear)에 요소 추가
• 삭제 (Dequeue): 큐의 앞쪽(front)에서 요소 제거 및 반환
• 조회 (Peek/Front): 큐의 앞쪽 요소 반환(제거하지 않음)
• 비었는지 확인 (isEmpty): 큐가 비어있는지 확인

구현 방법 (Python)

리스트를 이용한 구현

Python - 리스트를 이용한 큐 구현

class Queue:
    def __init__(self):
        self.items = []  # 큐의 요소를 저장할 리스트

    def enqueue(self, item):
        self.items.append(item)  # 뒤쪽에 요소 추가

    def dequeue(self):
        if not self.is_empty():
            return self.items.pop(0)  # 앞쪽에서 요소 제거 및 반환
        return None

    def peek(self):
        if not self.is_empty():
            return self.items[0]  # 앞쪽 요소 반환 (제거하지 않음)
        return None

    def is_empty(self):
        return len(self.items) == 0  # 큐가 비어있는지 확인

    def size(self):
        return len(self.items)  # 큐 크기 반환
            

연결리스트를 이용한 구현

Python - 연결리스트를 이용한 큐 구현

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Queue:
    def __init__(self):
        self.front = None  # 큐의 앞쪽 노드
        self.rear = None   # 큐의 뒤쪽 노드
        self.size = 0      # 큐 크기

    def enqueue(self, data):
        new_node = Node(data)

        if self.is_empty():  # 빈 큐인 경우
            self.front = new_node
            self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node

        self.size += 1

    def dequeue(self):
        if self.is_empty():
            return None

        data = self.front.data
        self.front = self.front.next

        if self.front is None:  # 마지막 요소를 제거한 경우
            self.rear = None

        self.size -= 1
        return data

    def peek(self):
        if self.is_empty():
            return None
        return self.front.data

    def is_empty(self):
        return self.front is None

    def get_size(self):
        return self.size
            

시간복잡도 및 공간복잡도

연산	시간복잡도 (최선)	시간복잡도 (평균)	시간복잡도 (최악)	공간복잡도
선언	O(1)	O(1)	O(1)	O(1)
Enqueue	O(1)	O(1)	O(1)	O(1)
Dequeue (리스트)	O(n)	O(n)	O(n)	O(1)
Dequeue (연결리스트)	O(1)	O(1)	O(1)	O(1)
Peek	O(1)	O(1)	O(1)	O(1)
검색	O(1)	O(n/2)	O(n)	O(1)

다른 자료구조와의 비교

• 장점: 순서가 보장되는 처리, 연결리스트로 구현 시 빠른 삽입/삭제
• 단점: 중간 요소에 직접 접근 불가, 리스트로 구현 시 dequeue 연산 비효율
• 스택과의 비교: 큐는 FIFO, 스택은 LIFO 방식
• 종류: 일반 큐, 원형 큐, 우선순위 큐, 덱(Deque)
• 활용: BFS, 작업 스케줄링, 프린터 대기열, 버퍼 등에 사용