Part2. 게임 알고리즘과 설계: 1~25 | 2025 게임 프로그래밍 전문가 국가기술 자격검정 필기시험 B 풀이 | 게임국가기술자격검정 게임프로그래밍전문가 [한국콘텐츠진흥원]

Part 2. 게임 알고리즘과 설계 | 2025 게임 프로그래밍 전문가 국가기술 자격검정 필기시험 B 풀이

1. 다음 중 게임 내 물리 엔진을 활용하여 중력과 마찰력 등을 구현하는 이유로 가장 적합한 설명은?

① 캐릭터의 움직임을 자연스럽게 표현하기 위해

② 게임 속도를 인위적으로 증가시키기 위해

③ 캐릭터의 공격력을 높이기 위해

④ 게임 그래픽의 해상도를 높이기 위해

개념: 물리엔진

풀이

게임 내 물리 엔진은 중력, 마찰력, 충돌 등 실제 물리 법칙을 시뮬레이션합니다. 이를 통해 캐릭터가 땅을 딛고 뛰거나, 물건이 떨어지고, 부딪혔을 때 현실적이고 자연스러운 움직임을 구현하여 사용자의 몰입감을 높이는 것이 주된 목적입니다.

정답: ① 캐릭터의 움직임을 자연스럽게 표현하기 위해

2. 다음은 선택 정렬을 구현한 코드이다. 빈칸 (A)를 채우기 위한 코드로 알맞은 것은?

void selectionSort(int arr[], int size) {
    int i, j, min_idx, temp;
    for (i = 0; i < size-1; i++) {
        min_idx = i;
        for (j = i+1; j < size; j++)
            if (arr[j] < arr[min_idx])
                **( A );**
        temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

① min_idx = j

② arr[j] = min_idx

③ min_idx = arr[j]

④ j = min_idx

개념: 선택 정렬 (Selection Sort)

풀이:

선택 정렬(Selection Sort) 알고리즘에서 가장 작은 값을 찾기 위해 if 문 내부에서 min_idx를 갱신해주는 코드가 필요

선택 정렬은 배열에서 가장 작은 값을 찾아 맨 앞의 데이터와 자리를 바꾸며 정렬하는 알고리즘입니다. 이 과정은 크게 두 단계로 나뉩니다.

최소값 찾기: 정렬되지 않은 나머지 배열을 탐색하며 가장 작은 값의 위치(min_idx)를 기억합니다.
값 교환하기: 찾은 최소값을 현재 정렬 순서의 맨 앞 자리와 바꿉니다.

정답: ③ min_idx = arr[j]

3. 다음 단순 연결 리스트 노드 삭제 코드 중 옳지 않은 설명은?

Node* deleteNode(Node* head, int value) {
    Node* temp = head, *prev = NULL;
    if(temp != NULL && temp->value == value){
        head = temp->next;
        free(temp);
        return head;
    }
    while(temp != NULL && temp->value != value){
        prev = temp;
        temp = temp->next;
    }
    if(temp == NULL) return head;
    prev->next = temp->next;
    free(temp);
    return head;
}

① 삭제할 노드가 첫 번째 노드이면 head를 다음 노드로 변경한다. ② 삭제할 노드를 찾기 위해 리스트를 순회한다. ③ 삭제할 노드가 없는 경우 새 노드를 생성하여 연결 리스트에 추가한다. ④ 삭제할 노드의 앞 링크에 삭제할 노드의 다음 링크를 연결시키고, 해당 노드의 메모리를 해제한다.

개념: 노드, 단순 연결 리스트 노드

풀이:

제시된 코드는 단순 연결 리스트에서 특정 값을 가진 노드를 삭제하는 함수입니다. 각 보기에 대한 설명은 다음과 같습니다.

**① 삭제할 노드가 첫 번째 노드이면 head를 다음 노드로 변경한다. (옳음)**코드의 if(temp != NULL && temp->value == value) 부분에서 삭제할 노드가 첫 번째 노드일 경우 head = temp->next;를 통해 head를 변경하고, free(temp);로 메모리를 해제합니다.
② 삭제할 노드를 찾기 위해 리스트를 순회한다. (옳음)while(temp != NULL && temp->value != value) 문을 사용하여 삭제할 값을 가진 노드(temp)와 그 전 노드(prev)를 찾습니다.
③ 삭제할 노드가 없는 경우 새 노드를 생성하여 연결 리스트에 추가한다. (틀림)if(temp == NULL) return head; 부분은 삭제할 노드를 찾지 못하고 리스트 끝에 도달했을 때 수행되며, 이때는 아무것도 하지 않고(노드 삭제 없이) 원래의 리스트(head)를 그대로 반환합니다. 새 노드를 생성하지 않습니다.
④ 삭제할 노드의 앞 링크에 삭제할 노드의 다음 링크를 연결시키고, 해당 노드의 메모리를 해제한다. (옳음)prev->next = temp->next;로 링크를 연결하여 삭제할 노드를 리스트에서 건너뛰게 하고(삭제), free(temp);로 메모리를 해제합니다.

정답: ③ 삭제할 노드가 없는 경우 새 노드를 생성하여 연결 리스트에 추가한다.

4. 다음 재귀 함수 코드에서 함수 Factorial(4)의 반환 값으로 알맞은 것은?

int Factorial(int n){
    if(n == 0) return 1;
    else return n * Factorial(n - 1);
}

① 4

② 6

③ 12

④ 24

개념:

풀이:

제시된 재귀 함수는 n이 0이 될 때까지 n x Factorial(n-1)을 수행하는 팩토리얼(n!) 계산 코드입니다.

Factorial(4) 호출: 4 * Factorial(3)
Factorial(3) 호출: 3 * Factorial(2)
Factorial(2) 호출: 2 * Factorial(1)
Factorial(1) 호출: 1 * Factorial(0)
Factorial(0) 호출: if(n == 0) 조건에 의해 1 반환 (기본 케이스)

반환값 계산: 4x3x2x1x1 = 24

따라서 Factorial(4)의 최종 반환 값은 4x3x2x1x1 = 24

정답: ④ 24

문제 5. 다음은 이진 탐색(Binary Search)을 구현한 코드이다. 해당 코드가 수행하기 위한 전제 조건으로 옳은 것은?

int binarySearch(int arr[], int left, int right, int x) {
    if (right >= left) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == x) return mid;
        if (arr[mid] > x)
            return binarySearch(arr, left, mid - 1, x);
        return binarySearch(arr, mid + 1, right, x);
    }
    return -1;
}

① 배열의 모든 요소는 중복되지 않아야 한다.

② 배열이 반드시 정렬되어 있어야 한다.

③ 배열 크기가 홀수여야 한다.

④ 배열의 요소가 음수가 아니어야 한다.

개념: 이진 탐색 Binary Search

이진 탐색 Binary Search 는 정렬된 배열에서 중간값을 찾아 목표 값(Target)과 비교하고, 대소 관계에 따라 탐색 범위를 절반씩 줄여나가는 탐색 알고리즘입니다.

풀이

이진 탐색(Binary Search) 알고리즘은 정렬된 리스트에서만 작동하며, 핵심은 중간값과 대상값을 비교하여 검색 범위를 절반씩 줄여나가는 것입니다.

