기초 면접 공부

면접준비하면서 중요하다 싶은 것들 정리함.

 

-자료구조

Stack : LIFO구조. 오버플로우/언더플로우. 함수호출 순서제어. Postfix Notation 수식연산. 부프로그램호출시 복귀주

소 저장.

Queue : FIFO구조. Front/Rear포인터. 선형/환영큐 운영체제 작업스케쥴링

Hash table : 키값에 대한 해싱함수의 값을 인데스를 가지는 구조.

Priority queue/Heap : Binary tree구조. 삽입/삭제 O(log(n)), Find Min/Max O(1):상수시간. 그냥 Find O(n)

Array : 선형구조. 삽입/삭제 O(log(n)):선형시간, Find O(1)인덱스를 알고있다면, 모르면 O(n)

List : 선형구조. 포인터로 연결되어있음. 삽입/삭제 O(1), Find O(n)

BST(Binary Search Tree) : 왼쪽자식노드는 노드의 값보다 작은값, 오른쪽노드는 큰값. Find O(log(n)), 삽입 O(log

(n))

self-balancing BST

AVL Tree : 왼쪽 서브트리의 깊이를 hl, 오른쪽 서브트리의 깊이를 hr이라 할때, hl-hr의 값이 -1,0,1이되도록 변경.

공간복잡도 O(n). 삽입/삭제 O(log(n))

Red-Black Tree : 2-3-4 tree와 유사. 노드는 red/black이며 루트와 모든leaf는 블랙, red노드의 자식은 모두 black,

리프노드에 traversal할때 블랙노드의 수는 같음. 공간복잡도 O(n). 삽입/삭제 O(log(n))

*AVL Tree가 더욱 엄격함. RB tree가 더 효율적이다.

 

-알고리즘

Quick sort : 피벗을 정한후, 피벗앞/뒤를 나눈다.(partitioning) 분할된 서브리스트에 대해 재귀적 반복. O(nlog(n)),

최악 O(n^2)

Heap sort : 힙트리에서 하나씩 팝업.O(nlog(n))

Merge sort : 정렬되지 않은 리스트를 나눠 재귀적으로 병합하여 정렬 O(nlog(n)) 공간복잡도 O(n)

insertion sort : 정렬된 부분리스트에 원소를 삽입하는 방식 O(n^2)

Bubble sort : 인접한 두 원소를 비교해가면서 정렬하는 방식

DFS : Depth-first search. 노드검색 경로를 스택에 저장. 시간복잡도 O(버텍스개수 + 엣지개수), 공간복잡도 최악 O(

버텍스개수)

BFS : Breadth-first search. 이거는 큐. 시간복잡도 O(버텍스개수 + 엣지개수), 공간복잡도 최악 O(버텍스개수+엣지개

수)

Topological sort : 위상정렬. 순서가 있는 작업(ex. A->C, B->C라는 작업이있다면 C가 실행되기전에 A,B가 실행되어야

함.) DFS에서 스택에서 팝되는 순서를 거꾸로

(MST - Minimum spanning tree)

Prim's algo.: 현재노드에서 최소비용의 엣지선택. O(엣지숫자log버텍스숫자)

Kruskal's algo.: 엣지중에서 순환트리를 만들지않는 최소비용의 엣지선택.

(Shortest path)

Dijkstra's algo.: 노드와 연결되어 있는 엣지의 비용과 현재까지의 비용의 합이 최소인 엣지를 선택. O

(엣지+버텍스log버텍스)

A* : Heuristic함수 효율적으로 사용. 현재까지 비용과 목표노드까지의 추정비용(휴어리스틱함수)의 합을 Open set(힙

트리)에 넣고 팝업하면서 경로를 찾음. 목표지에 도착하면 부모노드를 찾아가는 경로. h(n)=0이면 다익스트라와 같음.

h(n)이 작거나 같아야 경로를 찾는다.

 

-C/C++

Class : 속성과 메소드를 가진 무언가를 추상적으로 정의한것

Object : 어떤 클래스의 특정 인스턴스

inheritance : 어떤 클래스에서 추가적인 행동을 제공하게 해줌

Polymorphism : 다형성. 한 행동을 여러방법으로 구현하고 상황에 따라 적당한 구현을 선택해서 쓸 수 있도록 기능 제

공. overloading/override

Override : 상속받은 부모클래스에서 정의한 메소드를 재정의함.

Overload : 서로 다른 매개변수를 가지는 동일한 이름을 가지는 함수를 중복정의함. (연산자오버로드)

Interface : (C++에서) 순수가상함수로 정의된 추상클래스  <-> 구현상속

is-a/has-a : is-a 관계는 public 상속관계/ has-a 관계는 어떤 클래스가 있어야 자신의 클래스가 정의되는 관계

virtual method : vptr테이블에 함수포인터가 저장. 4byte의 메모리. 자식클래스에서 오버라이드한 후, dynamic_cast를

하여 부모클래스의 메소드를 실행해도 자식클래스 메소드가 실행됨

