검색알고리즘

검색이란?

특정한 구조로 구성되어 있는 자료의 집합에서 주어진 키에 해당하는 레코드를 찾아내는 것

단순히 자료를 찾는 것에만 국한되는 것이 아니라 자료가 새로 추가되고 삭제될 때 어떻게 이 자료들의 특정한 구조를 계속 유지하느냐하는 문제도 포함되어있다.

순차검색(선형검색)

주어진 자료 파일에서 처음부터 검색키에 해당하는 레코드를 순차적으로 비교하여 찾는 가장 단순한 검색 방법

장점 : 데이터를 따로 조작할 필요가 없어 단순

단점 : 리스트의 길이가 길면 비효율

시간의 복잡도 : O(n)

1. 별다르게 조직화가 필요없다.

2. N개의 자료에 대해서 평균적으로 N/2번의 비교를 해야한다.

검색

[검색 방법]

① 첫 번째 원소부터 시작하여 마지막 원소까지 순서대로 키 값이 일치하는 원소가 있는지를 비교하여 찾는다.

② 키 값이 일치하는 원소를 찾으면 그 원소가 몇 번째 원소인지를 반환한다.

③ 마지막 원소까지 비교하여 키 값이 일치하는 원소가 없으면 찾은 원소가 없는 것이므로 검색 실패

개선 :검색한 키를 선두로 옮기는 과정

삭제

[삭제 방법]

① 삭제하려는 키가 어디에 있는지 탐색한다.

② 찾으려는 키가 나올때 까지 한칸씩 당기고 배열의 자료수를 하나 감소 시킨다

삽입

[삽입 방법]

① 배열의 인덱스를 하나 증가하고 배열의 제일 뒤에 key를 덧 붙인다.

② 그런 뒤 삽입위치를 리턴

문제

문자열을 받으면 몇 종류의 문자(char)가 있는지 체크하는 문제이다.

풀이 : 내가 작성한 코드

첫 번째 요소를 리스트에 넣고 두 번째 요소부터 리스트자료 집합에 있는 문자인지

체크하도록 했다. 함수와, 리스트를 새로 만들었고 문자를 계속 비교하는 과정이 효율적이지 않은 것 같다.

풀이 : 다른 사람 풀이

int 배열을 생성하고 두번 째 for문에서 비교가 끝난 문자에는 '1'을 넣어

중복 비교를 하지 않게 만들면서 중복요소를 체크한다.

문제

문자열 중 요소중 가장 인덱스가 가장 빠른 숫자를 리턴해야 하는 문제

풀이 : 내가 작성한 코드

내가 작성한 코드는 int.TryParse 숫자로 변환이 가능하면 true를 리턴하는 함수를 사용하여

숫자를 구분했다. ToString( )도 사용하고 사용하지 않는 int result로 선언하기도 해서 

그닥 좋아보이지 않다.

풀이 : 높은 순위에 있는 코드

char.IsDigit 10진수인지 판별하는 함수를 사용하여 숫자를 찾고있다.

몰랐던 함수였다.

퀵정렬

빠른속도와 간단 원리

연속적인 분할에 의해서 정렬한다.

축값을 중심으로 왼쪽은 이 축값보다 작은 값으로 오른쪽은 모두 이 축값보다 큰 값으로 배열시키는 것이다.

이 과정을 분할의 크기가 1이 될 때까지 반복하면 전체적으로는 정렬이 완료된다.

퀵 정렬의 전략

<퀵 정렬 알고리즘 (a, N)>

1.만약 n > 1이면

1.1 N의 크기의 a 배열을 분할하여 축값의 위치를 mid로 넘긴다.

1.2 퀵 정렬 알고리즘(a,mid)

1.3 퀵 정렬 알고리즘(a+mid+1,N-mid-1)

왼쪽구간 부터 우선적으로 분할을 하고, 그 다음에 오른쪽 부분에 대해서 분할을 시작한다.