① 중복된 요소가 있어도 작동하지만, 반드시 첫 번째 요소를 찾지는 않습니다.
② 이진 탐색의 가장 필수적인 전제 조건은 데이터가 정렬(오름차순 또는 내림차순)되어 있어야 한다는 것입니다.
③ 배열 크기는 짝수/홀수 상관없습니다.
④ 음수도 포함될 수 있습니다.

정답: ② 배열이 반드시 정렬되어 있어야 한다.

문제 6. 다음은 최소신장트리(MST, Minimum Spanning Tree)와 이를 구하는 알고리즘에 대한 설명이다. 이 중 옳지 않은 것은 무엇인가?

① 크루스칼(Kruskal) 알고리즘은 간선을 오름차순으로 정렬한 후, 사이클이 형성되지 않도록 작은 가중치의 간선부터 선택한다.

② 프림(Prim) 알고리즘은 임의의 정점에서 시작하여 인접한 정점 중 최소 가중치 간선을 선택해 신장트리를 확장한다.

③ 최소신장트리는 항상 유일한 형태로 존재하지는 않으며, 동일한 가중치의 간선이 여럿 있다면 여러 가지의 최소신장트리가 나올 수 있다.

④ 최소신장트리는 음수 가중치를 가진 간선을 포함할 수 없으므로, 음수 간선이 있는 그래프에서는 MST를 구할 수 없다.

개념: 최소신장트리(Minimum Spanning Tree, MST

****최소신장트리(Minimum Spanning Tree, MST)는 무방향 가중치 그래프에서 모든 정점을 연결하는 간선들의 가중치 합이 최소가 되는 트리 구조이다. 크루스칼(Kruskal)과 프림(Prim) 알고리즘이 대표적이며, greedy(탐욕) 방식으로 동작한다.

풀이:

① 크루스칼 알고리즘: 모든 간선의 가중치를 오름차순으로 정렬한 후, Union-Find 자료구조를 사용하여 사이클이 발생하지 않는 작은 가중치 간선부터 선택하므로 옳은 설명이다.
② 프림 알고리즘: 임의의 정점에서 시작하여, 현재 연결된 트리에 인접한 정점 중 가장 작은 가중치 간선을 선택해나가며 트리를 확장하므로 옳은 설명이다.
③ 유일성: 그래프에 동일한 가중치를 가진 간선이 여러 개 있다면, MST는 유일하지 않고 여러 개가 존재할 수 있다.
④ 음수 가중치: MST 알고리즘(크루스칼, 프림)은 가중치의 '상대적 순서'에 의존하므로, 음수 가중치를 가진 간선이 있어도 정상적으로 동작하여 MST를 구할 수 있다. 따라서, "음수 간선이 있는 그래프에서는 MST를 구할 수 없다"는 틀린 설명이다.

정답:④ 최소신장트리는 음수 가중치를 가진 간선을 포함할 수 없으므로, 음수 간선이 있는 그래프에서는 MST를 구할 수 없다.

문제 7. 다음의 수식 트리에 대한 중위 순회 결과로 옳은 것은?

    `+
   / \\
  *   -
 / \\ / \\
A  B C  D`

① ABCD*-+

② AB*+CD-

③ A*B+C-D

④ AB*CD-+

개념: 수식 트리(Expression Tree), 순회, 중위 순회(Inorder Traversal)

수식 트리(Expression Tree)의 중위 순회(Inorder Traversal)는 왼쪽 자식 노드 -> 루트 노드 -> 오른쪽 자식 노드 순서로 탐색하며, 이는 우리가 일반적으로 사용하는 중위 표기법(Infix notation) 식을 만들어냅니다.

**풀이:**제시된 수식 트리는 다음과 같습니다.

     `+ (루트)
    / \\
   *   -
  / \\ / \\
 A  B C  D`

전체 루트(+): (왼쪽 서브 트리) + (오른쪽 서브 트리) 형태로 진행됩니다.
왼쪽 서브 트리(*): 'A * B' 순으로 순회합니다.
오른쪽 서브 트리(-): 'C - D' 순으로 순회합니다.
최종 결과: (왼쪽) + (오른쪽)을 결합하면 (A * B + C - D)가 됩니다.

정답: ③ A*B+C-D

문제 8. 다음 중 그래프 탐색 알고리즘인 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)에 대한 설명으로 옳지 않은 것은?

① BFS는 큐(Queue)를 사용하여 인접한 정점부터 순서대로 탐색한다.

② DFS는 스택(Stack) 또는 재귀(recursion)를 사용하여 한 방향으로 최대한 깊이 내려가 탐색한다.

③ BFS는 최단거리 탐색에 자주 활용되며, 모든 간선의 가중치가 동일할 때 특히 유용하다.

④ DFS는 항상 최단 경로를 보장하며, 최적 경로 탐색 알고리즘으로 주로 사용된다.

개념: 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)

깊이 우선 탐색(DFS)은 그래프에서 한 경로를 따라 끝까지 탐색한 후 돌아오는 방식, 너비 우선 탐색(BFS)는 시작점부터 가까운 정점부터 단계적으로 탐색하는 방식이다.

풀이:

①, ②: BFS는 큐, DFS는 스택/재귀를 사용하여 정석적으로 구현한다.③: BFS는 모든 간선의 가중치가 같을 때 최단 경로를 보장한다.
④: DFS는 경로를 탐색할 뿐, 가장 먼저 찾는 경로가 최단 경로임을 보장하지 않는다. 최단 경로는 BFS가 보장한다.

정답: ④ DFS는 항상 최단 경로를 보장하며, 최적 경로 탐색 알고리즘으로 주로 사용된다.

문제 9. 최단거리 그래프 알고리즘에 대한 설명 중 틀린 것은?

① 다익스트라 알고리즘은 음수 간선을 처리하지 못한다.

② 벨만-포드 알고리즘은 음수 간선을 처리할 수 있다.

③ 다익스트라 알고리즘은 항상 가장 긴 경로를 찾는다.

④ 최단거리 알고리즘은 두 노드 간 최소 거리의 경로를 찾는다.

개념: 최단 거리(Shortest Path) 알고리즘, 다익스트라(Dijkstra), 벨만-포드(Bellman-Ford), 장다리 경로(Longest Path) 알고리즘

최단 거리(Shortest Path) 알고리즘은 그래프 내의 특정 노드에서 출발하여 다른 노드로 이동할 때, 거쳐가는 간선들의 가중치 합이 최소가 되는 경로를 찾는 알고리즘입니다.
다익스트라(Dijkstra): 특정 시작 노드에서 다른 모든 노드까지의 최단 거리를 구하는 알고리즘으로, 간선의 가중치가 모두 양수일 때만 정상적으로 작동합니다.
벨만-포드(Bellman-Ford): 다익스트라와 마찬가지로 최단 거리를 구하지만, 음수 가중치가 포함된 그래프에서도 사용 가능하며 음수 사이클의 존재 여부도 확인할 수 있습니다.

풀이:

① 다익스트라 알고리즘은 음수 간선을 처리하지 못한다. (옳음)

다익스트라는 현재 최단 거리라고 판단된 노드를 확정하며 진행하는 그리디 방식이므로, 나중에 가중치를 줄여주는 음수 간선이 등장해도 이미 방문한 노드의 값을 갱신하지 못할 수 있습니다.

② 벨만-포드 알고리즘은 음수 간선을 처리할 수 있다. (옳음)

벨만-포드는 매 단계마다 모든 간선을 확인하기 때문에 음수 가중치를 가진 간선이 있어도 최단 거리를 올바르게 찾아냅니다.

