자료구조의 이해

자료구조란?
자료구조(Data Structure)는 데이터를 효율적으로 저장하고 관리하기 위해 조직하는 방법을 말합니다. 알고리즘과 함께 컴퓨터 과학의 핵심 주제 중 하나로, 적절한 자료구조 선택이 알고리즘의 성능을 크게 좌우합니다.

자료구조의 필요성
컴퓨터가 데이터를 처리할 때, 어떻게 데이터를 저장하고 접근할지를 결정하는 것이 매우 중요합니다. 자료구조의 선택은 효율적인 문제 해결을 위한 첫걸음이라 할 수 있습니다.

주요 자료구조 종류
배열 (Array), 리스트 (List), 스택 (Stack), 큐 (Queue)

배열은 고정된 크기의 연속된 메모리 공간에 데이터를 저장하는 자료구조입니다. 같은 타입의 데이터만 저장할 수 있으며, 특정 위치(인덱스)에 빠르게 접근할 수 있는 장점이 있습니다.

• 고정된 크기: 배열의 크기는 생성 시 정해지며 이후 변경할 수 없습니다.
• 인덱스를 통한 접근: 배열의 요소는 인덱스를 통해 직접 접근할 수 있어 시간 복잡도 O(1)로 접근이 가능합니다.
• 메모리 효율성: 데이터가 연속된 메모리 공간에 저장되어, 효율적인 메모리 사용이 가능합니다.

문제 설명: 주어진 배열에서 특정 값을 찾아 인덱스를 반환하는 프로그램을 작성하세요.

의사 코드:
입력: 배열 arr, 찾고자 하는 값 target
반복문 (i = 0부터 arr 길이까지):
    만약 arr[i] == target:
        return i
return -1  # 값이 없을 경우
                

Python 코드 예제:
def find_index(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

arr = [10, 20, 30, 40, 50]
print("찾는 값의 인덱스:", find_index(arr, 30))
                

리스트는 배열과 달리 크기가 가변적인 자료구조입니다. 데이터를 연속적으로 저장할 수도 있지만 링크드 리스트 형태로 분산된 메모리 공간에 저장할 수도 있습니다.

• 동적 크기: 리스트의 크기는 필요에 따라 자유롭게 변경될 수 있습니다.
• 삽입 및 삭제 용이: 배열에 비해 중간에 데이터를 삽입하거나 삭제하는 작업이 용이합니다.
• 순차 탐색: 인덱스를 통한 접근이 가능하지만, 링크드 리스트의 경우 인덱스를 사용하지 않고 순차 탐색을 합니다.

문제 설명: 주어진 리스트에 특정 값을 추가하거나 제거하는 프로그램을 작성하세요.

Python 코드 예제:
lst = [1, 2, 3, 4]
lst.append(5)  # 값 추가
if 2 in lst:
    lst.remove(2)  # 값 제거
print("리스트:", lst)
                

스택은 후입선출(LIFO: Last In, First Out) 구조를 가지는 자료구조로, 마지막에 추가된 데이터가 가장 먼저 제거됩니다. 주로 호출 스택(Call Stack)이나 되돌리기 기능에서 많이 사용됩니다.

• push: 스택에 데이터를 추가
• pop: 스택에서 데이터를 제거
• peek: 스택의 가장 위에 있는 데이터를 확인

문제 설명: 문자열에 괄호가 균형 있게 열리고 닫혔는지 검사하는 프로그램을 작성하세요.

Python 코드 예제:
def is_balanced(expr):
    stack = []
    for c in expr:
        if c in "({[":
            stack.append(c)
        elif c in ")}]":
            if not stack or stack.pop() != {"}": "{", "]": "[", ")": "("}[c]:
                return False
    return not stack

print("괄호 균형 검사:", is_balanced("(a+b)*[c-d]"))
                

큐는 선입선출(FIFO: First In, First Out) 구조를 가지는 자료구조로, 가장 먼저 들어온 데이터가 가장 먼저 제거됩니다. 주로 작업 대기열(Task Queue)이나 프로세스 스케줄링에 사용됩니다.

• enqueue: 큐에 데이터를 추가
• dequeue: 큐에서 데이터를 제거

문제 설명: 큐를 이용해 은행에서 고객들이 순서대로 서비스를 받도록 시뮬레이션하는 프로그램을 작성하세요.

Python 코드 예제:
from collections import deque

queue = deque(["고객1", "고객2", "고객3"])
while queue:
    customer = queue.popleft()  # 고객을 dequeue
    print(customer, "서비스 중입니다.")