[Database] 2장 자료 구조와 기본 알고리즘

728x90

✅ 1. 자료 구조(데이터 구조)란

자료 구조란 데이터를 효율적으로 저장해 필요한 데이터를 더욱 빠르게 접근할 수 있게 만들고 수정과 삭제가 가능할 수 있도록 구성한 데이터 조직화 방법입니다. 데이터 분석에서 수많은 데이터를 처리하고, 통계 계산, 검색 필터링을 수행하기 때문에 자료 구조에 대한 이해가 필수적입니다. 자료 구조를 올바르게 정의하면 코드의 효율이 달라집니다.

✅ 2. 배열(Array)

배열(Array)은 같은 타입의 데이터를 연속된 메모리 공간에 저장하는 구조입니다. 인덱스로 바로 접근이 가능하며 그만큼 조회 속도가 빠르고(O(1)) 구현이 간단합니다.

// Python 에시
arr = [10, 20, 30, 40, 50];
print(arr[2]) # 30 출력
arr.append(60) # 배열 끝에 추가
print(arr[5]) # 60 출력

인덱스로 바로 접근 가능 구현이 간단함
크기를 미리 정해야 하며(동적 배열 제외) 삽입/삭제 시 데이터 이동이 필요해 그만큼 속도가 느린 단점
동작 원리 플로우차트:
- 배열 생성
- 인덱스 접근
- 값 읽기/쓰기
- 필요시 추가/삭제

✅ 3. 리스트(List, 연결 리스트)

리스트(List)는 각 요소가 데이터와 다음 요소에 대한 포인터를 가진 구조로, 배열과 달리 메모리가 연속적이지 않아도 됩니다.

class Node:
    def __init__(self, data):
        self.data = data 
        self.next = None
    
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)

current = head
while current:
      print(current.data)
      current = current.next

삽입/삭제 속도가 빠르며 (중간 위치에서도 O(1) 포인트 변경만 가능) 크기 제한이 없음
인덱스로 접근 시 O(n) -> 순차 탐색이 필요하고 메모리 사용량이 배열보다 많은 게 단점
활용 사례:
- 분석 데이터 스트리밍 시 동적 삽입
- Undo/Redo 기능 구현
- 그래프나 트리 구조 기반 데이터 분석
동작 원리 플로우차트 아이디어:
- 노드 생성
- 링크 연결
- 순차 탐색
- 삽입/삭제 시 링크 변경

✅ 4. 스택(Stack)

스택(Stack)은 LIFO(Last In, First Out = 마지막에 들어오고 제일 먼저 나간다) 구조로 구조가 단순하며 함수 호출 및 Undo 기능에 적합합니다. 단 임의 접근이 불가하고 (top만 접근 가능) 크기에 제한이 있습니다.

stack = [];
stack.append(10)
stack.append(20)
stack.append(30)
print(stack.pop()) # 30부터 출력 = 마지막에 들어온 데이터인 30이 먼저 나감

활용 사례:
- 수식 계산 (후위표기법)
- 웹 브라우저 뒤로가기 기능
- 데이터 분석에서 DFS(깊이 우선 탐색) 구현
동작 원리 플로우 차트:
- push: 데이터 추가
- pop: 데이터 제거
- top 확인

✅ 5. 큐 (Queue)

큐(Queue)는 FIFO(First In, First Out = 제일 먼저 들어오고 제일 먼저 나간다)의 구조로 먼저 들어온 데이터부터 나갑니다. 순서 유지에 최적하고 프로세스 관리, 이벤트 처리에 적합하나 임의 접근이 불가하고 크기에 제한이 있는 단점이 있습니다.

from collections import deque
queue = deque([10,20,30])
queue.append(40)
print(queue.popleft()) # 10 출력

활용 사례:
- 데이터 분석 배치 처리
- 이벤트 순차 처리
- BFS(너비 우선 탐색) 구현
동작 원리 플로우 차트:
- enqueue: 데이터 추가
- dequeue: 데이터 제거
- front 확인

✅ 6. 해시맵(HashMap)

키(Key)와 값(Value)가 쌍으로 데이터를 저장하는 구조로, 키를 해시 함수로 변환해 빠른 조회가 가능합니다. 조회, 삽입, 삭제 속도는 O(1)을 평균으로 하고 키 기반 검색이 가능합니다. 하지만 그만큼 메모리 사용량이 많고 해시 충돌 관리가 필요한 단점이 있습니다.

data = {"japan": "Sushi", "france": "Croissant"}
print(data["france"]) # Croissant
data["spain"] = "Paella"
print(data["spain"]) # Paella

활용 사례:
- 데이터 분석에서 카운팅(빈도수 계산)
- 추천 시스템에서 사용자 정보를 저장
- 통계 집계하기(ex. 특정 이벤트 발생 횟수)
동작 원리 플로우차트:
- 해시 함수로 키 변환
- 저장할 위치를 확인
- 삽입/조회/삭제 (CREATE, READ, DELETE)

✅ 7. 기본 알고리즘