③ 다익스트라 알고리즘은 항상 가장 긴 경로를 찾는다. (틀림)

다익스트라 알고리즘은 가중치의 합이 최소가 되는 경로, 즉 최단 경로를 찾는 알고리즘입니다. 가장 긴 경로를 찾는 알고리즘은 장다리 경로(Longest Path) 알고리즘입니다.

④ 최단거리 알고리즘은 두 노드 간 최소 거리의 경로를 찾는다. (옳음)

최단거리 알고리즘의 정의 그 자체입니다.

정답: ③ 다익스트라 알고리즘은 항상 가장 긴 경로를 찾는다.

문제 10. 아래의 큐(Queue)에 관한 설명 중 맞는 것을 고르시오.

① 큐의 기본 연산인 enqueue와 dequeue는 일반적으로 O(1)의 시간 복잡도를 가진다.

② 큐는 LIFO(Last In First Out) 방식으로 동작하는 자료구조이다.

③ 큐에서 가장 최근에 삽입된 데이터가 가장 먼저 제거된다.

④ 큐에서 데이터 검색은 O(1)의 시간 복잡도를 가진다.

개념: 큐(Queue), FIFO(First-In, First-Out) (선입선출)

큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 FIFO(First-In, First-Out) (선입선출) 방식의 자료구조이다. 큐의 끝(Rear)에서 삽입(Enqueue), 앞(Front)에서 삭제(Dequeue)가 이루어진다.

풀이