쉘 정렬 처럼 멀리 떨어져 있는 요소끼리 교환을 하기 때문에 빨리 정렬된 상태로 변화된다.

난수나, 반쯤 정렬된 배열에 대해서는 빠른 속도를 보이지만 이미 정렬된 배열이나 역순 배열에 대해서는 성능이 매우 떨어진다.
(빠른 알고리즘이란 최대한 적은 비교와 교환이다. 퀵정렬은 피벗에 모두 순차적으로 비교하게 되므로)

퀵소트 비재귀 버전

쉘정렬

삽입정렬은  정렬된 배열에 대해서는 매우 뛰어난 성능을 보이지만 그렇지 않은 경우에는 속도가 매우 느리다

ex) 역순 배열의 경우 제일 작은 키값이 제일 뒤에 있으므로 N번의 비교와 이동을 해야한다.

이 문제를 해결하기 위해 h만큼의 간격으로 떨어진 레코드를 삽입하는 정렬

4중 루프가 된 것을 제외하고는 삽입 정렬과 비슷하다.

쉘 정렬의 개선

h = (h-1)/3은 풀어쓰면 h = h/3 -1/3이 되며 1/3으로 취급하기 때문에 h = h/3

<결과>

쉘정렬은 O(NlogN)을 가지는 알고리즘들에 비해서는 속도면에서는 약간 떨어지지만 10,00이하의 자료 정도라면 쉘 정렬이 오히려 더 빠를 수가 있다.

O(NlogN)을 가지는 다른 알고리즘처럼 추가적인 메모리가 필요 하지 않는다.

학습참고 : C로배우는 알고리즘

삽입정렬

많은 비교와 적은 교환으로 특징인 선택 정렬과 반대로 적은 비교와 많은 교환이 이루어지는게 특징이다.

삽입 정렬의 전략

이미 정렬이 된 부분에 새로운 키를 적절한 장소에 삽입하는 동작을 반복적으로 하는 정렬 방법이다.

[루프안에 a[i]보다 t를 쓰는것이 더 빠르다(단순히 t의 값만 읽어 오기 때문)]

삽입정렬은 안정성이 있는데, 항상 그런것은 아니다. (>=t 경우)

이미 정렬된 배열일 경우 매우 빠른 속도를 가진다.

이미 정렬된 경우에는 삽입 정렬의 실행 시간은 N에 비례하는 선형적인 특성을 가진다.

둘째로 삽입 정렬은 역순의 경우 최악의 경우가 된다. 이동과 비교의 횟수는 N*(N-1)/2가 되어서 선택 정렬보다 속도가 떨어진다.

삽입 정렬의 최적화

a[0]값에 -1을 집어넣고 실제 값들은 이후의 저장하도록 하자

그러면 while문에 루프의 판단문에서 j>0과 같은 비교문을 하나 없앨 수 있다.

이런 방법을 사용하게 되면 정렬의 실행시간이 약간 단축되고 N이 클 경우 더 단축

(키값의 최소값을 정하지 못하는 경우가 있기 때문에 신중히 사용해야한다.)

간접정렬

교환이 많은 삽입정렬이기에 간접정렬이 고려된다.

레코드의 배열은 전혀 손대지 않고 따로 만든 인덱스의 배열을 조작하는 방법

비교는 실제 배열a이 하지만 while루프 내의 교환 작업은 index배열을 사용한다.

a에는 아무 변화가 없지만 index배열에는 정렬된 순서가 저장되어 있다.

제일 첫 번째 레코드가 무엇인지 알려면 a[index[0]]와 같이 접근 하면 알 수 있다.

실제로 a 배열을 정렬 하려면 아래와 같은 함수가 필요할 것이다.

학습참고 : C로배우는 알고리즘

정렬알고리즘

정렬이란 임의의 순서대로 배열되어 있는 자료의 집합을 일정한 순서대로 재배열하는 것을 의미

