[게임프로그래밍전문가] 필기이론 간단정리 - 프로그래밍기반이론(1)

제3과목 프로그래밍 기반 이론

1. 자료구조

- 데이터 : 수치데이터, 문자데이터

* FIFO형태 - 큐, LIFO형태 - 스택

(1) 스택(Stack) : 후입선출리스트, LIFO, 먼저 삽입된 것이 나중에 삭제

․Top>=스택크기 : OVERFLOW 발생(삽입시)

․Top<=0 : underflow 발생(삭제시)

․사용예 : 서브루틴 처리, 인터럽트 처리, 산술문의 인픽스, 포스트픽스(후위표시법) 표현할 때

미로에서 길 찾기 알고리즘 ,함수 호출과 복귀 처리를 위한 복귀 주소 저장

(2) 큐 : 선입선출리스트, FIFO, 먼저 삽입되는 것이 먼저 삭제되고 나중에 삽입되는 것이 나중에 삭제

․front=0 : underflow 발생(삭제시)

․큐의 종류 : 일반큐, 환형큐

(3) 연결리스트(Linked List) : 일정한 순서로 데이터 항목표현

․구조: 하나의노드와 다음 항목데이터값으 포인트

․종류

- 단일연결리스트 : 데이터 값 다음 노드를 가리키는 포인터, 역방향으로 안됨

- 이중연결리스트 : 이전노드 가리키는 포인터 추가, 데이터 값 다음 노드를 가리키는 포인터

기억장소가 많이 차지

(4) 트리(Tree) : 데이터를 계층적으로 할 때 사용

․트리 구조를 적용할 때 - 가족족보, 산술식, 상하관계 <행렬은 안됨>

․이진트리 : 차수가 노드가 2개를 넘지 않는 트리

․이진트리설명 : 임의의 트리는 이진트리로 변할 수 있다, 이진트리를 이용하여 정렬할 수 있다

․Binary Tree 특징 : Oredred tree, Degree(차수) 2이하이다, null link 점유율이 약 1/2이다

․이진트리종류 : 사항트리(한방향), 정이진트리, 전이진트리

․이진트리 각 노드 방문하는 순서

+ 전위순회 : 자신-왼쪽-오른쪽(프리오더운행법)

+ 중위순회 : 왼쪽-자신-오른쪽(인오더운행법)

+ 후위순회 : 왼쪽-오른쪽-자신(포스트오더운행법)

․이진탐색트리

이진탐색트리검색 방법

키값을가지고 노드를 찾는방법

(5) 그래프

․방향성그래프, 무방향성그래프

․무향그래프 : 노드의 순서가 정해지지 않은 그래프

․유향그래프 : 노드들의 순서가 정해진 그래프를 말한다

․완전그래프 : 노드를 쌍으로 링크를 말한다

․그래픽 표현방법 - 인접행렬, 인접리스트

․그래프탐색

- 깊이우선탐색(Depth First Search) : 시작점에서 방문하지 않은 인접 노드를 탐색

- 너비우선탐색(Breath First Search) : 인접된 모든 정점을 방문하여 탐색

․해싱(Hashing) : 테이블에 특정명칭을 찾고자 할 때 키값을 찾는 것

*이중링크시 필요한 자료구조 Deque

2. 게임 알고리즘의 특징 및 개요

온라인게임 : Visual C++, 웹기반 모바일 게임 : 자바(Java)

(1) 게임알고리즘 개요

+ 그래픽게임 - DirectX, OpenGL 주로 사용

(2) 윈도우즈 프로그래밍

+ API : 윈도우의 응용 프로그램 인터패이스, SDK : API보다 상위레벨클래스

+ 윈도우즈AIP: 프로그램개발도구

(3) DirectX 프로그래밍

+ DirectX, OpenGL 프로그래밍 : 3차원그래픽을 처리하는 도구

① DirectX 개요

- SDK(도스용), GDK(게임전용) 이름으로 세상에 출시

- HAL(하드웨어와 직접통신, 하드웨어로 이어지는 층, 호출을 통해 장치드라이버와 직접통신)