① 맞는 설명: 큐는 맨 뒤에서 데이터를 넣고(enqueue), 맨 앞에서 데이터를 꺼내는(dequeue) 구조로, 배열이나 연결 리스트로 구현할 때 위치 포인터만 이동하면 되므로 일반적으로(O(1) (상수 시간)이 소요됩니다.
② 틀린 설명: 큐는 LIFO(Last In First Out, 후입선출)가 아니라, FIFO(First In First Out, 선입선출) 방식으로 먼저 들어온 데이터가 먼저 나가는 구조입니다.
③ 틀린 설명: 큐는 가장 최근에 삽입된 데이터(rear)가 아니라, **가장 먼저 삽입된 데이터(front)**가 가장 먼저 제거됩니다.
④ 틀린 설명: 큐는 특정 위치의 데이터에 직접 접근하는 구조가 아니기 때문에, 검색을 위해서는 데이터를 하나씩 꺼내보아야 하므로 보통 O(n)의 시간 복잡도를 가집니다.

정답: ① 큐의 기본 연산인 enqueue와 dequeue는 일반적으로 O(1)의 시간 복잡도를 가진다.

문제 11. 아래의 배열의 대한 설명 중 틀린 것을 고르시오.

① 배열은 같은 자료형의 데이터를 연속된 메모리 공간에 저장하는 자료구조이다.

② 배열의 인덱스는 일반적으로 0부터 시작하며, 크기가 n인 배열의 마지막 원소는 인덱스 n-1에 위치한다.

③ 배열에서 특정 원소에 접근하는 시간 복잡도는 O(n)이다.

④ 정적 배열은 크기가 고정되어 있어 선언 시 지정된 크기보다 많은 원소를 저장할 수 없다.

개념: 배열(Array)

배열(Array)은 동일한 데이터 타입을 메모리의 연속된 공간에 나열한 자료구조입니다. 인덱스(Index)를 사용하여 원하는 데이터에 직접 접근(Random Access)할 수 있는 것이 가장 큰 특징입니다.

풀이

① 참: 배열은 동일 자료형을 메모리상에 연속적으로 저장합니다.
② 참: 인덱스는 0부터 시작하므로, 크기가 n이면 0 ~ n -1 까지의 인덱스를 가집니다.
③ 거짓: 배열은 인덱스를 통한 직접 접근이 가능하므로 특정 원소에 접근하는 시간 복잡도는 O(1) (상수 시간)입니다. O(n)은 선형 검색(Linear Search)을 할 때의 시간 복잡도입니다.
④ 참: 정적 배열은 메모리 할당 시 크기가 고정되어 변경할 수 없습니다.

정답: ③ 배열에서 특정 원소에 접근하는 시간 복잡도는 O(n)이다.

문제 12. UML 다이어그램의 설명 중 옳은 것은?

① 클래스 다이어그램은 시스템의 동적 행동을 나타낸다.

② 시퀀스 다이어그램은 객체 간 상호작용의 시간적 순서를 나타낸다.

③ 유스케이스 다이어그램은 데이터베이스 구조를 나타낸다.

④ 상태 다이어그램은 데이터 흐름을 나타낸다.

개념: UML 다이어그램

구조 다이어그램 (Static): 클래스, 객체, 컴포넌트, 배치 다이어그램 등 (시스템의 정적 구조)
행위 다이어그램 (Dynamic): 시퀀스, 유스케이스, 활동, 상태 다이어그램 등 (시스템의 동적 상호작용 및 행동)

풀이:

① 클래스 다이어그램은 시스템의 동적 행동을 나타낸다. (거짓)
- 클래스 다이어그램은 시스템의 정적 구조(클래스, 속성, 관계)를 나타냅니다.
② 시퀀스 다이어그램은 객체 간 상호작용의 시간적 순서를 나타낸다. (참)
- 시퀀스 다이어그램은 시간의 흐름에 따라 객체들이 주고받는 메시지 순서를 강조하는 행위 다이어그램입니다.
③ 유스케이스 다이어그램은 데이터베이스 구조를 나타낸다. (거짓)
- 유스케이스 다이어그램은 사용자 관점에서 시스템의 기능과 외부 엑터와의 상호작용을 나타냅니다. 데이터베이스 구조는 ERD 등을 사용합니다.
④ 상태 다이어그램은 데이터 흐름을 나타낸다. (거짓)
- 상태 다이어그램은 하나의 객체가 생명 주기 동안 갖는 상태 변화를 나타냅니다. 데이터 흐름은 DFD(Data Flow Diagram)가 나타냅니다.

정답: ② 시퀀스 다이어그램은 객체 간 상호작용의 시간적 순서를 나타낸다.

문제 13. 다음은 (ㄱ) 정렬 알고리즘의 주요 특징이다. (ㄱ)에 해당하는 정렬 알고리즘을 고르시오.

배열의 처음부터 끝까지 반복적으로 인접한 두 원소를 비교한다.

만약 앞의 원소가 뒤의 원소보다 크다면 두 원소의 위치를 교환한다.

한 번의 전체 반복이 끝나면 가장 큰 원소가 맨 뒤로 "떠오르게" 된다.

배열의 크기가 n일 때, 최대 n-1번의 전체 반복을 수행한다.

구현이 매우 단순하지만, 대부분의 상황에서 다른 정렬 알고리즘보다 성능이 떨어진다.

① 삽입 정렬(Insertion Sort)

② 버블 정렬(Bubble Sort)

③ 퀵 정렬(Quick Sort)

④ 선택 정렬(Selection Sort)

개념: 정렬 알고리즘, 삽입 정렬(Insertion Sort), 버블 정렬(Bubble Sort), 퀵 정렬(Quick Sort), 선택 정렬(Selection Sort)

**버블 정렬(Bubble Sort)**은 서로 인접한 두 원소를 비교하여, 정렬 기준(오름차순/내림차순)에 맞지 않으면 자리를 교환하는 방식의 단순 정렬 알고리즘이다. 물방울이 수면 위로 올라오는 것처럼 가장 큰 원소가 맨 뒤로 이동하는 모습 때문에 '버블' 정렬이라 부른다.

풀이:

인접한 두 원소 비교 및 교환: 버블 정렬의 가장 핵심적인 특징이다.
가장 큰 원소가 맨 뒤로 "떠오름": 한 번의 패스(pass)가 끝나면 가장 큰 값이 맨 마지막 자리로 이동한다.
(n-1)번의 전체 반복: n개의 원소일 때 최대 (n-1)번 전체 배열을 순회한다.
단순 구현 vs 낮은 성능: 알고리즘이 직관적이고 구현이 쉬우나, 시간 복잡도가 최악, 평균 모두 O(n^2) 으로 매우 비효율적이다.
① 삽입 정렬은 앞부분의 정렬된 부분에 삽입하는 방식
③ 퀵 정렬은 피벗(pivot)을 이용한 분할 정복 방식
④ 선택 정렬은 최소값을 찾아 맨 앞으로 보내는 방식이다.

정답: ② 버블 정렬(Bubble Sort)

문제 14. 다음은 어떤 자료 구조와 관련 있는 개념에 대한 설명이다. 이것이 무엇에 대한 설명인지 고르시오.

컴퓨터에서 데이터를 빠르게 찾기 위해 '주소 값'을 계산하는 방법이 있다. 이 방법은 데이터마다 특별한 계산식을 통해 보관 위치를 정해주는데, 가끔 서로 다른 데이터가 같은 보관 위치를 받게 되는 문제가 생긴다. 예를 들어, '사과'와 '바나나'라는 데이터가 모두 '5번 위치'에 저장되어야 한다고 계산되면, 두 데이터를 어떻게 모두 보관할지 결정해야 한다. 이런 문제를 해결하기 위해 '연결 목록으로 여러 데이터 보관하기', '다음 빈자리 찾아가기' 같은 방법들이 사용된다. 이러한 상황이 자주 발생하면 데이터를 찾는 속도가 느려지기 때문에, 좋은 시스템은 이런 현상이 적게 일어나도록 설계한다.

① 데이터 손실

② 해시 충돌(Hash Collision)

③ 데이터 중복

④ 데드락(Deadlock)

개념: 해시 테이블(Hash Table)

**해시 테이블(Hash Table)**은 키(Key) 값을 해시 함수를 통해 계산된 '주소값(인덱스)'을 사용하여 데이터를 저장하는 구조입니다.

풀이:

서로 다른 두 개의 데이터('사과', '바나나')가 해시 함수를 거쳐 같은 주소(5번 위치)를 계산받게 되는 현상을 **해시 충돌(Hash Collision)**이라고 합니다.
이 문제를 해결하기 위해 제시된 '연결 목록으로 여러 데이터 보관하기'는 체이닝(Chaining), '다음 빈자리 찾아가기'는 **개방 주소법(Open Addressing, 선형 탐사)**이라는 대표적인 충돌 해결 기법입니다.
데이터 손실: 충돌의 결과일 수는 있으나 현상 자체를 뜻하지 않음.
데이터 중복: 해시 테이블에서 key는 고유해야 함.
데드락: 교착 상태로, 주로 멀티 스레딩 환경에서 자원 배분 시 발생.

정답: ② 해시 충돌(Hash Collision)

문제 15. 게임 개발자 최코딩은 RPG 게임의 스킬 트리 시스템을 구현하고 있다. 이 스킬 트리는 아래 그림과 같이 구성되어 있다. 아래의 스킬 트리에서 콤보 효과를 위한 최적의 스킬 발동 순서는 무엇인지 고르시오.

볼 마법(A) | | 번개 볼트(B) 화염 폭발(C) | | | 총격파(D) 용암터대(E) 블레이징(F)

최코딩은 게임 캐릭터가 스킬을 모두 배웠을 때, 특정 순서로 스킬을 실행하면 "콤보 효과"가 발동되도록 프로그래밍하려고 한다. 이 콤보 효과는 각 스킬을 배운 순서대로가 아니라, "왼쪽 서브트리의 모든 스킬 → 오른쪽 서브트리의 모든 스킬 → 현재 노드의 스킬" 순서로 실행해야 최대 데미지를 낼 수 있다.

① 전위순회

② 후위순회

③ 중위순회

④ 역중위순회

개념:

풀이:

문제에서 제시한 콤보 효과의 스킬 발동 순서는 "왼쪽 서브트리 → 오른쪽 서브트리 → 현재 노드"입니다. 이는 트리 자료구조의 순회 방식 중 후위순회(Postorder Traversal, Left-Right-Root)의 정의와 정확히 일치합니다.

① 전위순회 (Preorder): 루트 → 왼쪽 → 오른쪽
② 후위순회 (Postorder): 왼쪽 → 오른쪽 → 루트 (정답)
③ 중위순회 (Inorder): 왼쪽 → 루트 → 오른쪽
④ 역중위순회 (Reverse Inorder): 오른쪽 → 루트 → 왼쪽

주어진 스킬 트리 구조를 기반으로 후위순회(왼쪽-오른쪽-루트)를 적용하면 다음과 같은 순서가 됩니다.

최상위 노드 A(볼 마법)에서 시작.
왼쪽 서브트리인 B(번개 볼트) 하위 노드 탐색.
B의 왼쪽이 없으므로, B의 오른쪽인 D(총격파) 확인.
하위 노드부터 처리: D(총격파) → B(번개 볼트)
오른쪽 서브트리인 C(화염 폭발) 하위 노드 탐색.
C의 왼쪽 E(용암터대)와 오른쪽 F(블레이징) 처리: E → F → C
마지막으로 루트인 A(볼 마법) 처리.

즉, 자식 스킬(하위 트리)을 모두 발동한 후 부모 스킬을 발동하는 방식이므로 후위순회가 맞습니다.

스킬 트리 적용 결과:볼 마법(A)을 루트로 하여, 왼쪽 서브트리(B, D)와 오른쪽 서브트리(C, E, F)를 거쳐 최종적으로 볼 마법(A)이 발동됩니다.

콤보 순서: 충격파 (D) → 번개 볼트(B) → 용암터대(E) → 블레이징(F) → 화염 폭발(C) → 볼 마법(A)

정답: ② 후위순회

문제 16. 아래는 게임에서 캐릭터 스킬 트리를 구현하기 위한 이진트리 코드의 일부이다. 이 코드는 게임에서 캐릭터의 스킬을 파워에 따라 이진트리로 정렬하여 저장한다. 빈칸에 들어갈 적절한 코드를 고르시오.

struct SkillNode {
    string skillName;
    int power;
    SkillNode* left;
    SkillNode* right;
};

// 새로운 스킬 노드를 추가하는 함수
void addSkill(SkillNode* &root, string name, int power) {
    if (root == nullptr) {
        root = new SkillNode{name, power, nullptr, nullptr};
        return;
    }
    if (power < root->power) {
        ________________; // 빈칸
    } else {
        addSkill(root->right, name, power);
    }
}

① root->left = new SkillNode{name, power, nullptr, nullptr} ② addSkill(root->left, name, power) ③ return addSkill(root->left, name, power) ④ root = root->left

개념: 이진 탐색 트리(Binary Search Tree, BST), 재귀(Recursion) 알고리즘

이진 탐색 트리(Binary Search Tree, BST)에서 노드를 삽입하는 재귀(Recursion) 알고리즘입니다. 새로운 스킬의 파워(power)가 현재 노드의 파워(root->power)보다 작으면 왼쪽 자식 노드(root->left)로 이동하여 재귀적으로 addSkill을 호출하여 빈 공간을 찾습니다.

풀이:

함수의 정의를 보면 addSkill(SkillNode* &root, ...)으로 root를 참조자(Reference)로 받고 있습니다. 이는 nullptr인 위치를 찾아 새로운 노드를 할당할 때, 이전 노드의 left 또는 right 포인터 값을 직접 변경해주기 위함입니다.
if (power < root->power) 조건문은 새로운 스킬이 현재 스킬보다 파워가 작을 때, 더 작은 파워를 가진 왼쪽 서브트리로 들어가야 함을 의미합니다.
따라서, 왼쪽 자식(root->left)을 대상으로 다시 addSkill 함수를 재귀적으로 호출하여 빈 공간을 찾아야 하므로 ②번이 정답입니다.

①번: 새로운 노드를 직접 할당하고 있지만, 재귀적인 구조를 사용하지 않아 잘못된 위치에 연결될 수 있습니다.
③번: void형 함수는 return 시 값을 반환할 수 없습니다.
④번: root 자체를 root->left로 변경하면 트리 구조가 깨집니다.

정답: ② addSkill(root->left, name, power)

문제 17. 다음은 알고리즘의 성능 분석과 관련된 설명이다. 틀린 것을 고르시오.

① 게임 내 캐릭터의 이동 경로를 찾는 알고리즘에서 O(n²) 표기법은 맵의 크기(n)가 2배로 커지면 실행 시간이 약 4배 증가함을 의미한다.

② 게임 아이템 정렬 알고리즘에서 '최악의 경우 시간복잡도'는 플레이어가 가진 아이템이 가장 많을 때 게임이 버벅거리지 않도록 미리 예측하는 데 중요하다.

③ 대규모 멀티플레이어 게임에서 플레이어 매칭 알고리즘의 공간복잡도는 알고리즘이 사용하는 메모리 양을 분석하여 서버 자원을 효율적으로 사용할 수 있게 한다.

④ 게임 내 경험치 계산 알고리즘의 시간복잡도는 항상 입력 크기와 관계없이 일정하므로, 어떤 알고리즘이든 플레이어 수가 많아져도 동일한 처리 속도를 유지한다.

개념: 알고리즘 성능 분석(시간 복잡도, 공간 복잡도)

풀이:

풀이:

① 옳음: O(n^2) 은 입력 크기 n의 제곱에 비례하는 시간 복잡도를 가집니다. n이 2배가 되면 (2^2 = 4)배의 시간이 걸립니다.
② 옳음: 최악의 경우 시간복잡도(Worst-case)는 알고리즘이 가질 수 있는 가장 느린 경우를 분석하여, 데이터가 많아도 게임이 멈추지 않도록 보장하는 데 사용됩니다.
③ 옳음: 공간 복잡도는 알고리즘이 사용하는 메모리 공간을 분석하므로 서버 자원을 효율적으로 관리하는 데 필요합니다.
• ④ 틀림: 시간복잡도가 일정하다는 것은 O(1) 을 의미하며, 입력 크기(n)에 상관없이 항상 일정한 시간이 걸린다는 뜻입니다. 그러나 모든 경험치 계산 알고리즘이 O(1) 인 것은 아닙니다. 예를 들어, 전체 플레이어 목록을 순회하며 계산한다면 O(n) 이 되어 플레이어 수가 많아지면 처리 속도가 느려집니다.

정답: ④ 게임 내 경험치 계산 알고리즘의 시간복잡도는 항상 입력 크기와 관계없이 일정하므로, 어떤 알고리즘이든 플레이어 수가 많아져도 동일한 처리 속도를 유지한다.

문제 18. 게임 개발에서 그래프 알고리즘이 사용되는 이유에 대한 설명 중 틀린 것을 고르시오.

① 길찾기(Pathfinding): 다익스트라나 A* 알고리즘을 사용하여 게임 캐릭터가 출발지에서 목적지까지 최단 경로를 찾을 수 있다.

② 네트워크 시뮬레이션: 멀티플레이어 게임에서 플레이어 간의 연결 상태를 그래프로 모델링하여 데이터 전송 경로를 최적화할 수 있다.

③ 게임 밸런싱: 그래프 알고리즘은 게임 내 아이템과 능력치 간의 관계를 분석하여 항상 모든 전략이 동등한 승률을 가지도록 자동으로 조정한다.

④ 퀘스트 시스템: 게임 내 스토리와 퀘스트를 그래프 구조로 관리하여 플레이어의 진행 상태에 따라 새로운 퀘스트를 제공할 수 있다.

개념: 게임 개발에서의 그래프 알고리즘 활용 (길찾기, 네트워크, 퀘스트, 관계 분석 등)

풀이:

① 길찾기(Pathfinding): A* 알고리즘 등은 게임에서 캐릭터가 장애물을 피해 최단 경로를 찾는 데 필수적으로 사용됩니다. (옳음)
② 네트워크 시뮬레이션: 멀티플레이어 게임에서 서버와 클라이언트, 혹은 노드 간의 데이터 전송 경로를 최적화하기 위해 그래프 이론을 사용합니다. (옳음)
③ 게임 밸런싱: 그래프 알고리즘을 이용해 아이템 간의 관계를 분석할 수는 있으나, 모든 전략이 항상 동등한 승률을 가지도록 '자동'으로 조정하는 것은 불가능합니다. 게임 밸런싱은 데이터 분석을 기반으로 개발자가 조정하는 영역입니다. (틀림)
④ 퀘스트 시스템: 퀘스트의 선후 관계, 조건(조건 A 완료 시 퀘스트 B 발생) 등을 유향 그래프(Directed Graph) 구조로 관리하여 복잡한 스토리 라인을 구현합니다. (옳음)

정답: ③ 게임 밸런싱: 그래프 알고리즘은 게임 내 아이템과 능력치 간의 관계를 분석하여 항상 모든 전략이 동등한 승률을 가지도록 자동으로 조정한다.

문제 19. 다음은 게임에서 물체의 이동을 구현하기 위한 C++ 벡터 연산 코드다. 빈칸에 들어갈 적절한 코드를 고르시오.

#include <iostream>
#include <cmath>

class Vector2D {
public:
    float x, y;
    Vector2D(float x, float y) : x(x), y(y) {}

    Vector2D add(const Vector2D& other) {
        return Vector2D(x + other.x, y + other.y);
    }
    Vector2D scale(float scalar) {
        return Vector2D(x * scalar, y * scalar);
    }
    float getMagnitude() {
        return (         );
    }
};

int main() {
    Vector2D playerVelocity(3, 4);
    float speed = playerVelocity.getMagnitude();
    std::cout << "플레이어 속도: " << speed << std::endl; // 출력: 플레이어 속도: 5
    return 0;
}

① x + y

② (x * x + y * y) / 2

③ sqrt(x * x + y * y)

④ abs(x) + abs(y)

개념:

벡터의 크기(Magnitude) 또는 길이는 피타고라스의 정리를 이용하여 계산합니다. 2차원 벡터 (vec{v} = (x, y))의 크기는 원점에서 해당 점까지의 거리와 같으며, 공식은 sqrt{x^{2}+y^{2}} 입니다.

풀이:

getMagnitude() 함수는 벡터의 크기(\(\sqrt{x^{2}+y^{2}}\))를 반환해야 합니다.
cmath 라이브러리를 사용하므로 제곱근을 구하는 함수 sqrt()를 사용합니다.
x의 제곱은 x * x 또는 pow(x, 2)로 표현할 수 있습니다.
따라서, sqrt(x * x + y * y)가 올바른 코드입니다.
예시의 (3, 4) 벡터를 대입하면 sqrt{3^2 + 4^2} = sqrt{9 + 16} = sqrt{25} = 5 가 되어 출력 결과와 일치합니다.

① x + y: 단순히 성분을 더한 것으로 크기가 아닙니다.
② (x * x + y * y) / 2: 잘못된 공식입니다.
④ abs(x) + abs(y): 택시 거리(Manhattan distance) 공식입니다.

정답: ③ sqrt(x * x + y * y)

문제 20. 다음은 게임 개발에서 사용되는 디자인 패턴에 대한 설명이다. 이 설명이 가리키는 디자인 패턴으로 가장 적절한 것을 고르시오.

이 패턴은 게임 캐릭터의 상태(예: 대기, 걷기, 공격, 점프 등)가 변할 때 캐릭터의 행동이 변경되도록 하는 패턴이다. 플레이어가 버튼을 누를 때마다 캐릭터는 현재 상태에 따라 다르게 반응하며, 상태가 바뀌면 캐릭터의 전체 행동 방식이 바뀐다. 이것은 마치 캐릭터가 다른 모드로 전환되는 것과 같다.

① 옵저버 패턴(Observer Pattern)

② 싱글톤 패턴(Singleton Pattern)

③ 상태 패턴(State Pattern)

④ 팩토리 패턴(Factory Pattern)

개념: 디자인 패턴: 옵저버 패턴(Observer Pattern), 싱글톤 패턴(Singleton Pattern), 상태 패턴(State Pattern), 팩토리 패턴(Factory Pattern)

상태 패턴(State Pattern)은 객체의 내부 상태가 변경될 때 행동을 변경하는 행위 디자인 패턴입니다. 객체가 마치 클래스를 바꾸는 것처럼 보이게 하여, 복잡한 if-else나 switch 문 대신 상태마다 클래스를 만들어 행동을 캡슐화합니다.

풀이:

문제 설명: 게임 캐릭터가 대기, 걷기, 공격 등 상태가 바뀔 때 행동 방식이 전체적으로 변경되며, 이는 마치 다른 모드로 전환되는 것과 같다는 설명은 상태 패턴의 전형적인 정의입니다.
상태별 행동 캡슐화: 캐릭터의 상태(State)를 클래스(IdleState, WalkState, JumpState 등)로 분리하여 관리하므로 유지보수가 쉽습니다.
정답 근거: 런타임 중에 객체의 행동을 상태에 따라 동적으로 변경해야 할 때 사용되는 패턴입니다.

오답 분석:

① 옵저버 패턴: 한 객체의 상태 변화에 따라 다른 객체들의 상태를 자동으로 업데이트하는 패턴 (구독/발행).
② 싱글톤 패턴: 클래스의 인스턴스를 하나만 생성하여 전역적으로 접근하도록 보장하는 패턴.
④ 팩토리 패턴: 객체 생성 로직을 캡슐화하여 구체적인 클래스에 의존하지 않고 객체를 생성하는 생성 패턴.

정답: ③ 상태 패턴(State Pattern)

문제 21. 최근 국내 게임에서 블록체인 기술을 접목하여 대체불가능토큰(NFT, Non-Fungible Token)으로 게임 아이템 소유 인증을 받는 기술이 화제다. 블록체인에도 많이 쓰이는 해시 테이블(Hash Table)에 대한 설명 중 잘못된 것은?

① 해시 테이블은 키-값(Key, Value)으로 데이터를 저장하는 자료구조 중 하나로 내부적으로 배열(Bucket)을 사용하여 데이터를 저장하기 때문에 빠르게 데이터를 검색할 수 있는 자료구조다.

② 해시 함수(Hash Function)는 인자에 키(Key)를 넣어 데이터를 고정된 길이의 해시 값(Hash Value)으로 리턴해주는 함수다.

③ 해시 값이 충돌하는 문제를 해결하기 위해서 동일 버킷 데이터에 대해 추가 메모리를 사용하여 다음 데이터 주소를 저장하는 분리연결법(Separate Chaining)과 비어있는 해시테이블 공간을 활용하는 개방주소법(Open Addressing)을 사용한다.

④ 해시 테이블의 시간복잡도는 각각의 키 값에 대하여 해시 함수에 의해 고유한 인덱스를 가지고 바로 접근할 수 있어 평균 O(n)이 걸리고, 해시 충돌 경우에는 분리연결법에서 연결된 리스트들까지 검색을 해야 하므로 O(n)까지 증가할 수 있다.

개념: 해시 테이블 (Hash Table)

해시 테이블(Hash Table)은 키(Key)를 해시 함수(Hash Function)를 통해 인덱스로 변환하고, 그 인덱스에 데이터를 저장하는 방식의 자료구조이다. 평균적으로 매우 빠른 데이터 검색(O(1))을 제공하지만, 해시 충돌(Hash Collision)이 발생할 경우 분리연결법(Separate Chaining)이나 개방주소법(Open Addressing)으로 해결한다.

풀이:

① 옳음: 키-값 쌍을 저장하며 내부 배열(Bucket)을 사용하여 즉시 접근(Direct Access)하므로 데이터 검색이 빠르다.
② 옳음: 키를 입력받아 일정한 길이의 인덱스(Hash Value)로 변환하는 것이 해시 함수의 역할이다.
③ 옳음: 충돌 해결을 위해 리스트를 연결하는 분리연결법과 비어있는 버킷을 찾는 개방주소법을 사용한다.
④ 틀림: 해시 테이블의 평균 시간복잡도는 O(1)(상수 시간)이다. 모든 키가 하나의 인덱스로 몰리는 최악의 경우에만 O(n)이 된다.

[오답 분석]

④ 번이 잘못된 이유: 해시 테이블의 평균적인 검색, 삽입, 삭제 시간 복잡도는 O(n)이 아니라 O(1)이다. 해시 함수가 데이터를 골고루 분산시키지 못하거나, 충돌이 많이 발생하는 최악의 경우에 O(n)이 된다.

정답: ④ 해시 테이블의 시간복잡도는 각각의 키 값에 대하여 해시 함수에 의해 고유한 인덱스를 가지고 바로 접근할 수 있어 평균 O(n)이 걸리고, 해시 충돌 경우에는 분리연결법에서 연결된 리스트들까지 검색을 해야 하므로 O(n)까지 증가할 수 있다.

문제 22. 다음 중 일반적인 알고리즘에 대한 설명으로 적합하지 않은 것은?

① 욕심쟁이 알고리즘(Greedy Algorithm) : 매 순간 가장 좋아 보이는 것을 선택하여 결정하는 알고리즘.

② 분할 정복 알고리즘(Divide and Conquer Algorithm) : 큰 문제를 하위 문제로 나누어 나중에 재결합하는 알고리즘.

③ 무작위 알고리즘(Random Algorithm) : 난수를 절차적인 방법으로 이용하여 하위문제가 독립적이지 않은 문제에 대해서 해결하는 알고리즘.

④ 근사 알고리즘(Approximation Algorithm) : 최적의 해를 구하는 대신에 충분히 좋은 것을 구하는 알고리즘.

개념: 알고리즘, 욕심쟁이 알고리즘(Greedy Algorithm), 분할 정복 알고리즘(Divide and Conquer Algorithm), 무작위 알고리즘(Random Algorithm), 근사 알고리즘(Approximation Algorithm)

무작위 알고리즘(Randomized Algorithm, 확률적 알고리즘) : 절차의 일부에 난수(Random Number)를 사용하여 실행 과정이나 결과가 확률적으로 결정되는 알고리즘입니다. 주로 퀵 정렬(Quicksort)의 피벗 선택처럼 결정론적 알고리즘보다 평균 수행 시간이 빠르거나, 최적해를 구하기 어려운 경우 난수를 이용해 합리적인 시간에 근사치를 구하기 위해 사용됩니다.
하위문제의 독립성: "하위 문제가 독립적이지 않다"는 표현은 주로 **동적 계획법(Dynamic Programming)**이나 무작위 알고리즘의 특정 상황(병렬 처리 등)에 대한 설명일 수 있으나, 난수를 이용해 문제를 해결하는 주된 이유나 정의는 아닙니다. 무작위 알고리즘은 오히려 전체적인 독립성을 유지하면서 무작위 선택을 통해 난관을 극복하는 방식입니다.

풀이:

① 탐욕 알고리즘(Greedy Algorithm) : 매 순간 지역적으로 최적인 선택을 하여 최종적인 전역 최적해를 찾는 방법입니다.
② 분할 정복 알고리즘(Divide and Conquer) : 큰 문제를 하위 문제로 분할하고, 이를 해결한 후 합쳐서(Merge) 전체 문제를 해결하는 방식입니다.
③ 무작위 알고리즘 : 난수를 사용하여 문제를 해결하는 알고리즘으로, 하위문제의 독립성 여부가 이 알고리즘의 핵심 정의가 아닙니다.
④ 근사 알고리즘(Approximation Algorithm) : NP-난해(NP-hard) 문제처럼 최적해를 찾기 어려운 문제에 대해, 최적해에 근접한 솔루션을 빠른 시간 내에 구하는 알고리즘입니다.

정답: ③ 무작위 알고리즘(Random Algorithm) : 난수를 절차적인 방법으로 이용하여 하위문제가 독립적이지 않은 문제에 대해서 해결하는 알고리즘.

문제 23. 다음은 자료구조 중 데크(Deque)에 대한 설명으로 틀린 것을 고르시오.

① 데크는 Double-Ended Queue의 줄임말인 Deque 이다.

② 데크는 큐의 양쪽 끝에서 삽입과 삭제가 모두 가능한 큐의 변형 자료 구조이다.

③ 데크는 논리적으로 배열의 시작과 끝이 연결되어 있는 것으로 간주되며 원형으로 보통 연결되어 있다.

④ 데크에는 입력 제한을 설정한 스크롤(SCROLL)과 출력 제한을 설정한 셸프(SHELF)가 있다.

개념: 데크(Deque, Double-Ended Queue)

데크(Deque, Double-Ended Queue)는 선형 리스트의 양쪽 끝에서 데이터의 삽입과 삭제를 허용하는 자료 구조입니다.

풀이:

데크는 기본적으로 일직선 형태의 선형 구조이며, 배열의 양 끝이 연결된 원형 구조는 원형 큐의 특징이므로 3번 설명은 틀렸습니다.

데크(Deque)는 양쪽 끝에서 삽입과 삭제가 가능한 선형 자료 구조입니다. 논리적으로 시작과 끝이 연결되어 원형으로 간주되는 구조는 데크가 아니라 **원형 큐(Circular Queue)**에 대한 설명입니다.

① 데크는 Double-Ended Queue의 줄임말인 Deque 이다. (O)
- 데크는 이름 그대로 양쪽 끝(Double-ended)이 있는 큐를 의미합니다.
② 데크는 큐의 양쪽 끝에서 삽입과 삭제가 모두 가능한 큐의 변형 자료 구조이다. (O)
- 스택(Stack)과 큐(Queue)의 장점을 결합하여 Front와 Rear 양단에서 입출력이 모두 가능하도록 설계되었습니다.
④ 데크에는 입력 제한을 설정한 스크롤(SCROLL)과 출력 제한을 설정한 셸프(SHELF)가 있다. (O)
- 스크롤(Scroll): 한쪽으로만 입력이 가능하고 양쪽에서 출력이 가능한 입력 제한 데크입니다.
- 셸프(Shelf): 양쪽에서 입력이 가능하고 한쪽으로만 출력이 가능한 출력 제한 데크입니다.

정답: ③ 데크는 논리적으로 배열의 시작과 끝이 연결되어 있는 것으로 간주되며 원형으로 보통 연결되어 있다.

문제 24. 스타크래프트와 같은 전략 시뮬레이션 게임을 작성하고자 한다. 어떤 유닛(unit)에게 명령어를 연속하여 입력하여 순서대로 예약하고자 한다면 어떤 자료구조를 사용하는 것이 가장 적당한가?

① 스택 자료구조를 사용하여 명령어를 push하여 넣고, pop하여 각 명령어를 처리한다.

② 원형 큐 자료구조에 명령어를 넣고, delete하면서 명령어를 처리한다.

③ 트리구조에 명령어를 넣고, 루트부터 시작하여 전위 순회를 하면서 차례로 처리한다.

④ FSM 그래프 자료 구조를 만들어 명령어를 넣고, 순차적으로 명령어를 처리한다.

개념: 자료구조, 큐 (Queue), 스택 (Stack), 원형 큐 (Circular Queue)

큐(Queue) 는 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO, First-In-First-Out) 구조입니다. 게임에서 유닛의 명령어 예약(Shift 클릭 등)은 입력된 순서대로 처리되어야 하므로 큐가 적합합니다.
원형 큐(Circular Queue)는 큐의 단점인 고정된 크기 내에서 재사용성을 높여, 제한된 명령어 예약 공간(스타크래프트의 경우 8회 등)을 효율적으로 관리할 때 적합한 자료구조입니다.

