자료구조와 알고리즘

진정·2025년 4월 20일

bootcamp 컴퓨터공학개론

자료구조와 알고리즘: 효율적인 프로그래밍의 핵심

이번 주 부트캠프에서는 소프트웨어 개발의 근간이 되는 자료구조(Data Structure)와 알고리즘(Algorithm)에 대해 학습함

평소 이미 알고있는 내용이지만 간단하게 배웠던 것들의 개념과 원리 위주로 복습 정리 예정

1. 자료구조란 무엇인가?

자료구조는 데이터를 어떻게 저장하고 구성할 것인지에 대한 방법
목적은 데이터를 효율적으로 삽입, 삭제, 탐색, 정렬할 수 있도록 하는 것

🔑 자료구조의 목적

빠른 접근(access): 필요한 데이터를 얼마나 빠르게 꺼낼 수 있는가
유연한 삽입/삭제: 데이터 추가, 삭제가 얼마나 효율적인가
메모리 효율성: 공간을 얼마나 낭비하지 않고 사용할 수 있는가

📌 주요 자료구조와 특징

(A) 배열 vs 연결 리스트 예시 (Python)

# 배열 예시
arr = [10, 20, 30]
arr.append(40)
print(arr[2])  # 출력: 30

# 연결 리스트 예시 (클래스로 직접 구현)
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

node1 = Node(10)
node2 = Node(20)
node1.next = node2

print(node1.next.data)  # 출력: 20

(B) 해시 테이블 vs 트리 구조 (Python)

# 해시 테이블: 딕셔너리 사용
user_info = {
    'superjinjung': 'jinjung1234@gmail.com',
    'ai_learner': 'ai4life@naver.com'
}
print(user_info['superjinjung'])  # O(1)

# 트리 구조: 이진 탐색 트리 구현
class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def insert(root, key):
    if not root:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    return root

root = Node(50)
insert(root, 30)
insert(root, 70)
# 이진 탐색은 O(log n) 시간복잡도

2. 알고리즘(Algorithm)이란 무엇인가?

알고리즘은 특정 문제를 해결하기 위한 일련의 절차나 규칙
같은 문제라도 어떤 알고리즘을 사용하느냐에 따라 성능 차이가 극명하게 나타나게 됨

좋은 알고리즘의 조건 🎯

정확성(Correctness): 문제를 올바르게 해결하는가?
효율성(Efficiency): 자원을 얼마나 적게 쓰는가?
명료성(Clarity): 구현이 간결하고 이해하기 쉬운가?

대표적인 알고리즘 유형과 사례

예제 1: 이진 탐색 (Binary Search, O(log n))

def binary_search(arr, target):
    left, right = 0, len(arr)-1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

arr = [10, 20, 30, 40, 50, 60]
print(binary_search(arr, 40))  # 출력: 3

예제 2: 피보나치 수열 (재귀 vs 동적 계획법)

# 비효율적인 재귀 방식 (O(2^n))
def fib_recursive(n):
    if n <= 1:
        return n
    return fib_recursive(n-1) + fib_recursive(n-2)

# 효율적인 동적 계획법 (O(n))
def fib_dp(n):
    dp = [0, 1]
    for i in range(2, n+1):
        dp.append(dp[i-1] + dp[i-2])
    return dp[n]

print(fib_dp(10))  # 출력: 55