정렬의 방법론

= > 판단과 교환을 어떻게 적절히 조합하는가에 대한 방법론.

정렬을 하는 대상을 파일이라고 하며, 이 파일은 정보의 단위인 레코드의 나열이다.

아래 정보를 가지고 있는 인사기록 카드를 정렬하려고 했을 경우 카드 각 한장은 레코드, 레코드의 정보를 가지고 있는 사번, 성별,나이 등은 필드라고 한다.

정렬을 하려면 키가 있어야한다. ‘비교’의 대상이 되는 것은 레코드 중에서 키값이며, ‘교환’의 대상이 되는 것은 레코드 자체가 된다. 사원번호 정도가 ‘키’가 될 수 있겠다.

선택 정렬(Selection Sort)

순서대로 정렬하는 가장 간단한 정렬 알고리즘.

선택 정렬 알고리즘

선택정렬 특징:

첫 번째  배열의 앞 부분부터 정렬을 차례로 해나간다.

두 번째 정렬을 아직 하지 않은 부분은 n의 변함이 없다.

선택 정렬의 비교 횟수는 최소값을 찾기 위해서 N2/ 2 정도로 많지만 교환 횟수는 많아야 N번이다.

안정성 문제

안정성이란 같은 키의 상대적 순서가 정렬 후에도 변함이 없음을 뜻한다.

하지만 선택 정렬은 안정성이 없다.

인접한 배열 요소를 교환하는 것이 아닌 뚝 떨어진 요소와도 교환이 되기 때문이다.

문제

a 배열의 요소를 X로 생각하고 모든 요소들에 차를 절대값으로 만든 뒤 그 뺀 값을 더한 값중

가장 작은 값을 가지는 배열의 요소를 출력하는 문제이다.

(값이 같다면 가장 배열의 요소중 가장 작은 값을 출력) 

풀이 : 내가 작성한 코드

코드만 봐도 대충 어떤 문제인지 알 수 있다. 

각 모든 요소를 비교해서 'sum'이 가장 작은 배열의 요소를 출력한다.

코드 시그널은 문제를 해결하면 다른 사람들이 푼 답을 볼 수가 있는데 

밑에는 가장 작은 글자수로 문제를 해결 한 사람의 풀이다...

풀이 : 다른 사람이 작성한 코드

이게 어떻게 가능하지 생가했는데 정확히 원하는 값을 가지는 제일 작은 요소를 출력한다.

포문2개나 쓴 내 코드는....;;

같은 문제를 가지고 이렇게도 생각을 할 수 있구나 라고 생각이 들었다.

문제

가리키는 셀의 색상이 같으면 true를 리턴해주는 문제이다.

a1,a3,a5,a7 ...
b2,b4,b6,b8 ...
c1,c3,c5,c7 ...

위 셀들은 같은 색상(진한색)이다.

풀이

a1,a3,a5,a7 ...
b2,b4,b6,b8 ...
c1,c3,c5,c7 ...

(진한색)

a2,a4,a6,a8 ...
b1,b3,b5,b7 ...
c2,c4,c6,c8 ...

(옅은색)

보면 문자의 알파벳 다음인 숫자는 일정한 규칙으로 증가한다.

고로 색상이 같다는 것은 비교하려는 2개의 문자가 10진수로 변환하여 짝수인지

체크해주면 된다.

문제

true 조건

1. 알파벳 a~z(A~Z)과 특수문자 '_', 숫자가 포함되어야한다.

2. 문자열 처음은 숫자가 오면 안된다.

풀이

if((int.TryParse(name[0].Tostring( ), out int a))) : 문자열 첫번째 문자가 int형인지 아닌지 체크한다 2번조건

for, if문 : 모든 문자를 비교하여 true 조건 체크

테스트

04.01

문제

true조건 (IPv4address 약식 조건?)

