게임 클라이언트 프로그래머 직군 면접 준비 (5)

게임 클라이언트 프로그래머 직군 면접 준비 (5)

 

자료구조 (Data Structure)

자료 구조란 데이터의 편리한 접근과 조작을 가능하게 하는 데이터를 저장하거나 조직하는 방법입니다.

자료구조의 다양한 종류와 각각의 장점과 한계를 잘 이해하고 상황에 맞게 올바른 자료 구조를 선택하고 사용하는 것이 중요합니다.

 

[자료구조의 분류]

•선형 구조 : 배열, 선형 리스트, 스택, 큐, 데크

•비선형 구조 : 트리, 그래프

 

[배열(Array)]

가장 기본적인 자료구조인 Array 자료구조는, 논리적 저장 순서와 물리적 저장 순서가 일치한다. 따라서 인덱스(index)로 해당 원소(element)에 접근할 수 있다. 그렇기 때문에 찾고자 하는 원소의 인덱스 값을 알고 있으면 Big-O(1)에 해당 원소로 접근할 수 있다. 즉 random access 가 가능하다는 장점이 있는 것이다.

 

[연결 리스트(Linked List)]

각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있다. 따라서 이 부분만 다른 값으로 바꿔주면 삭제와 삽입이 간단합니다. 하지만, 원하는 위치에 삽입을 하고자 하면 원하는 위치를 Search 과정에 있어서 첫번째 원소부터 다 확인해봐야 한다는 단점이 있습니다.

 

[스택(Stack)]

•리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료 구조이다.

•가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO) 방식으로 자료를 처리한다.

 

[큐(Queue)]

•리스트의 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지는 자료 구조이다.

•가장 먼저 삽입된 자료가 가장 먼저 삭제되는 선입선출(FIFO) 방식으로 처리한다.

 

[데크(Deque)]

•삽입과 삭제가 리스트의 양쪽 끝에서 모두 발생할 수 있는 자료 구조이다.

•입력 제한 : 입력은 한쪽에서만 일어나고 출력은 양쪽에서 일어남

•출력 제한 : 입력은 양쪽에서 일어나고 출력은 한쪽에서만 일어남

 

[트리(Tree)]

트리는 계층적 관계(Hierarchical Relationship)을 표현하는 비선형 자료구조입니다.

요소를 의미하는 노드와 노드를 연결하는 간선으로 이루어져 있습니다.

노드가 최대 2개인 트리를 이진 트리(Binary Tree)라고 합니다.

모든 레벨이 꽉 찬 트리를 포화 이진 트리(Full Binary Tree)라 하고

위에서 아래로, 왼쪽에서 오른쪽 순서대로 차곡차곡 채워진 트리를 완전 이진 트리(Complete Binary Tree)라고 한다.

 

[이진탐색트리(Binary Search Tree)]

데이터 삽입. 삭제, 탐색 등이 자주 발생하는 경우에 효율적인 구조로, 이진 트리 이면서 같은 값을 갖는 노드가 없어야합니다. 왼쪽 서브 트리에 있는 모든 데이터는 현재 노드의 값보다 작고, 오른쪽 서브 트리에 있는 모든 노드의 데이터는 현재 노드의 값보다 크다는 특징이 있습니다. 즉, 정렬이 되어있어야 합니다.

 

[레드-블랙 트리(Red-black tree)]

자가 균형 이진 탐색 트리(self-balancing binary search tree)로써, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조입니다. 레드 노드와 블랙 노드가 인접하지 않은 특징을 가지고 있으며, 복잡하지만 최악의 경우에도 효율적인 특징이 있습니다.

 

[그래프(Graph)]

객체 사이의 연결 관계를 표현할 수 있는 자료구조로 정점과 간선으로 이루어진 자료구조입니다.

간선이 방향성을 가지면 방향성 그래프(Directed Graph)

간선에 방향성이 없으면 무방향성 그래프(Undirected Graph)

 

[해시 테이블(Hash Table)]

해시 테이블은 <key, value>로 데이터를 저장하는 자료구조 중 하나로, 빠른 데이터 검색이 필요할 때 유용합니다. key값에 대해서 해시 함수를 계산하여 주소를 구하고, 구한 주소에 해당하는 위치로 바로 이동하여 값을 꺼내오는 구조입니다.

 

[해싱 함수 (Hashing Function)]

•제산법(Division)

•제곱법(Mid-Square)

•폴딩법(Folding)

•기수 변환법(Radix)