- HEL(하드웨어가 지원을 안할 때 사용, 소프트웨어알고리즘, 프로그램중단, 처리속도느림)

② DirectX 주요함수

- DirectDraw 객체를 생성하기 위해 DirectDrawcreate()함수 사용

- 윈도우모드 설정시 SetCooperativeLavel()함수 사용

- 화면모드설정시 팔레트 폭, 높이 설정 SetDisplayMode()함수 사용

- 표면을 생성하기 위한 함수 CreateSurface()함수 사용

* 표면(surface)

DirectX 2D그래픽, 플리핑, 블리핑, 오프스크린 등을 지원

* 실제그림을화면에 출력하기위한 필요한부분 (기본표면)

보조표면 오프 스크린 나뉜다

기본표면과 보조표면 자료교환을 플리핑

오프스크린과 보조 표면의 자료교환을 블리팅

API 가상 키값은 VK_ 로 시작

윈도우를 생성하는 함수 CreatewindowEx, 메시지를 처리하는부분 : WndPorc

3. 정렬알고리즘

- 정렬 : 크기가 제각각으로 나열된 데이터를 크기의 순서대로 다시 나열한 작업

(1) 퀵정렬 : c.a.r. Hoare 의해 제안, 평균실행속도가 가장 우수

기준값은 피벗(pivot) 좌측 첫번째 값 전송

피벗을 중심으로 큰 값은 오른쪽, 작은 값은 왼쪽으로 정렬, 순환프로그램 스택 필요

전체 리스트를 2개의 부분 리스트로 나누고, 정복법사용, 연산시간 : O(nlog2n)

(2) 삽입정렬 : 정렬된 레코드에 새로운 레코드를 적절한 위치에 삽입하는 방법

왼쪽은 이미 정렬되어 있고 오른쪽 리스트 첫번째와 왼쪽의 정렬된 리스트의 어느 위치에 삽입되는지 판단

대부분데이터가 이미 정렬되어 있을 때 많이 사용

데이터수가 적으면 알고리즘 자체가 간단

데이터 양이 많고 레코드가 클 경우 적합하지 않음

(3) 선택알고리즘

- 가장 작은 값을 선택하고 나열반복

- 가장 키값이 작은 것을 찾아 첫번째 위치에 있는 레코드와 교환

- 첫번째 값을 제외하고 가장 작은 값을 2번째 레코드와 교환

(4) 버블정렬

- 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어있지 않으면 서로교환

- 비교-교환 과정을 정렬이 안된 리스트의 왼쪽에서 시작하여 오른쪽 끝까지 진행되며 가장 큰값을 오른쪽으로 이동

(5) 셀정렬 : Donald L.Shell 사람이 제안

정렬해야할 리스트를 중분에 따라 연속적이지 않은 여러 개의 리스트로 분할

삽입정렬 이용, 더 작은 수의 부분리스트가 1이 될 때까지 반복

(6) 히프정렬

- 최소 히프를 사용하여 가장 작은 원소를 차례대로 추출하여 정렬

- 부모노드가 자식노드보다 작은 값을 구성하는 정렬, 자료의 수만큼 기억장소 스택 필요

(7) 합병정렬

- 분할-정복법을 이용, 두개의 이미 정렬된 리스트를 합쳐서 하나의 정렬된 리스트로 합병

- 메모리가 많이 요구, 연결리스트구성

(8) 외부정렬

① 자연합병

- 2개런에 대하여 합병이 이루어지기 때문에 2원 합병이라고 지칭, 두 파일의 런을 서로 합병

② 균형 2-원 병합

- 출력을 미리 다음 단계의 입력 파일로 재분배

③ 다단계합병

- 균형합병에 파일유휴상태 단점개선

- 출력을 미리, 불균형 병합방식, 초기 입력파일 런이 복잡

- 최저 3개 파일 가지고 있다

- 정렬을 대상이 주 메모리보다 클 경우에는 외부 정렬을 사용한다

- 퀵정렬은 Divide and Conquer 방식에 의한 소트이다

- 힙정렬은 초기 힙의 구성이 필수