1. '.'을 기준으로  4개 위치를 가지고 있어야함.

2. 각 위치 값이 0보다 크고 255보다 작아야함

3. 각 값들은 양의 정수이어야함.

풀이

String.Split('.') : '.'기준으로 나눈 값들을 배열의 요소로 담는다.

if(split.Lengt !=4) : true 2번 조건

int.tryParse(val, out int b)  : b를 int로 파싱하고(true를 반환) / 

불가능한 문자열이면 false를 반환한다. 

0 > b || b>255 : int로 파싱한 (int)b를 가지고 조건 범위에 벗어나지 않는지 체크한다. 

결과체크

true 2번 조건 255초과

true 3번조건 a는 int로 파싱불가

04.01

문제

풀이

//셋팅

int length : 각 배열하나당 글자수

int count : 배열의 갯수(문자열이 몇개인지)

string[] 배열을 생성 후 

//첫 째줄과 마지막 줄에 '*' 을 찍기 위한 과정

b[0] = new string('*', length); : 첫 번째 배열

b[count-1] = new string('*', length); : 마지막 배열

///b배열에 넣는 과정

for(int i=1; i< count-1; i++)

{ b[i] ="*" + b[i] + picture[i-1] + "*"; }

          * + 인풋문자열 + *

마지막 for문은 콘솔창에서 확인해보려고 넣음 (결과 의미없음)

test

03.31_CodeSignal

문제

풀이

<스택에 쌓인 문자>

문제

풀이

-1을 제외한 값을 내림차순으로 정렬

 a[i] 와 a[j]를 비교하여 비교 대상보다 자신의 값이 크면 뒤쪽으로 이동시켜준다.

03.28

문제

풀이

int 숫자를 리스트로 한 개씩 담는다.

ex) n = 1230

1230 % 10 = 0 //리스트add

1230 / 10 = 123; 

123 % 10 = 3 // 리스트add

123 / 10 = 12

12 % 10 = 2 // 리스트 add

12 / 10 = 1 

1 % 10 = 1 //리스트 add

03.27

문제

풀이:

diff값을 -1로 초기화 해준다.

배열안에 있는 모든 값들이 서로 비교

else if : 두 값차이가 d보다 작고, 두 값차가 -1보다 크면 diff 값을 두 값차인 값으로 변경해준다.

2번째 부터는 diff보다 크면 변경 (앞의 조건 만족 후 현재 diff보다 두 값의 차이가 크다는 것은 d 값과 비교하는 두 값의 차이가 작다는 의미)

03.26

Linked List 링크드 리스트(연결리스트)

연결리스트는 노드와 링크로 구성이 된다. 

노드 : 실제의 정보를 담고 있는 하나의 단위

링크 : 인접 노드의 위치를 저장하고 있어 연결 리스트의 순서를 유지할 수 있게 하는 연결 고리

배열과 차이점

-배열과는 다르게 동적인 자료구조 => 메모리절약

배열은 여분의 공간을 마련해야 하지만 연결리스트는 필요할 때만 메모리를 할당 할 수 있다.

-배열은 연속된 공간을 차지 하는데, 연결리스트는 동적으로 수시로 할당 해제 되기 때문에 메모리의 연속된 공간을 차지하지 못한다. 순서도 제대로 되어 있지 않다.(이런 연결 리스트의 순서를 유지시켜 주는 것은 링크(Link)에 의해서 가능해진다.)

-자료 순서의 재배열이 편하다. (링크가 가리키는 방향만 바꿔주면 된다) 

연결리스트 종류

단순연결리스트

단순 연결 리스트는 정보를 저장하는 노드와 바로 다음의 노드를 가리키는 링크 하나로 구성 되어 있다.