•대수적 코딩법(Algebraic Coding)

•숫자 분석법(Digit Analysis, 계수 분석법)

•무작위법(Random)

 

알고리즘(Algorithm)

 

기수 정렬 -> 퀵 정렬 -> 병합 정렬 = 힙 정렬 -> 셀 정렬 -> 삽입 정렬 -> 선택 정렬 -> 버블 정렬

[삽입 정렬 (insertion sort)]

삽입 정렬은 두번째 위치부터 시작하여, 그 앞의 이미 정렬된 원소들과 비교하여 삽입할 위치를 찾아 삽입하는 알고리즘입니다. 평균 시간복잡도는 O(n2)이며, 가장 빠른 경우 O(n)까지 빨라질 수 있습니다.

 

[선택 정렬 (selection sort)]

선택 정렬은 각 순서에 원소를 넣을 위치는 이미 정해져 있고, 해당 위치에 어떤 원소를 넣을지 선택하는 알고리즘입니다. 오름차순으로 정렬한다면 첫 번째 순서에는 첫 번째 위치에 가장 최솟값을 선택하여 넣고, 두 번째 순서에는 두 번째 위치에 남은 값 중 최솟값을 선택하여 넣는 과정을 마지막까지 반복합니다. 구현이 간단하지만 O(n2)의 시간복잡도를 갖는 비효율적인 정렬 방식입니다.

 

[버블 정렬 (bubble sort)]

버블 정렬은 인접한 두 원소를 비교하여 자리를 교환해가며 정렬하는 알고리즘입니다.

오름차순으로 정렬한다면 첫번째 순서에는 처음부터 마지막 원소까지 비교하여 결과적으로 마지막 위치에 가장 큰 값이 위치하게 되고, 두 번째 순서에는 마지막 원소를 제외하고 같은 과정을 반복하며 정렬하는 방식입니다. 구현이 간단하지만 O(n2)의 시간복잡도를 갖는 비효율적인 정렬 방식입니다.

 

[퀵 정렬 (quick sort)]

퀵 정렬은 pivot을 설정하여 원소들을 pivot보다 큰 값과 작은 값으로 분할하여 정렬하는 분할 정복 알고리즘입니다. 시간 복잡도는 O(nlogn)이지만, 계속해서 불균등하게 나누어지는 경우에는 O(n2)까지 나빠질 수 있습니다.

 

[병합 정렬 (merge sort)]

병합 정렬은 주어진 배열을 크기가 1인 배열로 분할한 뒤 이들을 병합하면서 정렬을 진행하는 분할 정복 알고리즘입니다. 시간 복잡도는 항상 O(nlogn)입니다.

 

[셸 정렬 (shell sort)]

셸 정렬은 삽입 정렬이 어느 정도 정렬된 배열에 대해서 매우 빠르다는 점에서 착안하여 삽입 정렬을 보완한 알고리즘입니다.

일정한 간격으로 떨어져 있는 원소들끼리 부분집합을 구성하여, 각 부분집합 내에서 삽입 정렬을 수행한 뒤 모든 부분집합을 다시 합치는 과정을 반복하며 정렬합니다. 시간 복잡도는 평균적으로 O(n1.5)이며, 최악의 경우에는 O(n2)입니다.

 

[힙 정렬 (heap sort)]

힙 정렬은 주어진 데이터를 힙으로 만들어 최댓값 또는 최솟값부터 하나씩 꺼내며 정렬하는 알고리즘입니다. 전체를 정렬할 때보다는 가장 크거나 작은 값 몇 개를 필요로 할 때 가장 유용합니다. 시간 복잡도는 O(nlogn)입니다.

 

[트리 정렬 (tree sort)]

트리 정렬은 이진 탐색 트리(BST)를 이용하여 데이터를 정렬하는 방식입니다. 원소들을 순서대로 이진 탐색 트리에 넣은 뒤, 중위 순회로 값을 모두 꺼내면 데이터가 오름차순으로 정렬됩니다. 시간 복잡도는 O(nlogn)입니다.

 

[브루트 포스 알고리즘(Brute Force)]

무식하게 탐색하는 순차 탐색, 백트래킹, DFS, BFS 알고리즘 등

[DFS 깊이 우선 탐색 (Depth Fisrt Search)]

미로 찾기처럼 그래프의 정점을 타고 깊이 들어가다가 더 이상 방문해왔던 정점 말고는 다른 이웃을 갖고 있지 않은 정점을 만나면 뒤로 돌아와 다른 경로로 뻗어있는 정점을 타고 방문을 재개하는 방식으로 동작합니다.

 