풀이:

1. 연속 입력된 명령어 처리: 유닛에게 A -> B -> C 순서로 이동 명령을 예약하면, A, B, C 순서대로 실행되어야 하므로, 먼저 들어온 명령을 먼저 처리하는 큐가 필요합니다.
1. 원형 큐의 장점: 일반적인 선형 큐는 배열의 끝에 도달하면 데이터를 앞으로 당겨야 하는 비효율이 있지만, 원형 큐는 인덱스를 0부터 다시 활용하여(원형으로 연결) 큐가 꽉 차지 않는 한 지속적으로 명령을 넣고 빼는(enqueue/dequeue) 작업을 O(1) 시간 내에 처리할 수 있습니다.

오답 분석:

① 스택(Stack)은 후입선출(LIFO)이라 마지막 명령이 가장 먼저 처리됩니다.
③ 트리는 계층 구조를 다룰 때 적합하며 순차 예약에는 과도합니다.
④ FSM(유한 상태 머신)은 상태 전환을 관리하지만, 명령어 예약 대기열 자체는 큐로 구현됩니다.

정답: ② 원형 큐 자료구조에 명령어를 넣고, delete하면서 명령어를 처리한다.

문제 25. 다음은 최단경로 알고리즘에 대한 설명의 일부분이다. 이 특징에 가장 가까운 알고리즘을 고르시오.