다중상속 문제점 : A->B, A->C에서 B와C를 다중상속받는 D에서 오버라이드된 메소드라던지 중복된이름의 변수에 접근할

때 모호성을 가지게됨. 가상상속을 사용(class B:virtual A/ class C:virtual A/ class D: public B,public C). 그러나

크기와 속도비용이 늘어남.

static_cast : 암시적 변환

reinterpret_cast : c스타일의 강제형변환

const_cast : 객체의 상수성을 없앰.

dynamic_cast : 안전하게 다운캐스팅을 하게 해줌. 런타임비용이 높다.

upcasting : 자식클래스를 부모클래스처럼 사용 -안전

downcasting : 부모클래스를 자식클래스처럼 사용 -위험

헤더파일 중복을 막기 위한 방법 : #pragma once 또는 #ifndef XX #define XX ~~ #endif

 

- DB/네트워크

트랜잭션 : 한단위를 이루는 일련의 연관된 데이터베이스 조작. 트랜잭션의 모든 작업이 성공적으로 처리되지 않으면

트랜재션의 어떤작업도 처리되면 안됨(atomicity 원자성). 시작과 종료후 DB가 올바르고 일관된

상태여야됨(consistency 일관성). 트랜잭션이 커밋될때까지 어떤 질의나 트랜잭션과도 고립되어야됨(isolation

고립성). 커밋된 내용은 영구적이어야됨(durability 영속성).

roll back : 트랜잭션 실패시 DB를 원래대로 돌려놓는것.

commit : 트랜잭션 성공시 DB를 업데이트.

DB정규화 : 1NF 반복되거나 복수값을 가지는 속성을 제거. 모든 속성은 하나의 값만. 2NF 기본키에 완전히 종속되지 않

는 속성제거(부분적 함수종속 제거,  모든 속성은 기본키에 종속되어야됨). 3NF 키본키이외의 속성에 종속정인 속성제

거(이행적 함수종속제거, 기본키가 아닌 속성간에는 종속이 될 수 없음.)

TCP : 연결형. 신회성이 높으나 UDP에 비해 오버헤드. FTP에 사용. ACK로 서로 sync를 맞춤(flow control 흐름제어)

UDP : 비연결형. 속도는 빠르나 신뢰성이 없음. TFTP. 중요하지 않은 데이터전송시.

온라인게임에 적합한 프로토콜은 : 서버와 클라이언트가 주고받는 데이터 용량은 작으며 또한 자주 발생한다. 또한, 통

신중에 에러가 발생하더라도 크게 영향을 끼치지 않으므로(게임상 문제는 없으나 싱크문제는 발생할수있음) UDP가 더

적절. TCP는 주로 큰 용량을 안전하게 전송하기에 알맞기에 부적절하다.

 

- 그래픽스

BSP tree (binary space partitioning tree) : 공간을 이분할적으로 나눠 만드는 트리구조. 예전에는 컬링에 사용하였

으나, 지금은 주로 충돌체크에 사용

Octree/Quadtree : 화면을 분할하는 기술로 입방체(사각형)를 8개(4개)의 작은 입방체로 나눠 트리를 만드는 방식. 컬

링에 사용하였으나, 이것도 주로 충돌체크에 사용

AABB/OBB : 충돌체크를 위한 바운딩박싱. Aligned-Axis BB의 경우 매 프레임마다 객체를 포함하는 xyz축에 평행한 입방

체를 만들어 계산(충돌처리는 쉽지만 입방체를 계속 리빌드해야함, 정적물체에 용이). Objected BB 애니메이션되는 모

델에 적합. 연산이 살짝 어려움.

Shadow Volume : 물체를 빛의 방향으로 늘려 스텐실버퍼를 사용하여 그림자영역 검출. 때로는 그 영역이 바뀌기도 함(

카메라가 입체안에 있는 경우). 과도한 필레이트. 그림자가 날카로워 부자연스러움.

Shadow Mapping : 그림자가 드리워질 모델에 그림자 텍스쳐를 입혀서 렌더링. 앨리어싱이 발생함.

Normal Mapping : 노멀맵을 이용하여 탄젠트 공간으로 변환시켜 픽셀에 대해 조명값을 변경해주는 범프매핑.

Parallax Mapping : 노멀맵을 이용하여 탄젠트 공간으로 변환시켜 픽셀에 대해 텍스쳐 uv를 변경해주는 범프매핑.

Displacement Mapping : 실제 기하정보를 변경시키는 범프매핑.

셰이더의 역할 : Vertex shader 기존 렌더링 파이프라인에서 조명과 변환/ Pixel shader 기존 멀티텍스쳐 단계를 대신

함.(텍스쳐뿐 아니라 알고리즘에 따라 어떠한 결과도 나오게 함)

출처 : http://blog.naver.com/re4ever/10088171200

 

[출처] 게임 프로그래머 면접 단골문제라면 단골문제.|작성자 조금신