이제 까지 기본적인 자료구조에 대해 이해해보았습니다. 이번에는 데이터를 정렬하고 검색하는 알고리즘을 알아보겠습니다 데이터를 분석할 때 필수적인 요소가 이 알고리즘 이라는 요소입니다.

🤓 7-1. 정렬(Sort)

🚀 버블 정렬(Bubble Sort)

arr = [5, 2, 3, 1, 4]
n = len(arr)
for i in range(n):
  for j in range(0, n-i-1):
     if arr[j] > arr[j+1]:
         arr[j], arr[j+1] = arr[j+1], arr[j]
print(arr)

동작 원리 프로우 차트:
- 첫 번째 원소와 두 번째 비교
- 필요 시 교환
- 배열 끝까지 반복
- 반복 횟수가 감소하며 전체 정렬

🚀 선택 정렬(Selection Sort)

arr = [7,2,6,5,7]

def selection_sort(arr):
    n =len(arr)
    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr


sorted_arr = selection_sort(arr)

print(sorted_arr)

동작 원리 플로우 차트:
- 리스트에서 가장 작은 원소를 찾음
- 맨 앞에 위취한 원소와 교환하는 과정 반복

🚀 삽입 정렬(Insertion Sort)

arr = [4,8,6,5,7]

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr;

insert_arr = insertion_sort(arr)

print(insert_arr); # [4, 5, 6, 7, 8]

동작 원리 플로우 차트:
- 배열에 정렬된 부분과 정렬되지 않은 부분으로 나눔
- 정렬되지 않은 부분의 원소를 정렬된 부분의 적절한 위치에 삽입해 정렬

🚀 병합 정렬(Merge Sort)

arr = [1,5,6,4,3,8]

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    
    left = merge_sort(left)
    right = merge_sort(right)
    
    return merge(left, right)

def merge(left, right): 
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else: 
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

merge_arr = merge_sort(arr)
print(merge_arr)

동작 원리 플로우 차트:
- 배열을 더 이상 나눌 수 없을 때까지 재귀적으로 분할
- 정렬된 부분 배열들을 합쳐 전체 배열을 정렬하는 분할 정복 방식

🚀 퀵 정렬 (Quick Sort)

arr = [8,2,5,1,3,4,6,7]

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        less = [x for x in arr[1:] if x <= pivot]
        greater = [x for x in arr[1:] if x > pivot]
        return quick_sort(less) + [pivot] + quick_sort(greater)
    
sorted_arr = quick_sort(arr)

print(sorted_arr)

동작 플로우 차트:
- 기준점(피벗)을 설정하고, 피벗을 기준으로 배열을 두개의 부분으로 나눔
- 각 부분에 대한 재귀적으로 퀵 정렬을 수행하는 분할 정복 방식

🤓 7-2. 탐색(Search)

🚀 선형 탐색(Linear Search)

my_list = [10, 22, 30, 45, 25]

def linear_search(data,target):
    for i in range(len(data)):
        if data[i] == target:
            return i # 찾는 경우 인덱스를 반환
    return -1 # 찾지 못할 씨 -1

target_value = 22

index = linear_search(my_list, target_value)
if index != -1:
   print(f"탐색 결과: {target_value}는 인덱스 {index}번 쨰에 있습니다")
else:
   print(f"탐색 결과: {target_value}는 인덱스에 존재하지 않습니다.")

동작 플로우 차트:
- 리스트의 첫 번째 요소 부터 하나씩 비교하며 찾는 방법

🚀 이진 탐색(Binary Search)

def binary_search(data, target):
    low = 0
    high = len(data) - 1
    
    while low <= high:
        mid = (low + high) // 2 
        min_value = data[mid]
        
        if min_value == target:
            return mid # 찾을 시 인덱스 바로 반환
        elif target < min_value:
            high = mid - 1 # 찾을 값이 중간 값보다 작을 시 왼쪽 범위를 탐색
        else:
            low = mid + 1 # 찾을 값이 중간 값보다 크면 오른쪽 범위 탐색
    return -1 

# 이진 탐색 시 반드시 정렬된 리스트에서 사용
sort_list = [5,10,15, 25, 30,35] # 정렬 되지 않을 시 출력 X
target_value = 35

index = binary_search(sort_list, target_value)
if index != -1:
    print(f"탐색 결과: {target_value}는 {index}번째 인덱스에 있습니다")
else:
    print(f"탐색 결과: {target_value}는 검색 결과에 없습니다.")

동작 플로우 차트:
- 중간값(mid) 계산
- 찾는 값 비교
- 범위(left, right) 축소
- 반복

✅ 정리

자료 구조	장점	단점	데이터 분석 활용
배열	인덱스 접근이 빠르다	삽입/삭제가 느림	시계열, 통계 계산에 용이
리스트	동적 삽입/삭제 용이	인덱스 접근은 느림	스트리밍 데이터
스택	LIFO 구조, 단순함	임의 접근 불가	수식 계산, DFS
큐	FIFO 구조	임의 접근 불가	배치 처리, BFS
해시맵	키 기반 O(1)	과도한 메모리 사용	카운팅, 추천 시스템

GitHub - Koras02/database-posting

Contribute to Koras02/database-posting development by creating an account on GitHub.

github.com