Gyong

• Convex는 무엇인가?
  
  

Convex는 한국말로 "볼록하다"또는 볼록 모양으로 된 집합으로도 표현을 하는데

이와 반대로 Concave(오목하다)라는 것도 존재한다.

그런데 이것을 수학적으로 설명하려면 어떻게 해야 되는지 고민을 하게 된다. 

정의된 것 중에 영어로 정리가 된 것이 있어서 살펴보려고 한다.

"A Subset C of S is convex if, for all x and y in C, the line segment connecting x and y is included in C."

해석을 하자면

"S의 부분 집합 C를 Convex라 하고 C에 속한 모든 x, y에 대해서 x, y를 연결한 선분이 C안에 포함되어있다면 C를 Convex라고 한다."라고 할 수 있다.

이것을 의역해보면 "무수한 점으로 된 집합이 있는데, 여기서 아무 점이나 두 개를 찍고 연결을 하였을 때
해당 선분을 Convex라고 한다."라고 생각하면 된다.

Convex와 반대로 Concave(오목하다)가 존재한다.

• Convex의 성질이 왜 중요한가

충돌처리를 할 때 Convex 모양으로 만들어주면 편리하다.

왜냐하면 Convex는 SAT(Seperating Axis Theorem)라는 성질이 만족하고,
이 성질을 통해서 충돌 처리를 할 때 충돌이 됐는지 안됐는지 확인을 할 수 있기 때문이다.

위에 그림을 보면 어떤 축을 찾았을 때 그것이 서로 떨어져 있는 것을 볼 수 있는데,

이것은 충돌하지 않았음을 의미한다.

이로써 Convex가 가지는 특징은 "충돌체크를 할 때 유용하다."라고 볼 수 있다.

• Line(직선)의 생성 조건

선이 무한대에서 -무한대의 범위로 제한을 두지 않고 쭉 연결했을 때

• Ray(반직선)의 생성 조건

선이 무한대에서 한쪽으로만 뻗어나가 0으로 고정시키게 되는 경우

• Segment(선분)의 생성 조건

선이 0~1 사이가 되는 경우

• Affine Set?
  
  점의 집합

Affine Set 안에는 요소(점)가 있고, 이 요소들을 묶음으로써 하나의 집합이 만들어진다.

이 요소들은 개별적으로 하나의 독립된 물체이기 때문에 따로 사용할 수가 없다.

그래서 집합에 있는 요소들을 사용하려면 점과 점 사이에 연관 관계가 있어야 한다.

벡터 공간으로 예를 들어보면

벡터 공간 안에는 A라는 벡터와 B라는 벡터가 있고, 이 요소들은 서로 간의 구별될 수 있는 독립적인 물체이다.

하지만 이 벡터 공간에 있는 벡터를 정의하기 위해서는 연산자가 필요하다.

왜냐하면 연산자가 있어야 계산을 해서 활용을 할 수 있기 때문이다.

벡터에서 사용하는 연산자는 덧셈과 스칼라곱이 있다. 이러한 연산자들이 있기 때문에 새로운 벡터를 만들 수 있다.

만약 연산자라는 것이 없으면 A벡터와 B벡터는 서로 연관 관계가 없기 때문에 새로운 벡터를 만들 수가 없다.

아핀 공간도 마찬가지이다. 공간 안에 요소만 있고 연산자가 없으면 이 요소들을 활용을 할 수가 없다.

아핀 공간 역시 뺄셈 연산자로 인해서 점과 점 사이의 최단 거리를 계산할 수 있는 벡터가 존재하고,

bijection(전단사 함수) 성질을 가지고 있기 때문에 벡터와 크기가 같으며 반대 방향인 "역 벡터"도 존재한다.

따라서 이러한 벡터의 연산을 통해서 아핀 공간에 있는 점들을 활용할 수가 있다.

이것을 이제 시각적으로 표현을 해보자

부분 공간으로 생각을 해보면, 새로운 차원에서 마지막 차원의 값이 0인 부분이 벡터이고 1인 부분이 점이 되고,

3차원 공간으로 생각을 한다고 하면 벡터는 (x, y, z, 0)이 되고 점은 (x, y, z, 1)이라고 보면 된다.

이것을 연산을 해보면

점 - 점 = 0

점 + 벡 = 1

벡터 + 벡터 = 0 이 나오게 된다.

그렇다면 점 + 점은 가능할까?

가능은 하다. 하지만 특정 조건에서만 가능하다.

임의의 a라는 점과 b라는 점이 존재할 때 이 두 개의 점의 합이 반드시 1이 나와야 한다는 결론이 나와야 한다.

공식을 만들어보면

a (x1, y1, z1, 1)

b (x2, y2, z2, 1)

(ax1, ay1, az1, a) + (bx2, by2, bz2, b) = (ax1 + bx2, ay1 + by2, az1 + bz2, a+b)에서

a+b의 값이 1이 나오게 되면 점의 성질을 만족하게 된다.

이런 것을 이제 "아핀 조합"이라고 하는데 아핀 조합의 공식을 보면 위에 적힌 공식과 같다.

따라서 아핀 조합을 이론적으로 보면 "여러 점들을 선형 조합할 때 계수의 합을 1로 제한하게 되는 것" 이라고도 하지만

위와 같이 직접 공식을 만들어서 알아볼 수도 있다.

이러한 방식으로 만들어진 형태는 다음과 같다.

이렇게 해서 새로 만들어 진 점을 "무게 중심"이라고 한다.

무게 중심을 이제 계수로 표현을하면 아래와 같다.

표현된 계수를 앞서서 말한 것처럼 하면 (a, b)가 되고, 이것을 이제 "무게 중심 좌표"라고 한다.

무게 중심 좌표를 설명하자면 새롭게 두 점을 덧셈으로 조합해서 생성된 점이 "무게 중심"이고,

그 것을 만드는데 기여한 계수(a, b)를 묶어서 벡터로 만든 것이라고 생각하면 된다.

• STL Vector란 무엇인가?
  
  Vector는 임의 접근 반복자를 지원하는 배열 기반 컨테이너이다.
  일반적으로 배열처럼 개체들을 연속적인 메모리 공간에 저장한다.
  
  
  
• Vector의 시간 복잡도

• Linear Search(선형 탐색)란 무엇인가?
  
  데이터가 모인 집합(배열, 리스트 등)의 처음부터 끝까지 하나씩 순서대로 비교하며 원하는 값을 찾아내는 선형 탐색 알고리즘이다.
  
  

• Binary Search(이진 탐색)란 무엇인가?
  
  오름차순으로 정렬된 배열에서 중간 값 부터 위치를 찾는 이진 탐색 알고리즘이다.

• Linear Search와 Binary Search의 차이점

• Linear Search와 Binary Search의 장점

• Linear Search와 Binary Search의 단점