제일 처음의 노드는 누가 가리켜 줄 것인가라는 문제 때문에 사용자에게 알려진 연결 리스트의 입구인 머리가 필요하다. 이 머리는 일반적으로 전역 변수로 선언이 되어 모듈 내의 어떤 부분에서도 접근 가능하도록 개방되어 있고, 소멸되지 않는다. 그리고 연결리스트의 제일 마지막 노드는 항상 무엇인가를 가리켜야 하는데 특별히 마지막을 나타내는 꼬리 노드를 만들어서 마지막 노드임을 표시하게 한다.

스택기반 노드 구현 연습

Node클래스 

연결리스트 초기화

노드 삽입

노드 삭제

원하는 노드 찾기

이중연결 리스트

이중 연결리스트는 단순 연결리스트와 함께 가장 많이 사용된다.

단순 연결리스트가 다음의 노드를 가리키는 하나의 링크를 가져서 바로 전의 노드를 알 수 없던 단점에 비해서,

 이중 연결 리스트는 다음의 노드를 가리키는 링크와 전의 노드를 가리키는 링크 두가지를 가져서 바로 전의 노드에도 접근할 수 있다. 

노드 클래스

단순노드와 다르게, 노드의 이전 노드를 가리키는 prev가 추가 됨.

노드생성

머리와 꼬리를 전역변수로 선언하여 공간을 할당하며 노드를 따라 이동하다가 연결 리스트의 외부로 벗어나어는 일을 방지하기 위해서 머리와 꼬리는 자기 자신을 가리키도록 설정한다.

노드 삽입

t노드 앞에 k값을 갖는 노드를 삽입한다.

노드찾기

노드삭제

정렬된 순서로 노드삽입

Stack 스택

스택,큐,트리와 같은 자료 구조는 자신이 행위적 측면을 포함하는 구조이다.

스택은 밑이 막힌 긴 통이라 생각하고 입,출구가 하나인 과자통을 생각하면 쉽다(프링글스)

 먼저 들어간 것은 가장 나중에 빠져 나오게 된다. (후입선출)LIFO

반대로 가장 늦게 들어간 데이터가 가장 먼저 빠져나가게 되는 것이다.

스택에는 구현방법이 배열구현과 리스트구현 두가지가 있다.

배열은 처음 배열의 크기를 설정해두고 시작해야 하기 때문에 나중에 배열의 크기를 변경 할 수 없는 반면에 리스트구현은 동적인 할당을 통해서 구현되기 때문에 연결리스트로 구현 하는것이 유연하다.

배열로 구현한 스택구조가 더 빠르다고 하는데 하드웨어가 발단된 지금에서는 별 차이가 없다.

그렇기에 이번 학습일지에도 리스트를 이용한 스택구현을 연습!

입출구가 하나이기 때문에 연단순결리스트로 쉽게 구현이 가능하다.

Node클래스

PUSH 데이터 노드 삽입

연결리스트를 이용 할 경우 TOP이라는 변수의 역할은 머리 노드가 대신한다.

머리노드의 다음 노드가 스택의 상단이 되는 것이다.

POP데이터 노드 삭제

후입선출이기 때문에 최상단 노드를 삭제한다.

머리노드의 다음 노드가 꼬리 노드이면 비어있는 스택이다. 

출력

POP하고 다시 출력

이진탐색트리(Binary Search Tree)

Queue 큐

큐는 스택과 다르게 앞뒤가가 뚫린 긴통이라고 보면 된다. 즉 입구와 출구가 다르다.

뒤에서 넣고 앞에서 꺼낸다. 그래서 먼저 들어간 것이 제일 먼저 나오는 FIFO구조이다.

큐를 조작하는 방법에는 put동작과 get동작이 있다.

put  : 뒤에서 넣음

get  :  앞에서 꺼냄

사진 : 위키백과

큐 구현방법에는 배열구현과 연결리스트 구현이 있다. 

큐노드 클래스

큐 초기화(이중연결 리스트)

Put

K의 값은 가지는 노드를 만들어 꼬리의 앞에 삽입한다. 

