실무 면접 대비 2번째 알고리즘, STL, 자료구조 (게임 클라이언트 프로그래머 기준)

0. STL이란 뭔가요?

Standard Template Library로 C++의 템플릿을 사용하여 표준으로 정리된 라이브러리입니다.

반복자/컨테이너/알고리즘/함수 객체등의 라이브러리로 구성됩니다.

 

1. 시퀀스 컨테이너, 연관 컨테이너, 어뎁터 컨테이너에 대해서 설명해주세요.

(자료의 구조로 구분을 하면…)

시퀀스 컨테이너는 자료를 입력한 순서대로 저장하기 때문에 저장 검색 알고리즘이라고 불립니다. 많지 않은 양의 자료/검색속도가 중요하지 않은 경우에 사용되며 vector, list, string, dequue등이 이에 해당합니다.

연관 컨테이너는 일정한 규칙에 따라 자료를 조직화하여 저장하는 것을 말합니다. 자료를 정렬하여 저장하기 때문에 검색에 유리하고 많은 양의 자료/빠른 검색이 중요할 때 사용합니다. 대표적으로 map, set이 그에 해당합니다.

어뎁터 컨테이너는 시퀀스 컨테이너를 변형시켜 스택, 큐, 우선순위 큐 형태로 저장하는 것을 말합니다.

(메모리 상에서 자료를 구성하는 형태로 구분을 하면)

contuquius-Memory연속메모리: 동적할당된 하나의 메모리 단위에 데이터 요소를 저장 

node-based노드기반: 동적할당된 하나의 메모리 단위에 하나의 요소만 저장합니다. 포인터로 이를 연경합니다. 자료 추가 삭제에 유리하며 순차적 접근만 가능해 랜덤 접근이 불가능 합니다.

 

2. 컨테이너가 뭔데요?

같은 타입의 여러 객체를 저장하는 일종의 집합이라고 할 수 있습니다. 컨테이너는 클래스 템플릿으로 컨테이너 변변수 선언할 때 컨테이너에 포함할 요소의 타입을 명시할 수 있습니다.

 

3. 이터레이터란?

반복자는 컨테이너에 저장된 원소를 순회하고 접근하는 일반화된 방법을 제공합니다. 반복자는 컨테이너와 알고리즘이 하나로 동작하게 묶어주는 인터페이스 역할을 합니다. 이 반복자 덕에 알고리즘은 특정 컨테이너에 종속적이지 않고 독립적이면서도 언제든지 컨테이너와 결합하여 동작 할 수 있습니다.

 

4. array, vector, list, forward_list, queue, deque, stack, map, set에 대해서 설명하시오.

	array (불가변배열)	vector (가변배열)	list
장점	- 적은 양의 자료에 유리	- 적은 양의 자료에 유리 - 크기 변경 가능 - 순차 접근 가능 - 랜덤 엑세스 가능	- 중간 삽입/삭제 가능 - 크기 변경 가능 - 적은 양의 자료에 유리 - 순차 접근 가능
단점	- 크기 변경 불가	- 중간 삽입 삭제 불가능 - 검색 느림 - 많은 양의 자료 불리	- 많은 양의 자료에 불리 - 랜덤 엑세스 불가능 - 검색 느림
특징		- reserve제대로 안하고 실시간 puch_back하면 안된다. - clear가 제대로된 clear가 아님 - 범위외 참조하지 말 것	- 기능적으로 list가 성능적으로 forward_list가 가볍고 좋음

 

	map	set
장점	- 많은 양의 자료에 유리 - 검색 속도가 빠름	- 많은 양의 자료에 유리 - 검색 속도가 빠름
단점	- 적은 양엔 오버헤드로 인해 손해	- 적은 양엔 오버헤드로 인해 손해
특징	- 이진탐색트리기반(레드블랙트리) - 자동정렬 - key와 value로 pair형태 - 값을 넣을 때 최대한 insert 사용	- 이진탐색트리기반 - 자동정렬 - key가 곧 value

 

- 랜던엑세스의 같은 말: 임의 접근, 랜덤 접근, 비순차적 접근, 직접 접근

5. Binary Search Tree에 대해 설명하세요.

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

 

6. 선형구조와 비선형구조로 나눠주세요

선형 구조: 리스트, 스택, 큐, 데큐,

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

 

7. 트리와 그래프의 차이점은 무엇인가요?

트리: 트리는 그래프의 특별한 케이스이며 ‘최소 연결 트리’라고 불립니다. 두개의 정점 사이에 반드시 1개의 경로만 가지며 loop나 circuit self-loop도 없습니다. 한 개의 루트 노드만이 존재하며 모든 자식 노드는 한 개의 부모노드만 가집니다. 트리는 DAG(Directed Acyclic Graphs)의 한 종류로 DAG는 사이클이 없는 방향 그래프를 말합니다.

트리는 이진트리, 이진 탐색 트리 AVL트리, 힙등이 있습니다.

간선은 항상 정점의 개수 – 1 만큼을 가집니다.

트리는 계층 모델입니다.

그래프는: 2 개이상의 경로가 가능하며 노드 사이에 무방향/양방향 경로를 가질 수 있습니다. self/loop/circuit모두가능하며 루트노드라는 개념이 없습니다. 그래프의 순회는 DFS. BFS로 이루어지며 그래프는 네트워크 모델입니다. 부모와 자식관계하는 계념이 없습니다.

 

8. 정렬

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

 

9. map은 레드블랙트리로 만들어져 있는데 레드블랙트리란?

레드-블랙 트리(Red-black tree)는 자가 균형 이진 탐색 트리(self-balancing binary search tree)로써, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조다. 1978년 레오 귀바스(Leo J. Guibas)와 로버트 세지윅이 1972년 루돌프 바이어가 창안한 "대칭형 이진 B-트리"를 발전시켜 만들었다. 레드-블랙 트리는 복잡한 자료구조지만, 실 사용에서 효율적이고, 최악의 경우에도 상당히 우수한 실행 시간을 보인다: 트리에 n개의 원소가 있을 때 O(log n)의 시간복잡도로 삽입, 삭제, 검색을 할 수 있다. (출저: 위키백과)