19강: 최적화의 근간 – 자료구조와 알고리즘
게임 개발에서는 실시간 처리, 예측 가능한 물리 연산, AI, 렌더링 등 다양한 측면에서 성능 최적화가 필수입니다. 자료구조와 알고리즘은 데이터 저장, 검색, 정렬, 경로 탐색, 충돌 판정 등 여러 작업의 기반 역할을 하며, 전체 시스템 성능과 안정성에 큰 영향을 준다.
1. 자료구조와 알고리즘의 기본 개념
1.1 자료구조란?
- 정의: 데이터를 체계적으로 저장하고, 효율적으로 접근 및 조작할 수 있도록 하는 구조적 방식
- 중요성: 데이터의 조직 방식이 성능, 확장성, 메모리 효율성에 직접적인 영향을 미치며, 특히 실시간성과 대용량 데이터 처리가 중요한 게임 개발에서 시스템 품질에 결정적인 역할을 함
1.2 알고리즘과의 관계
- 비유: 자료구조가 데이터를 담는 ‘그릇’이라면, 알고리즘은 그 데이터를 처리하는 ‘행동’
- 상호 작용: 정렬, 탐색 등의 알고리즘은 특정 자료구조 위에서 동작하며, 자료구조의 선택에 따라 알고리즘 성능이 달라짐
1.3 시간 복잡도와 공간 복잡도
- 시간 복잡도 (Time Complexity):
- O(1): 상수 시간 – 예: 배열의 특정 인덱스 접근
- O(n): 선형 시간 – 예: 배열 전체 순회
- O(n²): 이차 시간 – 예: 중첩 반복문(버블 정렬)
- 공간 복잡도 (Space Complexity): 알고리즘 실행 시 요구되는 메모리 양
- 추가 고려: 게임 개발에서는 프레임당 제한 시간(예: 16.6ms, 60fps) 내에 모든 연산을 처리해야 하므로, 시간/공간 복잡도 외에도 CPU 캐시 친화성, 메모리 단편화, 할당/해제 비용 등을 함께 고려해야 함
2. 기본 자료 구조
2.1 배열 (Array)
특징
- 연속 메모리: 동일한 데이터 타입의 값을 연속된 메모리 공간에 저장
- 빠른 접근: 인덱스를 통한 직접 접근이 가능해 O(1) 시간 복잡도를 가짐
- 캐시 효율성: 연속된 메모리로 인한 캐시 라인 활용에 유리함
정적 배열 vs 동적 배열
- 정적 배열 (Static Array):
- 선언 시 크기가 고정되어 스택에 할당
- 빠른 접근과 낮은 오버헤드
- 크기 변경 불가능
- 동적 배열 (Dynamic Array, 예:
std::vector):- 런타임 중 크기 조절 가능, 힙에 할당됨
- 용량 부족 시 새로운 메모리 블록 할당 후 데이터 복사 (최악의 경우 O(n) 비용 발생)
- 일반적으로 용량이 다 찰 때 현재 크기의 2배로 확장, amortized O(1) 성능 보장
- 초기 용량 예약(
reserve)을 통해 재할당 횟수와 메모리 단편화 완화 가능
실습 예제:
std::vector의 요소 추가 시 내부 배열의 메모리 주소 변화 확인 코드 제공
2.2 연결 리스트 (Linked List)
기본 개념
- 구조: 각 노드가 데이터와 다음(및 경우에 따라 이전) 노드의 포인터를 포함
- 비연속 저장: 노드들은 힙에 동적 할당되어 메모리상에서 연속적으로 배치되지 않음
장단점 및 고려 사항
- 장점:
- 삽입과 삭제 시 전체 데이터를 이동할 필요 없이 포인터 연결만 수정하면 됨
- 동적 크기 조절에 유리
- 단점:
- 임의 접근(Random Access)이 어려워 순차 탐색(O(n)) 필요
- 각 노드에 추가 포인터로 인한 메모리 오버헤드
- 노드들이 메모리상 산발적으로 배치되어 CPU 캐시 효율성이 떨어짐
- 동적 메모리 할당 시 메모리 누수에 주의 (스마트 포인터 등의 기법 사용 권장)
변형 및 실습
- 변형:
단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트 등 - 실습 예제:
- 단일 연결 리스트 구현 예제 (노드 생성, 순차 탐색 출력)
#include <iostream>
#include <vector>
int main() {
// 초기 용량을 5로 예약하여, 5개 채워지면 재할당이 발생하도록 합니다.
std::vector<int> vec;
vec.reserve(5);
std::cout << "Initial capacity: " << vec.capacity() << "\n";
// 이전 메모리 주소를 저장할 포인터 변수 (초기에는 nullptr)
int* prevAddress = nullptr;
for (int i = 0; i < 50; i++) {
vec.push_back(i);
int* currAddress = vec.data();
// 재할당이 발생하면 주소가 달라집니다.
if (prevAddress != currAddress) {
if (prevAddress == nullptr) {
// 최초 할당 시 로그
std::cout << "After push_back(" << i << "): Initial allocation.\n"
<< "New Address = " << currAddress
<< ", Capacity = " << vec.capacity() << "\n";
} else {
// 재할당 발생 시 로그: 이전 주소와 새로운 주소를 명시적으로 출력
std::cout << "After push_back(" << i << "): Reallocation occurred!\n"
<< "Old Address = " << prevAddress << " --> New Address = "
<< currAddress << "\n"
<< "New Capacity = " << vec.capacity() << "\n";
}
prevAddress = currAddress;
}
}
return 0;
}- 이중 연결 리스트 구현 (삽입, 삭제, 순방향 및 역방향 출력 포함)
#include <iostream>
// 이중 연결 리스트의 각 노드를 정의하는 구조체
struct Node {
int data; // 노드가 저장할 데이터
Node* prev; // 이전 노드에 대한 포인터
Node* next; // 다음 노드에 대한 포인터
};
// 이중 연결 리스트를 관리하는 클래스
class DoublyLinkedList {
private:
Node* head; // 리스트의 시작 노드 (첫 번째 노드)
Node* tail; // 리스트의 마지막 노드 (마지막 노드)
public:
// 생성자: 리스트가 처음 생성될 때 head와 tail을 nullptr로 초기화
DoublyLinkedList() : head(nullptr), tail(nullptr) {}
// 소멸자: 리스트의 모든 노드를 순회하며 메모리를 해제
~DoublyLinkedList() {
Node* current = head;
// 현재 노드가 nullptr가 될 때까지 순차적으로 삭제
while (current != nullptr) {
Node* nextNode = current->next; // 다음 노드를 임시 저장
delete current; // 현재 노드 메모리 해제
current = nextNode; // 다음 노드로 이동
}
}
// 리스트의 끝에 새 노드를 삽입하는 메서드
void insert(int value) {
// 새 노드를 동적 할당하여 생성, prev와 next는 nullptr로 초기화
Node* newNode = new Node{value, nullptr, nullptr};
// 만약 리스트가 비어있다면, 새 노드가 head와 tail이 됨
if (head == nullptr) {
head = newNode;
tail = newNode;
} else {
// 리스트가 비어있지 않다면, 새 노드를 tail 뒤에 추가
tail->next = newNode; // 기존 tail의 next가 새 노드를 가리킴
newNode->prev = tail; // 새 노드의 prev는 기존 tail을 가리킴
tail = newNode; // tail 포인터를 새 노드로 갱신
}
}
// 특정 값을 가진 노드를 삭제하는 메서드
// 값이 리스트에 존재하면 삭제 후 true를, 없으면 false를 반환
bool remove(int value) {
Node* current = head;
// 삭제할 노드를 찾기 위해 리스트 순회
while (current != nullptr && current->data != value) {
current = current->next;
}
// 만약 해당 값을 가진 노드가 없다면 false 반환
if (current == nullptr) {
return false;
}
// 삭제할 노드가 head인 경우
if (current == head) {
head = current->next; // head를 다음 노드로 갱신
if (head != nullptr) {
head->prev = nullptr; // 새 head의 prev를 nullptr로 설정
} else {
// 리스트에 노드가 하나뿐이었다면 tail도 nullptr로 설정
tail = nullptr;
}
}
// 삭제할 노드가 tail인 경우
else if (current == tail) {
tail = current->prev; // tail을 이전 노드로 갱신
tail->next = nullptr; // 새 tail의 next를 nullptr로 설정
}
// 삭제할 노드가 중간에 위치한 경우
else {
// 현재 노드의 이전 노드와 다음 노드를 서로 연결
current->prev->next = current->next;
current->next->prev = current->prev;
}
delete current; // 삭제할 노드의 메모리 해제
return true;
}
// 리스트를 순방향(앞에서 뒤로)으로 출력하는 메서드
void displayForward() const {
Node* current = head;
std::cout << "Forward: ";
// 리스트의 끝(현재 노드가 nullptr)이 될 때까지 순차적으로 출력
while (current != nullptr) {
std::cout << current->data << " -> ";
current = current->next;
}
std::cout << "NULL" << std::endl;
}
// 리스트를 역방향(뒤에서 앞으로)으로 출력하는 메서드
void displayBackward() const {
Node* current = tail;
std::cout << "Backward: ";
// tail부터 시작하여 이전 노드를 따라가며 출력
while (current != nullptr) {
std::cout << current->data << " -> ";
current = current->prev;
}
std::cout << "NULL" << std::endl;
}
};
int main() {
// DoublyLinkedList 객체 생성
DoublyLinkedList list;
// 리스트에 여러 값을 삽입
list.insert(10);
list.insert(20);
list.insert(30);
list.insert(40);
list.insert(50);
// 순방향 출력: head에서 tail 방향으로 출력
std::cout << "Initial Doubly Linked List:" << std::endl;
list.displayForward();
// 역방향 출력: tail에서 head 방향으로 출력
list.displayBackward();
// 특정 값을 가진 노드 삭제 예제 (값 30 삭제)
std::cout << "\nRemoving node with value 30..." << std::endl;
if (list.remove(30)) {
std::cout << "Node removed successfully." << std::endl;
} else {
std::cout << "Node not found." << std::endl;
}
// 삭제 후 리스트 출력
std::cout << "\nDoubly Linked List after deletion:" << std::endl;
list.displayForward();
list.displayBackward();
return 0;
}2.3 해시 테이블 (Hash Table)
기본 개념
- 정의: 키와 값의 쌍을 저장하는 자료구조
- 해시 함수: 입력된 키를 고정 크기의 정수(해시 코드)로 변환 후, 내부 배열(버킷)의 인덱스로 사용
충돌 해결 기법
- 체이닝 (Chaining):
같은 해시 값을 가진 여러 키-값 쌍을 연결 리스트나 동적 배열로 관리 - 오픈 어드레싱 (Open Addressing):
충돌 발생 시 다음 빈 버킷을 찾아 저장 (선형 탐사, 제곱 탐사, 이중 해싱 등)
성능 및 고려 사항
- 연산 효율: 평균적으로 검색, 삽입, 삭제가 O(1)
- 주의 사항:
해시 함수의 품질, 키 분포, 부하 계수(Load Factor), 재해싱(Rehashing) 과정에서 일시적 성능 저하 및 메모리 오버헤드를 고려해야 함
실습 예제
- 예제 코드:
C++ STLunordered_map을 사용해 키-값 삽입, 검색, 출력 확인
#include <iostream>
#include <unordered_map>
#include <string>
int main() {
// unordered_map은 C++ STL에서 제공하는 해시 테이블 구현체입니다.
std::unordered_map<std::string, int> hashTable;
// 키-값 쌍을 해시 테이블에 삽입합니다.
hashTable["apple"] = 3;
hashTable["banana"] = 5;
hashTable["cherry"] = 7;
// "apple" 키를 통한 데이터 접근 (평균 O(1) 시간 복잡도)
std::string key = "apple";
if (hashTable.find(key) != hashTable.end()) {
std::cout << "Key: " << key << ", Value: " << hashTable[key] << std::endl;
} else {
std::cout << key << " not found in the hash table." << std::endl;
}
// 해시 테이블의 모든 요소를 출력합니다.
std::cout << "Hash Table Contents:" << std::endl;
for (const auto& pair : hashTable) {
std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl;
}
return 0;
}2.4 트리 (Tree)
기본 개념 및 구성 요소
- 구조: 하나의 루트 노드를 시작으로 여러 자식 노드들이 계층적으로 연결된 비선형 자료구조
- 용어:
- 루트: 트리의 시작점
- 리프: 자식 노드가 없는 말단 노드
- 간선: 부모와 자식 노드를 연결하는 선
종류 및 특성
- 이진 트리 (Binary Tree):
각 노드가 최대 두 개의 자식을 가짐 - 이진 탐색 트리 (Binary Search Tree, BST):
왼쪽 서브트리에는 작은 값, 오른쪽 서브트리에는 큰 값을 저장 - 균형 트리:
AVL 트리, 레드-블랙 트리 등 – 삽입, 삭제, 탐색 시 균형을 유지하여 최적의 성능 제공 - 대용량 데이터 구조:
B-트리, B+트리 – 데이터베이스 인덱싱이나 파일 시스템 등에서 사용
트리 탐색 방법
- 전위 순회 (Preorder): 현재 노드 → 왼쪽 서브트리 → 오른쪽 서브트리
- 중위 순회 (Inorder): 왼쪽 서브트리 → 현재 노드 → 오른쪽 서브트리
※ BST의 중위 순회 결과는 오름차순 정렬된 값 - 후위 순회 (Postorder): 왼쪽 서브트리 → 오른쪽 서브트리 → 현재 노드
실습 예제
- BST 구현:
C++로 이진 탐색 트리 생성, 노드 삽입, 중위 순회를 통한 정렬된 출력, 메모리 해제 코드 제공
코드 예제
아래는 C++로 이진 탐색 트리(Binary Search Tree)를 간단하게 구현한 예제입니다.
이 예제에서는 노드 구조체를 정의하고, 데이터를 삽입하며 중위 순회(Inorder Traversal)를 통해 트리 내의 데이터를 정렬된 순서로 출력하는 방법을 보여줍니다.
#include <iostream>
// 이진 탐색 트리의 노드 구조체 정의
struct TreeNode {
int data; // 노드가 저장하는 데이터
TreeNode* left; // 왼쪽 자식 노드를 가리키는 포인터
TreeNode* right; // 오른쪽 자식 노드를 가리키는 포인터
// 생성자: 초기화 리스트를 사용하여 데이터와 포인터들을 초기화합니다.
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
// 트리에 새로운 데이터를 삽입하는 함수 (재귀적 구현)
TreeNode* insert(TreeNode* root, int value) {
// 만약 트리가 비어있다면 새로운 노드를 생성하여 반환
if (root == nullptr) {
return new TreeNode(value);
}
// 현재 노드의 값보다 작으면 왼쪽 서브트리에 삽입
if (value < root->data) {
root->left = insert(root->left, value);
}
// 현재 노드의 값보다 크면 오른쪽 서브트리에 삽입
else if (value > root->data) {
root->right = insert(root->right, value);
}
// 값이 중복될 경우 특별한 처리를 하지 않고 그대로 반환 (중복 허용하지 않음)
return root;
}
// 중위 순회를 이용해 트리의 데이터를 출력하는 함수
void inorderTraversal(TreeNode* root) {
if (root != nullptr) {
inorderTraversal(root->left);
std::cout << root->data << " ";
inorderTraversal(root->right);
}
}
// 트리의 메모리를 해제하는 함수 (후위 순회 방식)
void deleteTree(TreeNode* root) {
if (root != nullptr) {
deleteTree(root->left);
deleteTree(root->right);
delete root;
}
}
int main() {
TreeNode* root = nullptr;
// 이진 탐색 트리에 데이터 삽입
root = insert(root, 50);
root = insert(root, 30);
root = insert(root, 70);
root = insert(root, 20);
root = insert(root, 40);
root = insert(root, 60);
root = insert(root, 80);
// 중위 순회를 통해 트리의 데이터를 정렬된 순서로 출력
std::cout << "Inorder Traversal of BST: ";
inorderTraversal(root);
std::cout << std::endl;
// 동적 할당된 트리의 메모리 해제
deleteTree(root);
return 0;
}3. 종합 및 실제 적용
- 게임 개발에서의 최적화:
모든 연산이 제한된 시간 내 완료되어야 하는 실시간 시스템에서는 자료구조와 알고리즘 선택이 실행 성능, 메모리 효율성, 응답 속도, 그리고 안정성에 결정적인 역할을 함 - 실제 고려사항:
단순 이론에 머무르지 않고 CPU 캐시 친화성, 메모리 단편화, 동적 메모리 할당/해제 비용 등 현실적인 요소를 종합적으로 고려하여 적합한 자료구조와 알고리즘을 선택해야 함
이 문서는 강의의 핵심 개념 및 실습 예제를 바탕으로 작성되었으며, 블로그(벨로그) 포스팅용으로 자료구조와 알고리즘의 중요성을 정리하는 데 활용할 수 있다.