Ⓐ 하나의 정점에서 다른 하나의 정점까지의 최단경로를 구하는 것이 아닌 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이다.

Ⓑ 우선순위 큐를 사용해서 방문하지 않은 정점들을 시작점으로부터의 거리에 따라 저장한다.

Ⓒ 항상 하나의 시작점으로부터 그래프의 다른 모든 정점들 중에서 다음으로 가까운 정점을 선택한다.

Ⓓ 그래프의 어떤 간선도 음수 값을 가지지 않는다.

① 벨만-포드(Bellman-Ford) 알고리즘

② 다익스트라(Dijkstra) 알고리즘

③ A*(A Star) 알고리즘

④ BFS(Breadth First Search) 알고리즘

개념: 최단경로 알고리즘, 벨만-포드(Bellman-Ford), 다익스트라(Dijkstra), A*(A Star), BFS(Breadth First Search)

다익스트라(Dijkstra) 알고리즘은 그래프에서 특정 시작점(노드)에서 다른 모든 정점까지의 최단 경로를 찾는 단일 시작점 최단 경로(Single-Source Shortest Path) 알고리즘입니다.
Greedy(탐욕법) 접근 방식을 기반으로 하며, 우선순위 큐(Priority Queue)를 사용하여 처리되지 않은 정점 중 가장 가까운 정점을 효율적으로 선택합니다.