Get

큐가 비었는지 확인하고(머리노드 다음이 꼬리이면 꺼낼 노드가 없다)

C++같은 메모리 직접 관리가 가능한 언어는 당연히 메모리를 삭제했으니 메모리해제과정이 필요하다.

출력

확인

맨처음 put한 데이터가 맨 위에있다.

Get테스트

유니티) 포물선 궤적그리기

포탄을 날리거나 포탄 궤적을 보여주기 위해 사용된다.

유니티에서는 Line Renderer을 이용해봤다.

나는 포탄궤적이 아닌 캐릭터가 날아갈 점프 궤적을 그리는데 이용했다.

스크립트

셋팅

playerPlane :  라인이 그려질 plane(땅)의 위치를 셋팅해준다. 궤적이 시작하는 위치

targetPoint는 포물선이의 끝점이된다. (내 게임에서는 노란색 circle에서 최종 위치를 받아온다)

체크

Raycast를 통해 마우스가 위치하는 곳을 가져온다. 

center : 시작벡터와 착지위치벡터의 합에 1/2은 위치가 포물선의 중간위치가 된다.

targetRotation : 라인위치와 최종위치를 빼면 포물선의 방향백터를 구할 수 있다. 

(벡터OA -벡터 OB = 벡터BA) center가 아닌 캐릭터의 위치로 계산해도됨)

Physics.Linecast : 포물을 그리는 라인에 물체가 걸리면 부딪힌 지점을 넘겨준다.

실제로 궤적(라인)을 그리는 부분

theArc : 두 벡터 사이를 원하는 간격으로 보간 부분

(이해를 못함.. 이쪽은 공부가 필요하다)

lineRenderer.SetPosition : 위에서 구해준 라인의 벡터들의 위치를 설정

이진트리 구현

순회종류의 맞게 출력결과를 보기 위해 테스트해봤다.

트리는 목적/구성에 따라 맞는 순회방법을 결정해주어야한다.

테스트예제

레벨그림

결과

트리

어떤 요구조건을 만족하는 정점과 선분들의 비어있지 않는 집합

정점은 또한 노드라고도 표현한다.

노드 : 동그라미 하나하나 트리의 요소를 나타냄

루트노드 : 부모노드의 최상단

단말노트 : 자식이 없는 노드

서브트리 : 트리안에 존재하는 트리

트리의 높이 : 가장 최상단부터 레벨을 1,2,3이라 매긴다.

트리의 성질

트리에는 어떤 두 노드를 연결 하는 경로는 한개다. (부모-자식간 양방향의 경로가 있어도 경로는 한개)

어떤 두 노드는 최소 공통 선조를 지님.

루트가 최소공통선조가 되거나 근의 자식들중의 부분트리에 두 노드가 속하게 되므로 최소 공통선조는 항상 존재

각 노드가 최소공통 선조에 이르는 경로를 연결하면 두 노드간 최소 경로가 된다.

이진트리(Binary tree)

각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조로, 자식 노드를 가지는 트리 구조로,

 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다.

이진트리 순회방법

목적/구성에 따라 순회하는 방법이 다르다.(기준은 루트노드 기준)

1. 전위순회(Preorder) - 루트 -> 왼쪽서브트리 -> 오른쪽 서브트리

F, B, A, D, C, E, G, I, H (root, left, right)

2. 중위순회(Inorder) - 왼쪽서브트리 -> 루트 -> 오른쪽서브트리

A, B, C, D, E, F, G, H, I (left, root, right)

3. 후위순회(Posterorder) - 왼쪽서브트리 -> 오른쪽서브트리 -> 루트

A, C, E, D, B, H, I, G, F (left, right, root)

Tree구조

naver

트리는 2차원적 비 선형구조이다. 

나무의 모양을 거꾸로 뒤집어 놓은 모양이다. 