[BFS 너비 우선 탐색(Breadth First Search)]

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 알고리즘이다.

 

[다이나믹 프로그래밍(Dynamic Programming)]

동적 프로그래밍이란 주어진 문제를 풀기 위해서 문제를 여러 개의 하위 문제로 나누어 푼 뒤 그것을 결합하여 해결하는 방식입니다. 동적 프로그래밍에서는 어떤 부분 문제가 다른 문제들을 해결하는 데 사용될 수 있기 때문에, 답을 한 번만 계산하고 그 결과를 재사용하는 memoization 기법으로 속도를 향상할 수 있습니다.

분할 정복 vs 동적 프로그래밍

분할 정복 기법은 단순히 큰 문제를 작은 문제로 나누어 푸는 방법이고, 동적 프로그래밍은 작은 문제의 해가 중복해서 재사용된다는 점을 이용해서 푸는 방법입니다.

 

[그리디 알고리즘(탐욕법, Greedy Algorithm)]

- 최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론으로 ‘각 단계에서 최적이라고 생각되는 것을 선택’ 해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘입니다.

- 이때, 항상 최적의 값을 보장하는 것이 아니라 최적의 값의 ‘근사한 값’을 목표로 하고 있습니다.

 

[최단 경로 - 다익스트라 알고리즘]

다익스트라 알고리즘은 하나의 시작점에서 다른 정점까지의 최단 경로를 구하는 알고리즘입니다.

최단거리를 여러개의 최단거리로 이루어져 있기 때문에 DP를 적용하여, 하나의 최단 거리를 구할 때 이전까지 구했던 최단 거리 정보들을 재사용하게 됩니다.

매 과정에서 아직 방문하지 않은 정점들 중 최단 거리가 가장 짧은 정점을 방문하게 되는데, 이때 우선순위 큐를 활용하면 더욱 효율적으로 처리할 수 있습니다.

 

[최단 경로 - 플로이드 와샬 알고리즘]

플로이드 와샬 알고리즘은 특정 시작점 없이 모든 정점에서 다른 모든 정점으로 가는 최단 거리를 구하는 알고리즘입니다. 두 정점 사이의 어떤 경유점이 존재할 때, 경유점을 거쳐가는 경우의 거리를 계산하여 기존까지 계산한 최단 거리와 비교하며 더 짧은 거리를 선택하는 방식입니다.

 

[최단 경로 - 벨만 포드 알고리즘]

한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘입니다. 다익스트라 알고리즘과 달리 간선의 가중치가 음수인 경우에도 최단 거리를 구할 수 있습니다. 단, 음의 사이클이 없는 그래프에서만 가능합니다.

 

[최소비용 신장트리(MST: Minimum Spanning Tree)]

신장 트리는 N개의 정점으로 이루어진 무방향 그래프에서, N개의 모든 정점과 N-1개의 간선으로 만들어진 트리입니다. 최소비용 신장 트리는 신장 트리를 구성하는 간선들의 가중치의 합이 최소가 되는 신장 트리를 의미합니다. 최소비용 신장 트리를 만드는 알고리즘은 대표적으로 크루스칼 알고리즘과 프림 알고리즘이 있습니다.

 

[크루스칼 알고리즘]

크루스칼 알고리즘은 매 차례마다 가중치가 낮은 간선을 삽입하거나 가중치가 높은 간선을 삭제하는 방식으로 MST를 만드는 알고리즘입니다. 간선을 오름차순 또는 내림차순으로 정렬하여 선택하는데, 사이클이 생성되지 않게 하기 위해 매번 사이클 생성 여부를 판단해야 합니다.

 

[프림 알고리즘]

프림 알고리즘은 하나의 시작 정점을 기준으로 트리를 점점 확장해가는 알고리즘입니다. 선택된 정점들과 선택되지 않은 정점들을 연결하는 간선들 중 가중치가 최소인 간선으로 연결된 정점을 새로 선택하며, 모든 정점이 선택될 때까지 반복합니다.

프림 알고리즘은 이미 선택된 정점을 다시 선택하지 않기 때문에, 사이클 생성 여부를 판단하지 않아도 됩니다.

 

* 크루스칼 알고리즘은 가중치를 기준으로 간선을 정렬해야 하기 때문에 간선의 개수가 많지 않은 경우에 적합하며, 간선의 개수가 많을 때는 프림 알고리즘을 사용하는 것이 적합합니다.