풀이:

Ⓐ (1:N): 시작점에서 다른 모든 정점까지의 최단거리를 구합니다.
Ⓑ (우선순위 큐): heapq 같은 우선순위 큐를 사용하여 가장 거리가 짧은 노드를 우선적으로 탐색합니다.
Ⓓ (양수 간선): 간선의 가중치가 음수가 아닐 때만 정상적으로 작동합니다. 음수 간선이 있으면 최적성 보장이 깨집니다.

따라서 위 특징을 모두 만족하는 알고리즘은 다익스트라입니다.

벨만-포드는 음수 가중치를 처리하지만 우선순위 큐를 기반으로 하지 않고
A*는 1:1 최단경로이며
BFS는 가중치가 없는 그래프에 사용됩니다.

정답: ② 다익스트라(Dijkstra) 알고리즘

게임국가기술자격검정 게임프로그래밍전문가 [한국콘텐츠진흥원] | 종합

About this Certification 홈페이지: https://www.kgq.or.kr/service/main.do검정안내: https://www.kgq.or.kr/service/info/cert.do국가기술자격증 (유효기간 없음)Since 2003시험일정 : https://www.kgq.or.kr/service/rcpt/sc_list.do원서접

devcol.tistory.com

필기시험 관련 기초 개념 공부 | 게임국가기술자격검정 게임프로그래밍전문가 [한국콘텐츠진흥원]