뿌리가 가장 위에 있으며 가지(link)들은 밑으로 벌어지며 향한다.

트리구조에서 쓰는 용어

트리의 성질

-나무 구조에서 한 노드에서 다른 노드로 가는 경로는 유일하다.

(나무를 타는 경로가 중복되지않고, 되돌아감이 없다면)

나무구조의 임의의 두 노드는 최소 공통 선조(두 노드가 갖는 가장까운 부모 노드)를 갖는다. 

-N개의 노드를 갖는 나무는 N-1개의 링크를 가진다.

트리구조는 뿌리 노드를 제외하고 모든 노드가 자신의 선조를 향해 하나의 링크를 갖는다.

그래서 N개의 노드를 가진 나무는 N-1개의 링크를 가진다

-꽉 찬 이진트리는 레벨이 d라고 할때 노드의 수는 N이 다음과 같은 조건을 만족한다.

구글독스 데이터 저장

인게임 데이터를 구글폼과 연동해 저장하기

로그인시스템과(실제 게임과 로그인은 많이 다르 지만) 스코어를 저장시스템을 만들기

1. 구글독스 설정

데이터를 저장할 장소와 입력을 받을 매체를 설정하는 부분이다.

1). 구글설문지

이 구글 설문지가 유니티에서 데이터 입력매체가 되는 것이다.

저장할 데이터 항목 맞게 질문을 추가해준다 (단답형으로 변경)  

질문항목을 다 채웠다면 '응답'탭을 누르고 스프레드 시트를 만들어준다. 

2). 구글스프레드시트

스프레드시트를 열어보면 자동적으로 질문항목들이 채워져있다.

이 부분이 설문지로 받은 입력데이터들이 저장 될 곳이다. 

2. 스크립트 부분

유니티 스크립트에서 데이터를 입력매체(설문지)를 연결하는 방법

설문지에서 '미리보기' 클릭 후 페이지소스 보기

form action = 이 부분이다.

만약 질문 항목이 5개라면 entry 값도 5개 인 것이다

실행 테스트 

5가지 항목을 추가 했다.

nID : 로그인 정보가 입력된 번호(순서)

sID : 아이디

sPassword : 패스워드

sDeviceID : 기기 아이디

eOS : 운영체제 (안드로이드,IOS,PC)

이 부분은 디바이스 아이디를 받아오고, OS정보를 파악 

유니티 INPUT.TEXT를 통해 아이디와 패스워드를 입력한다.

결과

타임스탬프는 설문지를 통해 스프레드 시트를 만들면 자동으로 생성되는 항목인데 데이터를 입력한 시간을 입력해준다.

이 부분은 데이터를 입력하는 부분만 있다. 

로그인이라면 입력한 아이디와 패스워드가 맞는지 체크하는 기능이 있어야한다.  

그럴라면 데이터를 스프레드시트에서 받아오는 기능이 필요하다.

병합정렬(merge sort)

병합의 개념 : 두개 이상의 정렬된 자료집합을 하나의 정렬된 자료집합으로 합치는 것

병합의 방법 : 대상 자료집합이 정렬된 상태이므로 순차적으로 작은 자료를 뽑아서 놓으면됨

데이터의 분포에 영향을 덜 받는다.

즉, 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다. (O(nlog₂n)로 동일)

실제로 숫자들이 정렬되는 과정

거품 정렬

배열의 인접 요소를 비교하여 교환하는 모양이 보글보글하다고 해서 붙여진 이름이다.

거품 정렬은 인접한 배열의 요소를 비교 교환하여 전체적으로는

대충 정렬을 하면서 최대값을 배열의 제일 뒤로 보내는 것을 반복한다.

거품 정렬의 개선

아래 함수를 추가하여 정렬이 되어있는 체크

정렬이 되어 있다면 바로 빠져 나오도록

