알고리즘과 데이터베이스 (1)
데이터를 핸들링하는 데에 있어서 알고리즘과 데이터베이스는 매우 중요한 개념이다. 알고리즘은 데이터를 효과적으로 정렬하고 탐색하는 방법을 제공하며, 데이터베이스는 이를 효율적으로 저장하고 관리한다. 이 두 개념은 단순한 기술적 요소를 넘어, 방대한 데이터를 다루는 데이터 엔지니어링의 핵심이 된다고 한다.
현대 데이터 엔지니어링에서는 대량의 데이터를 빠르게 처리하고, 원하는 정보를 효율적으로 검색하는 것이 필수적이다. 정렬과 탐색 알고리즘은 데이터 처리 속도를 결정하는 중요한 요소이며, 데이터베이스는 이를 저장하고 활용하는 도구이다. 알고리즘이 최적화되지 않으면 데이터가 증가할수록 검색 속도가 기하급수적으로 느려지며, 데이터베이스 설계가 잘못되면 데이터 관리가 비효율적으로 이루어진다.
알고리즘이란?
알고리즘이란 어떤 문제를 해결하기 위한 절차나 방법을 의미한다. 쉽게 말하면, 주어진 입력을 원하는 출력으로 변환하기 위한 명령어들의 집합이다. 좋은 알고리즘은 효율적이어야 하며, 실행 속도가 빠르고 메모리 사용량이 적어야 한다.
예를 들어, 만약 친구들과 함께 피자를 주문한다고 가정해보자. 가장 저렴한 피자를 찾기 위해 메뉴판의 모든 항목을 하나하나 비교하는 방식(선형 탐색)은 시간이 오래 걸릴 수 있다. 하지만 메뉴가 가격순으로 정렬되어 있다면(정렬 알고리즘 적용), 원하는 가격의 피자를 훨씬 빠르게 찾을 수 있다(이진 탐색 적용). 이처럼 알고리즘은 우리의 일상에서도 자연스럽게 활용된다.
알고리즘의 효율성을 평가하는 기준은
- 시간 복잡도(Time Complexity) 와
- 공간 복잡도(Space Complexity) 이다.
이는 입력 크기(n)가 커질수록 연산 시간이 어떻게 변하는지, 그리고 얼마나 많은 메모리를 사용하는지를 나타내는 척도이다. 시간 복잡도가 낮은 알고리즘을 사용하면 같은 양의 데이터를 처리하더라도 실행 속도가 훨씬 빨라진다.
정렬 알고리즘
정렬(Sorting)이란 데이터를 일정한 순서대로 정리하는 과정이다. 정렬된 데이터는 검색과 탐색을 보다 효율적으로 수행할 수 있게 해준다. 예를 들어, 서점에서 책을 찾을 때 책이 제목순으로 정렬되어 있으면 원하는 책을 빠르게 찾을 수 있다. 하지만 무작위로 놓여 있다면 하나하나 확인해야 하므로 시간이 훨씬 오래 걸린다.
주요 정렬 알고리즘
1. 버블 정렬 (Bubble Sort)
정렬 방법: 인접한 두 요소를 비교하여 필요하면 자리를 바꾸는 과정을 반복한다.
def bubble_sort(arr):
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]
return arr장점: 구현이 간단함
단점: 성능이 매우 낮고, 데이터 크기가 커질수록 비효율적임
2. 선택 정렬 (Selection Sort)
정렬 방법: 리스트에서 가장 작은 값을 찾아 맨 앞에 배치하는 방식
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr장점: 자료 이동 횟수가 적음\
단점: 시간 복잡도가 O(n²)로 성능이 좋지 않음
추가 정렬 알고리즘 6개에 대한 상세 설명을 아래에 작성하였네.
3. 삽입 정렬 (Insertion Sort)
정렬 방법: 이미 정렬된 부분과 비교하며, 적절한 위치에 삽입하는 방식.
def insertion_sort(arr):
for i in range(1, len(arr)):
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장점: 데이터가 거의 정렬된 경우 빠르게 동작함.
단점: 최악의 경우 시간 복잡도가 O(n²)로 비효율적임.
4. 병합 정렬 (Merge Sort)
정렬 방법: 배열을 반으로 나눈 후 각각 정렬하고, 다시 합치는 방식.
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
merge_sort(left_half)
merge_sort(right_half)
i = j = k = 0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1
return arr장점: 최악의 경우에도 시간 복잡도가 O(n log n)으로 안정적임.
단점: 추가적인 메모리 공간이 필요함.
5. 퀵 정렬 (Quick Sort)
정렬 방법: 기준점(pivot)을 정하고, 작은 값은 왼쪽, 큰 값은 오른쪽으로 정렬 후 재귀적으로 반복.
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)장점: 평균적으로 매우 빠르며, O(n log n)의 시간 복잡도를 가짐.
단점: 최악의 경우 O(n²)까지 느려질 수 있음 (pivot을 잘 선택해야 함).
6. 힙 정렬 (Heap Sort)
정렬 방법: 힙(heap) 자료구조를 이용하여 정렬하는 방식.
import heapq
def heap_sort(arr):
heapq.heapify(arr)
return [heapq.heappop(arr) for _ in range(len(arr))]장점: O(n log n)의 성능을 유지하며 안정적인 정렬이 가능함.
단점: 힙을 구성하는 과정에서 추가적인 메모리 사용이 필요함.
7. 계수 정렬 (Counting Sort)
정렬 방법: 각 요소의 개수를 세어 순서를 결정하는 방식. (정수 데이터에 적합)
def counting_sort(arr):
max_val = max(arr)
count = [0] * (max_val + 1)
for num in arr:
count[num] += 1
sorted_arr = []
for i, freq in enumerate(count):
sorted_arr.extend([i] * freq)
return sorted_arr장점: 특정한 범위 내의 정수 정렬 시 매우 빠름(O(n)).
단점: 데이터의 크기가 클 경우 메모리 사용량이 많아질 수 있음.
8. 기수 정렬 (Radix Sort)
정렬 방법: 낮은 자릿수부터 차례대로 정렬하여 정렬하는 방식.
def radix_sort(arr):
max_num = max(arr)
exp = 1
while max_num // exp > 0:
counting_sort_exp(arr, exp)
exp *= 10
return arr
def counting_sort_exp(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
for i in arr:
index = (i // exp) % 10
count[index] += 1
for i in range(1, 10):
count[i] += count[i - 1]
for i in range(n - 1, -1, -1):
index = (arr[i] // exp) % 10
output[count[index] - 1] = arr[i]
count[index] -= 1
for i in range(n):
arr[i] = output[i]장점: O(n) 시간 복잡도를 가질 수 있으며, 정수 정렬에 강력함.
단점: 부동소수점 숫자나 문자열 정렬에는 적용하기 어려움.
정렬 알고리즘 15가지를 좀 더 보기 쉽게 동영상으로 만들어놓은 것이 있어서, 이를 보면 정렬 방식이 좀 더 구체적으로 와닿을 것 같다.
데이터베이스 기초
데이터베이스란?
데이터베이스(Database)는 데이터를 체계적으로 저장하고 관리하는 시스템이다. 데이터베이스를 사용하면 대량의 데이터를 쉽게 검색하고 수정할 수 있다.
데이터베이스의 종류는 크게 관계형 데이터베이스(Relational Database)와 NoSQL 데이터베이스로 나눌 수 있다.
- 관계형 데이터베이스 (RDBMS): 테이블(table) 형태로 데이터를 저장하며, SQL을 사용하여 데이터를 관리한다. (예: MySQL, PostgreSQL, SQLite)
- NoSQL 데이터베이스: 테이블 대신 키-값, 문서(Document), 그래프 형태로 데이터를 저장한다. (예: MongoDB, Redis)
SQL 기본 문법
아래는 아주 기초적인 CRUD 문의 예시이다. 산업 전반에서 데이터를 다루는 직무들이 아주 중요해진 만큼, 전공자가 아닌 일반 사무직이라도 SQL을 배우는 것이 권장되곤 한다.
-- 데이터 조회 (SELECT)
SELECT * FROM users WHERE age > 30;
-- 데이터 삽입 (INSERT)
INSERT INTO users (name, age) VALUES ('Alice', 25);
-- 데이터 수정 (UPDATE)
UPDATE users SET age = 26 WHERE name = 'Alice';
-- 데이터 삭제 (DELETE)
DELETE FROM users WHERE age < 20;SQLite와 정렬 알고리즘을 활용한 데이터 처리
Python에서 서버 연결 등 복잡한 작업 없이 DB를 활용할 수 있게 해주는 모듈인 SQLite를 활용하여 데이터를 저장하고, 정렬 알고리즘을 적용하여 데이터를 정리하는 실습을 진행해보자.
import sqlite3
# 데이터베이스 연결
conn = sqlite3.connect('example.db')
cursor = conn.cursor() # DB와 상호작용을 위한 커서 생성
# 테이블 생성
cursor.execute('''CREATE TABLE IF NOT EXISTS users (id INTEGER PRIMARY KEY, name TEXT, age INTEGER)''')
# 데이터 삽입
cursor.executemany("INSERT INTO users (name, age) VALUES (?, ?)", [('Alice', 25), ('Bob', 30), ('Charlie', 22)])
# 데이터 조회 및 정렬
cursor.execute("SELECT * FROM users")
data = cursor.fetchall()
def sort_by_age(data):
return sorted(data, key=lambda x: x[2])
sorted_data = sort_by_age(data)
print("정렬된 사용자 목록:", sorted_data)
# 연결 종료
conn.commit()
conn.close()SQLite 모듈은 내 컴퓨터의 현재 작업중인 디렉토리에 DB파일을 만들어주고, 데이터베이스와 상호작용하는 기능도 탑재하고 있다. 아주 간단한 예제지만, 이 실습을 통해 데이터베이스에서 데이터를 가져오고, 정렬 알고리즘을 적용하여 정리하는 과정을 경험할 수 있다. 규모가 크지 않은, 로컬 프로그램을 만들 때 활용해볼 수 있을 것 같다.
