알고리즘은 문제를 푸는 절차입니다. 게임에는 아이템 정렬, 길찾기, 충돌 확인, 랜덤 보상처럼 알고리즘이 필요한 기능이 곳곳에 있습니다. 이 글은 게임 프로그래머에게 특히 쓸모 있는 알고리즘을 분야별로 묶어 설명하고, 실무와 시험에서 어떻게 쓰이는지 정리합니다.

게임에서 알고리즘이 쓰이는 곳

• 인벤토리를 등급·이름·획득 순으로 정렬
• 랭킹에서 내 순위 찾기
• 몬스터가 플레이어에게 가는 경로 찾기
• 던전 맵을 자동으로 생성
• 확률에 따라 보상 뽑기

같은 결과를 내더라도 알고리즘에 따라 걸리는 시간이 크게 달라집니다. 데이터가 수십 개일 때는 차이가 없어 보여도, 수만 개로 늘어나면 한 프레임 안에 끝나지 않는 일이 생깁니다.

그래서 게임 프로그래머는 알고리즘을 외우기보다 '이 기능에 데이터가 얼마나 들어오는가, 얼마나 자주 실행되는가'를 먼저 따져 봅니다. 하루 한 번 실행되는 정산 코드와 매 프레임 실행되는 충돌 코드는 같은 기준으로 다룰 수 없습니다. 자주 실행되는 코드일수록 효율이 중요해집니다.

정렬과 탐색

정렬은 데이터를 기준에 따라 줄 세우는 일입니다. 실무에서는 대부분 표준 라이브러리의 정렬 함수를 쓰지만, 퀵 정렬, 병합 정렬, 삽입 정렬이 어떻게 동작하는지 알아야 상황에 맞게 고를 수 있습니다. 예를 들어 거의 정렬된 데이터에는 삽입 정렬이 빠르게 끝나는 특성이 있습니다.

탐색은 원하는 데이터를 찾는 일입니다. 정렬되지 않은 목록은 처음부터 하나씩 봐야 하지만, 정렬된 목록은 가운데를 기준으로 반씩 잘라 찾는 이진 탐색을 쓸 수 있습니다. 점수 구간으로 등급을 정하거나 경험치 표에서 레벨을 찾을 때 유용합니다.

그래프 탐색: BFS와 DFS

퍼즐 게임에서 같은 색 블록이 몇 개 붙어 있는지 세는 기능은 BFS나 DFS로 간단히 만들 수 있습니다. 코딩 테스트에서도 이런 격자 탐색 문제가 자주 나옵니다. 방문한 칸을 따로 표시하지 않으면 같은 칸을 계속 오가며 끝나지 않으니, 방문 기록을 남기는 습관을 들이세요.

동적 계획법과 탐욕 알고리즘

동적 계획법은 큰 문제를 작은 문제로 나누고, 이미 푼 결과를 저장해 다시 쓰는 방법입니다. 가방에 무게 제한이 있을 때 가치가 가장 큰 아이템 조합을 찾는 문제가 대표적입니다. 게임 밸런스 계산 도구나 최적 강화 경로 계산에 응용할 수 있습니다.

탐욕 알고리즘은 매 순간 가장 좋아 보이는 선택을 하는 방법입니다. 빠르지만 항상 최선의 답을 찾지는 못하습니다. 예를 들어 거스름돈 계산은 동전 단위에 따라 탐욕법이 맞기도 하고 틀리기도 합니다. 어떤 경우에 쓸 수 있는지 판단하는 것이 중요합니다.

확률과 랜덤 처리

게임의 확률 기능은 의사 난수(정해진 계산으로 무작위처럼 보이는 수를 만드는 것)로 구현합니다. 가중치 랜덤은 각 보상의 가중치를 모두 더한 뒤 그 범위 안에서 난수를 뽑아 어느 구간에 들어갔는지 보는 방식입니다.

• 셔플: 카드 덱을 섞을 때는 피셔-예이츠 셔플처럼 고르게 섞이는 방법을 씁니다.
• 시드: 같은 시드를 쓰면 같은 결과가 나와, 맵 생성 재현이나 리플레이에 활용합니다.
• 보정: 연속 실패를 줄이려는 보정 규칙은 기획 의도와 공개 정책을 함께 고려해 설계합니다.

공부 순서

1. 빅오 표기법으로 시간 복잡도를 읽는 법을 익힙니다.
2. 정렬과 이진 탐색을 직접 구현해 봅니다.
3. 격자 맵에서 BFS, DFS 문제를 풀어 봅니다.
4. 다익스트라와 A*로 길찾기를 만들어 봅니다.
5. 동적 계획법 기본 문제를 풀며 점화식 세우는 연습을 합니다.

SBS아카데미게임학원 게임프로그래밍 과정은 AI 알고리즘을 포함한 다양한 개발 기술을 실습 중심으로 다룹니다.

자주 묻는 질문