(but 정렬이 되어있을때는 시간이 적지만 그렇지 않을 경우는 더 시간이 느려진다.

s=0과 if s인지 판단하는 문장이 추가 됐기 때문)

3차원 물체를 그려지는 과정

컴퓨터 모니터는 평면이기 때문에 렌더링 된 3D 장면들은 

2D 이미지로 컴퓨터 스크린에 투영되어야 한다.

스크린에 표시되기 까지 아래 변환 과정이 필요하다.

그 중에서 투영 변환은 월드의 모든 물체를 카메라 공간으로 이동시킨 뒤,

 2차원 평면으로 그려주기 위한 변환이다.

클리핑 : 절두체의 경계에 걸치게 되면 걸쳐진 바깥쪽 부분은 잘려 버려지게 되는 것 (클립 공간에서 수행)

월드 변환

오브젝트 공간은 3차원 세상에서 표현될 각각의 오브젝트들이 정의된 공간이다.

하나의 물체가 자신만의 공간에서 고정 불변의 좌표를 가지는 것이라고 생각할 수 있다. 

이러한 오브젝트 공간의 물체는 다른 오브젝트의 공간과 전혀 관계가 없기 때문에 3차원 세상에서 표현하고자

하는 모든 오브젝트들은 하나의 단일 공간으로 변환 할 필요가 있다. 

이 때 모든 대상들이 모아질 공간을 월드 공간이라 하고, 각각의 대상을 월드 공간에 모으는 과정을 월드 변환이라 한다.

카메라 변환(뷰 공간 / 카메라 공간)

모든 물체가 월드 공간에 모아지면 카메라가 볼 수 있는 영역의 공간을 뷰 공간이라고 한다. 월드 공간의 모든 물체를 카메라 공간으로 변환하게 되면 보다 효율적인 랜더링 알고리즘을 설계할 수 있기 때문에 이 카메라 변환이 필요하다.

투영 변환

투영 변환은 이러한 원근법을 구현하기 위해 카메라 공간에서 정의된 절두체를 축에

나란한 직육면체 볼륨으로 변경하여 카메라 공간의 모든 물체를 3차원 클립 공간으로 변환하는 것을 의미한다.

여기서 투영 변환이라는 이름과 달리 3차원 카메라 공간의 물체를 2차원 평면으로 투영하는 것이 아니라 

또 다른 3차원 물체로 '변형'이다.

이 물체들은 관찰해보면 절두체 뒤쪽에 있던 영역의 폴리곤은 상대적으로 작아진다.(원근법 적용)

투영변환을 통해 원근법이 적용된 3차원 물체들은 직육면체 볼륨의 3차원 클리핑 공간으로 정의되어있다.

그러나 최종적으로 필요한 것은 2차원 사각 영역이다.

3차원을 2차원 공간으로 변환이 필요한 것이다. (단순히 z값을 버린 면? 원근법이 적용이 불가)

바로 Z좌표로 모든 성분을 나눠버리면?

실제 Z값은 투영 변환행렬을 곱한 후 동차좌표계의(x,y,z,w)에서 w성분에 저장되어 있기 때문에 투영변환 이후 w에 저장된 값을 좌표를 나누는 것이다.

나눗셈을 하고 나면 (x, y, z, w)의 동차 좌표 게에서 (x, y, z)의 직교 좌표계로 변화하게 되는데 이를 NDC공간이라고 하는 것이다.(NDC공간은 좌표의 XY범위가 [-1,1]이고, Z범위가 [0,1]이다.)

뷰포트 변환

컴퓨터 화면 상의 윈도는 스크린 공간을 갖는데, 이 스크린 공간 내에 2차원 이미지가 그려질 뷰포트가 정의되는데 NDC공간의 물체들을 스크린 공간으로 이전시키는 변환을 뷰포트 변환이라 한다. 

  출처 http://www.songho.ca/opengl/gl_projectionmatrix.html

https://jidon333.github.io/blog/Rendering-pipeline