마이 플밍 블로그

작은 컨퍼런스에서 발표할때 쓴 AABB OBB GJK에 대한 설명이다. 원래 티스토리에 다시 쓸려고 했는데 귀찮아서 그냥 파일만 올린다. https://www.slideshare.net/ssuserbe87d6/collision-detection-algorithms?qid=d75a9483-0b7a-454a-8797-d3b24c6c4deb&v=&b=&from_search=3 충돌 알고리즘(collision detection algorithms) 충돌 알고리즘인 AABB, OBB, GJK 알고리즘에 대한 설명 www.slideshare.net

보통 가장 간단한 모든 약수를 구하는 알고리즘하면 1부터 N까지 반복문을 돌려 N % i == 0 일경우 약수로 하는 알고리즘을 생각할 것이다. 이경우 시간 복잡도는 O(N)이 되는데 O(√N) 으로 줄일 수있다. 방법은 간단하다. N의 약수들 중 √N 이하의 것들을 구하고 그 것들을 N에 나누면 다른 약수들도 구할 수있다. 예를 들어서 111의 약수를 구할 때 √110 이하의 약수들은 1, 2, 5, 10 이고 이 것들을 110에 나누면 11, 22, 55, 110 이 나온다. #include #include #include using namespace std; vector vec; int main() { int n = 110; // sqrt를 안쓰고 i * i를 이용함 for (int i = 1; i..

1. 유클리드 알고리즘(Euclidean algorithm) 두 자연수의 최대 공약수(greatest common divisor)를 찾는 알고리즘을 뜻한다. 2. 유클리드 알고리즘 원리 두수 A와 B(A>B)가 있고 A를 B로 나누었을때 나머지가 C일 때 C가 0일경우 B가 최대 공약수이고 아닐경우 A = B 로 B = A % B로 하고 반복해서 C가 0일 될때까지 하면 된다. ex) GCD(12, 8) -> GCD(8, 4) -> GCD(4, 0) 최소공배수 = 4 장점 최대공약수를 구하는 방법중 가장 간단한 방법인 1부터 min(A,B)까지 순서대로 찾는 방법의 시간 복잡도는 O(N)이지만 유클리드 호제법을 이용할 경우 O(Log N)으로 줄일 수 있다. 3. 구현(C/C++) 반복문을 통한 GCD ..

GC란? 다들 알다시피 C#은 C나 C++과 달리 직접 메모리 해제를 할 필요가 없다. 이렇게 할 수 있는 이유로는 Garbage Collector라는 것이 있기 때문인데 이것은 CLR(Common Language Runtime, 공용 언어 런타임)에서 자동메모리 관리기능을 한다. GC덕에 우리는 메모리 관리 부담을 덜하면서 개발할 수 있다. 1. CLR의 메모리 할당 C#에서의 할당을 보자면 소스코드 컴파일 후 실행하면 CLR에선 일정 크기의 메모리를 확보하게된다. 이렇게 관리되는 Heap 메모리 영역을 Managed Heap라고 한다. 이렇게 확보한 Managed Heap의 첫번째 주소에 다음 객체를 할당할 메모리 주소를 메모리의 포인터로 가리킨다. 객체를 생성하게 된다면 포인터가 가리키고 있는 주소..

https://www.acmicpc.net/problem/1051 1051번: 숫자 정사각형 N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 www.acmicpc.net 풀이 가장 큰 정사각형의 크기를 구하면 되기 때문에 순회중인 타일의 위치를 (x, y)라고 하고 정사각형의 변의 길이를 i라고 하면 (x+i, y) (x, y+i) (x+i, y+i) 위치의 타일이 순회중인 타일의 번호가 같으면 넓이 비교를 하면 된다. 코드 #include #include using namespace std; int map[100][100]; int flag[100][100][4..

https://www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범 www.acmicpc.net 문제에선 Convex Hull에 대한 설명을 하는데 Convex Hull이란 가장 바깥쪽에 있는 정점들을 이어서 만드는 볼록 다각형을 뜻한다. 이런 Convex Hull을 만드는 알고리즘 중에서는 Graham's Scan 알고리즘이 있다. 이 문제는 Graham's Scan 알고리즘으로 풀었는데 이 알고리즘에 대해 설명하자면먼제 Convex Hull을 자세히보면 이어진 정점들이..