저작자표시 동일조건 (새창열림)

Part2. 게임 알고리즘과 설계: 1~25 | 2025 게임 프로그래밍 전문가 국가기술 자격검정 필기시험 B 풀이 | 게임국가기술자격검정 게임프로그래밍전문가 [한국콘텐츠진흥원]

Part 2. 게임 알고리즘과 설계 | 2025 게임 프로그래밍 전문가 국가기술 자격검정 필기시험 B 풀이

1. 다음 중 게임 내 물리 엔진을 활용하여 중력과 마찰력 등을 구현하는 이유로 가장 적합한 설명은?

2. 다음은 선택 정렬을 구현한 코드이다. 빈칸 (A)를 채우기 위한 코드로 알맞은 것은?

3. 다음 단순 연결 리스트 노드 삭제 코드 중 옳지 않은 설명은?

4. 다음 재귀 함수 코드에서 함수 Factorial(4)의 반환 값으로 알맞은 것은?

문제 5. 다음은 이진 탐색(Binary Search)을 구현한 코드이다. 해당 코드가 수행하기 위한 전제 조건으로 옳은 것은?

문제 6. 다음은 최소신장트리(MST, Minimum Spanning Tree)와 이를 구하는 알고리즘에 대한 설명이다. 이 중 옳지 않은 것은 무엇인가?

문제 7. 다음의 수식 트리에 대한 중위 순회 결과로 옳은 것은?

문제 8. 다음 중 그래프 탐색 알고리즘인 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)에 대한 설명으로 옳지 않은 것은?

문제 9. 최단거리 그래프 알고리즘에 대한 설명 중 틀린 것은?

문제 10. 아래의 큐(Queue)에 관한 설명 중 맞는 것을 고르시오.

문제 11. 아래의 배열의 대한 설명 중 틀린 것을 고르시오.

문제 12. UML 다이어그램의 설명 중 옳은 것은?

문제 13. 다음은 (ㄱ) 정렬 알고리즘의 주요 특징이다. (ㄱ)에 해당하는 정렬 알고리즘을 고르시오.

문제 14. 다음은 어떤 자료 구조와 관련 있는 개념에 대한 설명이다. 이것이 무엇에 대한 설명인지 고르시오.

문제 15. 게임 개발자 최코딩은 RPG 게임의 스킬 트리 시스템을 구현하고 있다. 이 스킬 트리는 아래 그림과 같이 구성되어 있다. 아래의 스킬 트리에서 콤보 효과를 위한 최적의 스킬 발동 순서는 무엇인지 고르시오.

문제 16. 아래는 게임에서 캐릭터 스킬 트리를 구현하기 위한 이진트리 코드의 일부이다. 이 코드는 게임에서 캐릭터의 스킬을 파워에 따라 이진트리로 정렬하여 저장한다. 빈칸에 들어갈 적절한 코드를 고르시오.

문제 17. 다음은 알고리즘의 성능 분석과 관련된 설명이다. 틀린 것을 고르시오.

문제 18. 게임 개발에서 그래프 알고리즘이 사용되는 이유에 대한 설명 중 틀린 것을 고르시오.

문제 19. 다음은 게임에서 물체의 이동을 구현하기 위한 C++ 벡터 연산 코드다. 빈칸에 들어갈 적절한 코드를 고르시오.

문제 20. 다음은 게임 개발에서 사용되는 디자인 패턴에 대한 설명이다. 이 설명이 가리키는 디자인 패턴으로 가장 적절한 것을 고르시오.

문제 21. 최근 국내 게임에서 블록체인 기술을 접목하여 대체불가능토큰(NFT, Non-Fungible Token)으로 게임 아이템 소유 인증을 받는 기술이 화제다. 블록체인에도 많이 쓰이는 해시 테이블(Hash Table)에 대한 설명 중 잘못된 것은?

문제 22. 다음 중 일반적인 알고리즘에 대한 설명으로 적합하지 않은 것은?

문제 23. 다음은 자료구조 중 데크(Deque)에 대한 설명으로 틀린 것을 고르시오.

문제 24. 스타크래프트와 같은 전략 시뮬레이션 게임을 작성하고자 한다. 어떤 유닛(unit)에게 명령어를 연속하여 입력하여 순서대로 예약하고자 한다면 어떤 자료구조를 사용하는 것이 가장 적당한가?

문제 25. 다음은 최단경로 알고리즘에 대한 설명의 일부분이다. 이 특징에 가장 가까운 알고리즘을 고르시오.

추천글

게임국가기술자격검정 게임프로그래밍전문가 [한국콘텐츠진흥원] | 종합

필기시험 관련 기초 개념 공부 | 게임국가기술자격검정 게임프로그래밍전문가 [한국콘텐츠진흥원]

티스토리툴바