C++의 STL에는 Vector와 List라는 컨테이너가 있다. 언뜻보기에는 두 컨테이너에는 차이가 없는것 처럼 보이지만 사실 큰 차이점이 있다. 1. Vector Vector 컨테이너는 일반적인 배열처럼 연속적인 메모리 공간에 저장하는 방식. 후에 들어올 요소들을 대비해 미리 예비 공간을 할당함. 배열과 달리 크기의 제한을 받지않음.(32bit 기준으로 10억개 정도는 있긴함) 맨뒤에 추가하는건 빠르지만 중간에 삽입할 시 O(n)만큼의 시간이 걸림. 중간에 삽입시 원소들을 뒤로 밀어냄. [1] 과 같이 랜덤 접근이 가능함. 동적으로 크기가 확장되지만 비용이 큼 2. List List 컨테이너는 더블 링크드 리스트로 구현되어 있음. 값을 추가할 때마다 메모리를 할당함 중간에 있는 특정 원소를 찾기 위해서..

DCEL 이중 연결 가장자리 목록 혹은 half-edge data structure 라고도 불리는 이것은 일반적으로 위처럼 폴리곤이 Face Vertex Edge 3개의 요소로 이루어지는 구조를 뜻하는데 각 요소의 뜻은 다음과 같다. Face - 폴리곤의 내부 Vertex - 폴리곤의 정점 Edge - 폴리곤의 가장자리 DCEL은 위와같은 모습이 되는데 한 폴리곤의 내부가 시계방향 혹은 반시계방향으로 정렬되 있는데 만약 모서리가 면의 경계에 있다면 그 위치에 있는 모서리는 두개이고 각 모서리를 가진 폴리곤의 회전 방향은 정 반대이다. 방향만 다른 같은 모서리가 두개있는 것이 마치 한 모서리를 반으로 가른것 같아서 half-Edge라고도 불리는 것 같다. 폴리곤을 이루는 각 요소는 다음과 같은 데이터를 가..

CCW란? CCW(Counter Clock Wise)는 시계반대 방향이라는 뜻으로 점 A B C가 있다고 했을 때 벡터 AB를 기준했을 때 C가 오른쪽에 있는지 왼쪽에 있는지를 알아내는 방법을 뜻한다. CCW를 구하는 방법은 외적을 통해서 구할 수 있다. 두벡터를 외적하면 새로운 벡터가 생기는데 그 벡터는 두 벡터의 수직인 벡터로 외적을 통해 생성된 벡터의 크기는 두 벡터를 변으로 하는 평행사변형의 크기가 된다. 외적의 값은 오른손 좌표계, 왼손 좌표계를 하느냐에 따라 값이 틀리게 나오는데 오른손 좌표계를 기준으로 값을 구하겠다. 위는 외적의 공식으로 2차원 평면에서 외적을하면 새로 생긴 벡터의 x와 y 값은 0이된다. z는 해당 벡터의 크기가 되고 그 값의 부호에 따라서 CCW를 판별할 수 있다. 선분..

개인적으로 공부한 것을 정리한 글입니다. 틀린내용이 있을 수도 있으니 주의해주세요. 운동량(momentum) - 뉴턴 역학에서 질량과 속도의 곱을 뜻함 운동량을 p 질량을 m 속도를 v라고 하면 위와같이 정의할 수 있다. 충격량(impulse) - 두 물체가 충돌했을 때 운동량의 변화량 운동량 보존 법칙 물체에 외부의 힘이 작용하지 않는다면 그 물체가 가진 총 운동량은 바뀌지 않는다. 서로 다른 두 물체가 충돌하더라도 총 운동량은 변하지 않는다. m이 질량 v가 속도 v^를 충돌 후 속도라고 하면 다음식이 된다. 반발계수 반발 계수는 두 물체가 충돌 전후의 속도 비율을 나타내는 분수로 0과 1사이값이다. e = 1 일시 탄성충돌(에너지 보존) 0 < e < 1 일시 비탄성충돌 e = 0 일시 완전비탄성충..