어느 게임 개발자의 기록

C++에 대한 문법을 공부하다가 Placement new라는 문법을 알게 되었다.

뭔가 어렵기도 하고 사용법이 다소 까다롭기도 하지만, 메모리 풀링을 할 때 중요하게 사용되는 문법이라고 한다.

먼저, Placement new를 이해하기 전에 malloc과 new의 차이점을 알고 있어야 한다 

모른다면 아래 링크를 참고하도록 하자.

C++ 문법 - malloc와 new의 차이 (tistory.com)

먼저, new의 작동 방식을 알아보자.

1. 전역 함수인 operator new를 실행하여 메모리를 할당한다.

malloc과 동일하게 사이즈만큼의 메모리 영역을 할당한 뒤, void*를 반환한다.

2. 할당된 영역의 내부의 값을 초기화해준다.

new의 경우 malloc과 다르게 내부의 값을 초기화해준다고 하였다. 이 과정에서 초기화가 이루어진다.

3.사용자가 요청한 자료형으로 포인터를 반환해준다.

malloc처럼 void*가 아닌, int*, char*등의 지정한 자료형으로 주소를 반환받을 수 있는 이유는 내부에서 변환을 해주기 때문이다.

new는 이렇게 3개의 과정을 거친다.

이 중에서 2번의 과정에 사용되는 문법이 placement new 이다.

placement new는 메모리를 할당해주는 문법은 아니다. 이미 할당되어 있는 메모리 영역을 초기화해주는 문법이다.

operator new를 통해, 메모리 영역을 할당하였다고 가정해보자.

이런 형태로 내부엔 쓰레기 값이 담겨있을 것이다.

하지만, 우리가 사용하기 위해선 우리가 사용할 데이터를 저 곳에 집어넣어야 한다.

그 역할을 해주는 것이 placement new이다.

int main()
{
    void* Pointer = operator new(sizeof(int));
    int* I = new(Pointer) int;
    
    return 0;
}

위와 같이 void*형으로 메모리만 할당받은 뒤에, 나중에 new(주소값) 의 형태로 초기화를 해준다.

괄호 안에 있는 주소가 가리키는 메모리 영역을 원하는 자료형으로 초기화하는 것이다.

아래와 같이 오버로딩된 생성자도 사용 가능하다.

class Test
{
public:
	Test() {};
	Test(int _X, int _Y) : X(_X), Y(_Y) {}
	~Test() { std::cout << "Delete\n"; }

	int GetX()
	{
		return X;
	}

	int GetY()
	{
		return Y;
	}

private:
	int X = 0;
	int Y = 0;
};

int main()
{
    void* Pointer = operator new(sizeof(Test));
    Test* T = new(Pointer) Test(4, 5);
    
    T->~Test();
    delete Pointer;
    
    return 0;
}

그런데 위 글을 보면 이상한 점이 한가지 있다.

바로 소멸자를 직접 호출해주고 있다는 점이다.

왜 그럴까?

먼저, 위의 코드를 보면 소멸자가 호출될 때 Delete라는 문자열을 출력하도록 해주었다.

소멸자를 호출하는 코드에 주석을 친 뒤에 프로그램을 실행해보면, Delete가 출력되지 않는다.

이렇게 아무것도 출력되지 않는다.

반면 소멸자를 직접 호출해주면?

위와 같이, Delete가 출력되는 것을 볼 수 있다.

왜 그럴까? 기본적으로 메모리 할당을 void* 형의 Pointer라는 변수에다가 할당을 해주었다.

그렇기 때문에 메모리 해제를 할 때에도 delete Pointer; 로 Pointer가 가리키는 주소의 메모리를 해제해 주었다.

하지만, Pointer는 void 타입이기 때문에 해당 영역의 소멸자를 호출해줄 수가 없다.

그렇다면, delete T;를 호출해준다면?

물론 소멸자가 잘 호출이 된다. 하지만, 문제가 있다.

아래와 같이 Pointer에는 메모리 할당을 크게 해놓고, 여러개의 객체를 사용하는 상황이다.

이 때, delete T를하면 T_2는 어떻게 해야할까?

T_2가 있는 메모리 영역도 해제되어 버린다. 물론 소멸자는 호출되지 않은 채로 말이다.

그렇기 때문에, 명시적으로 메모리 공간 내에 있는 모든 객체의 소멸자를 호출해준 뒤에 메모리영역을 해제하는 것이 훨씬 안전하고 적합한 방법이다.

placement new의 경우, 이미 할당된 메모리 영역에 초기화만 해주는 방식이기 때문에 동적할당된 메모리 영역이 아닌 스택 메모리에서도 사용할 수 있다.

int main()
{
    char Array[sizeof(Test)] = {0,};
    Test* T = new(Array) Test(4, 5);
    
    return 0;
}

이런 식으로 스택 메모리에도 사용할 수 있다. 어디에 활용해야 하는지는 모르겠지만, 할 수 있다는 것 쯤은 알아두자.

여기까지 placement new에 대해 알아보았다.

사용되는 곳은 참 많겠지만, 가장 많이 사용되는 곳은 메모리 풀링이라고 한다.

메모리를 한 번에 덩어리로 할당해놓고, 필요할때마다 필요한 크기만큼 placement new로 초기화하여 사용하는 것이다.

소멸자도 직접 호출해줘야 하고, placement new를 할 때, 메모리,주소의 오프셋도 잘 관리해야 하는 만큼 번거롭고 헷갈리는 부분이 많지만 실제 프로그래밍에서 사용되고 있는 만큼 지식을 쌓아두면 좋을 것 같다.

malloc는 C스타일의 동적 할당이고, new는 C++ 스타일의 동적 할당이다.

둘의 차이를 알아보도록 하자. 

1. 반환형의 차이

malloc의 경우, 말 그대로 메모리만 할당을 해준다. 내가 20바이트를 요구했다면 정확히 20바이트의 메모리 공간을 할당하여, 가장 앞의 주소값을 반환해준다. 메모리 공간만 할당해주었기 때문에 반환형이 void* 이다.

그렇기 떄문에 malloc으로 할당받은 메모리 영역을 사용하기 위해선 원하는 자료형으로 타입캐스팅을 해야 한다.

반면, new의 경우는 내가 요청한 자료형으로 타입캐스팅을 해서 반환해준다. int형으로 요청했다면 int*타입으로 반환해주며, Test라는 클래스로 요청했다면 Test*형으로 반환해준다.

2. 초기화의 차이

malloc의 경우 해당 메모리 영역을 초기화하지 않고, 그대로 넘겨준다. 개발자쪽에서 직접 초기화를 해주어야 한다.

반면, new의 경우 기본 생성자를 호출하여 메모리를 초기화 한 뒤에 반환해준다.

물론, 아래 코드처럼 인자를 넣어 오버로딩한 생성자를 사용할 수도 있다.

class Test
{

public:
    Test(){}
    Test(int _X) : X(_X){}
    
    int X = 0;
};

int main
{
    Test* T1 = new Test();
    Test* T2 = new Test(3);
}

3. 메모리 크기 조절 여부

malloc의 경우 realloc이라는 함수를 사용하여 할당받은 메모리영역의 크기를 조절할 수 있다.

물론 안정성, 오버헤드 등의 이유로 권장되지는 않는다고 한다. 하지만, 크기를 조절하는 것이 가능은 하다. 

반면, new의 경우는 재조정을 할 수가 없다. 크기를 늘리고 싶다면 새로운 메모리를 할당받은 뒤, 기존 데이터를 복사하고 다시 기존의 메모리 영역을 해제하는 작업을 해야한다.

4. 예외처리 방식

malloc의 경우 메모리 할당을 실패하게 되면, NULL을 반환하도록 되어있다.

그렇기 때문에 malloc으로 할당받은 메모리 영역에 대해서는 아래와 같이 예외처리하는 것이 일반적이다.

int main()
{
	int* I = (int*)malloc(sizeof(int));
    
    if(I == NULL)
    {
    	std::cout << "Memory allocationg failed";
        return 1;
	}

	return 0;
}

다만, new의 경우는 다르다. 메모리 할당이 실패하면 null을 반환하지 않고  bad_alloc이라는 예외가 발생한다.

그렇기 떄문에, 이 예외에 대한 처리를 해주지 않으면 프로세스가 그대로 종료되어 버린다.

try 
{
    int *I = new int();
}
catch (std::bad_alloc &exception)
{
    cout << "exception :" << exception.what() << endl;
    std::abort();
}

하지만, 이렇게 사용하면 new를 할 때마다 try-catch를 해주어야 하고 매우 번거롭고 코드도 지저분해진다.

그래서, 아래와 같은 방식을 사용하는 것이 권장된다.

void handler() 
{
    cout << "Memory allocating is failed" << endl;
    std::abort();
}

int main(void) 
{
    std::set_new_handler(handler);  
    int *arr = new int();
    
    return 0;
}

std::set_new_handler()는  c++ 표준 라이브러리에서 제공해주는 함수이다.

함수를 콜백으로 등록해놓으면, new가 실패할 때 알아서 등록한 함수를 기반으로 예외처리를 실행해준다.

5. 메모리 해제 방법의 차이

malloc으로 할당받은 메모리 영역은 free로 해제해준다.

반면, new로 할당받은 메모리 영역은 delete로 해제해주어야 한다.

여기서 한 가지 주의점은 new로 메모리를 할당할 때, int* I = new I[100]; 과 같이 배열로 할당받았다면

메모리를 해제할 때 delete가 아닌 delete[]로 해주어야 한다.

delete는 메모리 영역을 통채로 해제하기 때문에, 소멸자를 단 1회만 실행한다.

(배열이 아니라면, 객체가 1개만 있는 것이 정상적인 상황이기 때문에)

반면, delete[]의 경우엔 배열 원소의 개수만큼 소멸자를 호출해준다.

원소가 10개가 있으면 10개 모두 소멸자를 호출해주는 셈이다. 배열 형식으로 동적할당을 해놓고 delete로 해제해버리면 원소중 맨 앞에있는 원소의 소멸자만 호출되고 나머지는 호출되지 않기 때문에 반드시 delete[]를 사용해야 한다.

어떤 짝수가 주어졌을 때, 두 소수의 합이 이 짝수가 되는 경우 중 두 소수의 차이가 가장 적은 경우를 출력하면 된다.

예를 들면, 14의 경우 3 + 11이기도 하지만, 7 + 7이기도 하다.

이런 경우엔 7, 7을 출력하면 된다.

문제 풀이 

먼저, 에라토스테네스의 체를 이용하여 소수만을 걸러내고 시작하였다.

본인이 에라토스테네스의 체를 모른다면 아래 링크를 참고하도록 하자.

알고리즘 - 에라토스테네스의 체 (소수 판별) (tistory.com)

n의 범위가 1부터 10000까지이기 때문에 먼저 10000이하의 모든 소수만을 판별해주었다.

벡터를 하나 선언한 뒤, 10001의 사이즈로 resize해주었다.

에라토스테네스의 체를 이용하여 해당 인덱스가 소수가 아니라면 값을 0으로, 소수라면 값을 -1로 저장해주었다.

이후, 어떠한 짝수 N이 입력된다면 이 짝수를 이루는 두 소수의 합을 구하기 위해 본인은 아래와 같은 방법을 사용하였다.

먼저 N을 반으로 나누었다.

이렇게 숫자를 절반으로 나누어주었다.

N이 양의 짝수이므로 N/2는 반드시 자연수이다.

그렇다면 먼저 N/2가 소수인지 판별을 해보자.

위에서 에라토스 테네스의 체를 이용하여, 소수 판별을 해두었기 때문에 N/2가 소수인지는 바로 알 수 있다.

만약 N/2가 소수라면, 그대로 N/2 N/2 를 출력해주면 된다.

N/2와 N/2는 합이 N인 두 소수이며, 그 차이가 0으로 가장 작은 차이값이기 때문이다.

만약, N/2가 소수가 아니라면 이제 반복문을 돌며 판별할 것이다.

먼저 한쪽의 N/2에는 1을 빼주고, 한쪽의 N/2에는 1을 더해줄 것이다.

이렇게 해주자. 두 수의 합이 N이 되려면 반드시 한쪽은 N/2보다 작아야 하고, 한쪽은 N/2보다 커야한다.

그렇기 떄문에 한쪽엔 1을 빼주고 한쪽엔 1을 더해주었다.

이 때, N/2 - 1과 N/2 + 1 이 둘 다 소수라면? 그대로 N/2 -1과 N/2 + 1을 출력해주면 된다.

이걸 반복문으로 계속 돌리며 확인하면 된다.

이렇게, 더하고 빼는 수를 1씩 올리면서 계속 검사하면 된다.

그러다가 처음으로 두 수가 모두 소수가 된다면, 그 숫자를 그대로 출력해주면 된다.

당연히 처음 발견된 두 소수가 그 차이가 가장 적을 수 밖에 없다.

N/2 - i 와 N/2 + i 두 수의 차이는 2i이다.

먼저 발견될수록 i가 더 작기 때문에, 2i의 값도 더 작다.

그러므로 가장 빨리 발견된 두 소수를 답으로 출력해주면 된다.

풀이 코드

std::vector<int> Nums(10001, -1);
Nums[1] = 0;

for (int i = 2; i * i <= 10000; i++)
{
    if (Nums[i] != -1)
    {
        continue;
    }

    for (int j = i + i; j <= 10000; j += i)
    {
        Nums[j] = 0;
    }
}

먼저 에라토스테네스의 체를 이용하여 최대 범위인 10000개의 숫자에 대해 소수를 판별해주었다.

int NumOfTestCase = 0;
std::cin >> NumOfTestCase;

std::vector<std::pair<int, int>> Answers(NumOfTestCase);

이후, 테스트케이스의 수를 입력받고, 답을 모아둘 벡터를 하나 선언하였다.

마지막에 답을 한 번에 출력할 것이기 때문이다.

for (int Case = 0; Case < NumOfTestCase; Case++)
{
    int TargetNumber = 0;
    std::cin >> TargetNumber;

    int Half = TargetNumber / 2;

    for (int i = 0; i < Half; i++)
    {
        if (Nums[Half - i] == -1 && Nums[Half + i] == -1)
        {
            Answers[Case] = { Half - i, Half + i };
            break;
        }
    }
}

이후, 위에서 말한 내용을 그대로 코드로 구현하면 끝이다.

먼저, 수를 입력받은 뒤 그 수의 절반을 계산한다.

이후, 그 나누어진 두 절반에서 한 쪽은 i를 빼고, 한 쪽엔 i를 더해주며 두 수가 모두 소수인지 판별하였다.

처음으로 발견된 두 소수를 답에 저장한 뒤, 반복문을 탈출하면 된다.

for (int i = 0; i < NumOfTestCase; i++)
{
    std::cout << Answers[i].first << " " << Answers[i].second << "\n";
}

return 0;

테스트 케이스가 모두 끝난 뒤, 답을 한 번에 출력해주면 된다.

에라토스테네스의 체란, 일정 범위안에 있는 숫자들 중 소수만와 소수가 아닌 수를 구별하기 위한 알고리즘이다.

이렇게, 1부터 25까지의 숫자가 있다고 해보자.

이중에 소수만을 판별하면, 이렇게 된다.

이 그림처럼 소수만 걸러내는 알고리즘이 에라토스 테네스의 체이다.

그렇다면, 어떻게 알고리즘이 작동할까?

어렵지 않다.

먼저 소수란, 1과 본인을 제외한 어떠한 약수도 가지지 않는 수이다.

다르게 말하면, 1이 아닌 다른 어떠한 수의 배수도 되지 않는다는 뜻이다.

그렇다면, 2부터 시작해서 25까지 배수를 모두 제거한다면 남는 수가 소수라고 할 수 있지 않을까?

그림으로 보자.

이게 최초의 상태이다.

여기서 2의 배수를 먼저 제거해보자.

파란색으로 칠해진 부분이 제거된 숫자이다.

2의 배수를 모두 제거해보았으니, 3의 배수도 제거해보도록 하겠다.

이번엔 5의 배수도 지워보자.

이렇게 되었다. 5까지밖에 반복문을 돌지 않았는데도 소수만 남은 상태가 되었다.

그런데 보면 한 가지 문제점이 보인다.

2, 3, 5 또한 소수인데 불구하고 함께 제거해버린 것이다.

이런 일을 방지하기 위해, 배수를 제거할 때엔 본인은 제외하고 다음 배수부터 제거하는 것이 옳다.

2, 3,5 를 다시 추가해주면 아래와 같이 소수만 남는 것을 볼 수 있다.

마지막으로, 1의 경우는 소수가 아니다.

2의 배수부터 제거했기 때문에 마지막에 1이 남아있는 것을 볼 수 있다.

그러므로 1도 제거해주자.

이렇게 배수를 차례대로 지워나가면서 소수만 걸러내는 것이 에라토스 테네스의 체이다.

매우 간단하다.

하지만, 상식적으로 생각했을 떈 1~25까지 반복문을 다 돌아야할 것 같은데

실제로는 2~5까지만 돌았음에도 모든 소수가 제거되었다.

왜 그럴까? 

이는 우연이 아니다. 실제로 1~N까지의 소수를 판별하고 싶다면, sqrt(N) 까지의 배수만 검사해도 모든 소수를 판별할 수 있다.

다음은 이에 대한 수학적 증명이다. 어렵진 않으니 참고하도록 하자.

먼저, N이라는 자연수는 어떠한 실수의 제곱으로 표현할 수 있다.

N = m * m; 이라고 표현해보자.

이번엔 N을 어떠한 두 약수의 곱으로 표현해보자.

N = a * b 가 될 것이다.

여기서 a,b 와 m의 관계를 생각해보자.

먼저 a * b =  m * m 이다.

이 식을 보면 3가지의 경우를 나누어 볼 수 있다.

1. a == m , b == m 인 경우

당연히 a와 b가 m과 동일한 경우가 있을 것이다.

2. a > m, b > m 인 경우

다음 경우를 생각해보면, a와 b가 모두 m보다 클 수는 없다.

m보다 큰 두 수의 곱이라면 당연히 N보다 큰 값이 나오기 때문이다.

그러므로, 이러한 경우는 존재하지 않는다.

3. a < m , b > m 혹은 a >m , b < m 인 경우

a과 b가 m과 같지 않은 수라고 한다면, 두 숫자중 하나는 반드시 m보다 커야하고 남은 하나는 m보다 작아야 한다.

둘 다 m보다 크다면 a와 b의 곱은 N보다 큰 값이 나올 것이며, 둘 다 m보다 작다면 a와 b의 곱은 N보다 작은 값이 나올 것이다.

즉, N이라는 숫자는 반드시 sqrt(N)보다 작거나 같은 수의 배수가 될 것이다.

그러므로, 1~sqrt(N)까지의 수의 배수만 검사하여도 1~N 까지의 모든 배수를 제거할 수 있는 것이다.

코드 구현

이를 코드로 구현해보자.

int N = 100;
std::vector<int> Nums(N + 1, -1);

먼저, N을 100이라고 가정해보자.

Nums 배열의 값은 최초에 -1로 초기화 하였다.

만약, 해당 인덱스가 소수가 아니라고 판별된다면 값을 0으로 바꿀 것이다.

당연히 int가 아닌 bool값을 활용하여 구현하여도 된다.

Nums[1] = 0;

1은 소수가 아니므로, 먼저 제거해주자.

for (int i = 2; i * i <= N; i++)
{
    if (Nums[i] != -1)
    {
        continue;
    }

    for (int j = i + i; j <= N; j += i)
    {
        Nums[j] = 0;
    }
}

그 다음은 위와 같이 반복문을 돌리면 된다.

반복문의 조건을 보면, i * i <= N 까지로 조건을 설정해두었다.

위에서 말했듯이 N의 제곱근까지만 반복문을 돌면 된다.

i * i <= N 이나 i <= sqrt(N) 이나 동일하기 때문에 편한대로 사용하면 된다.

i*i는 매 프레임마다 곱하기 연산을 해주어야 하지만, sqrt(N)의 경우 처음 한 번만 하고 변수에 저장한 뒤 사용하면 되기 때문에 최적화를 조금이라도 노리려면 sqrt(N)을 하는게 더 좋을 수도 있다.

(다만 sqrt연산 자체가 곱하기에 비해 매우 느린 편이라 N이 충분히 크지 않다면 별 효과 없을 수도 있다.)

이후 내부 코드를 보자.

해당 인덱스의 값이 이미 0이라면, 이미 제거된 수이다.

당연히 이 숫자의 배수도 제거되었을테니 검사할 필요 없이 continue하면 된다.

제거되지 않은 수라면 그 숫자의 배수를 모두 지워나가면 된다.

위에서 말했듯이, 시작 인덱스는 i부터가 아니라, i + i 부터 시작하고 있다.

첫 번째 수는 반드시 소수이기 때문에 두 번째 배수부터 제거해나가면 된다.

이러면 에라토스 테네스의 체 끝이다.

이제, 배열의 값을 기반으로 남은 소수를 출력해보면 아래와 같이 소수만 걸러져 나오는 것을 확인할 수 있다.

에라토스 테네스의 체는 어렵지 않은 알고리즘이다.

하지만, 소수에 관한 문제가 나온다면 거의 100%확률로 사용되는 알고리즘이기도 하다.

알고 있는 것과 모르는 것은 문제를 푸는 것에 있어 천지차이이기 때문에 반드시 숙지하도록 하자.

유니온 파인드란, 노드간의 집합을 구분하는 알고리즘이다.

위 그림과 같이 10개의 노드가 있다고 해보자.

이 때, 같은 색을 가진 노드끼리 구분하여 집합을 연결하고 싶다.

이런 식으로 말이다.

그렇다면, 어떻게 이렇게 구분을 지을 수 있을까?

가장 간단한 방법은 배열을 만드는 것이다.

배열을 만들어서 파란색이면 1번, 초록색이면 2번, 주황색이면 3번으로 입력한 뒤,

배열을 1~N까지 순회하며 값을 갱신해주면 된다.

하지만, 다음의 경우엔 어떨까?

위 문제처럼 직접적으로 어떤 노드가 파란색인지 초록색인지 정보가 없고, 두 노드가 색이 같다는 정보만 주어지는 것이다.

예를 들어 입력이 아래처럼 들어왔다고 해보자.

1 2
2 3
3 4

5 6
5 7

8 10
9 10

12가 같은색이고, 23이 같은 색이고 34가 같은 색이다.

56이 같은 색이고 57이 같은 색이다.

8 10이 같은 색이고, 9 10이 같은 색이다.

이렇게, 어떤 노드가 같은 색을 가지고 있는 가에 대한 정보만 주어지고, 정확히 무슨 색인지 주어지지 않는다면

위에서처럼 배열을 순회하며 값을 특정 색상으로 갱신하는 방법은 불가능해진다.

이런 경우에 사용하는 알고리즘이 union_Find알고리즘이다.

union - find 알고리즘은 이름 그대로, Union과 Find의 2개의 기능으로 구성된다.

1. Union

    : 같은 속성을 지닌 노드들을 하나의 집합으로 합치는 것.

2. Find

    : 노드가 어느 집합에 속하는지 찾아보는 것.

그렇다면 그걸 어떻게 구현하게 될까?

아래 그림을 보자.

정확한 색은 알 수 없지만, 위와 같은 연결 관계가 주어져있다는 것은 입력을 통해 확인하였다.

그렇다면, 연결된 노드끼리 합쳐서 하나의 집합으로 만들어 볼 수 있을 것이다.

이 과정을 union이라고 한다.

위에서 그림을 보면, 12, 34, 23의 연결관계를 보면 오른쪽처럼 1-2-3-4로 하나로 묶을 수 있다.

나머지 노드들도 위의 그림처럼 하나의 집합으로 묶을 수 있을 것이다.

그런데, 단순히 이렇게 집합만 묶어버리면 Find연산을 할 수가 없어진다.

Find연산이란, 특정 노드가 어느 집합에 속해있는가를 찾는 연산인데 이렇게 하나로 묶어버리기만 하면, 집합간의 관계를 구별할 수가 없다. 무슨 말이냐면, 1과 5가 같은 집합에 속해있는가? 3과 7이 같은 집합에 속해있는가? 를 묻는다면 그걸 구별할 방법이 없다는 것이다.

그렇기 때문에, 트리 구조를 사용할 것이다.

이렇게, 선형적인 연결에서 트리구조로 바꾸게 되면, 루트 노드의 인덱스를 통해 집합을 서로 구분할 수 있게 된다.

예를 들어보면, 2가 속한 집합의 루트노드는 1이고 3이 속한 집합의 루트노드 역시 1이다.

그러므로 두 노드는 같은 집합에 속한다고 표현할 수 있게 되는 것이다.

즉, Union이란 같은 속성을 지닌 노드를 트리구조로 구축하는 것이며

Find란 노드의 루트 노드를 검사하는 일이 되는 것이다.

그렇다면, 구체적으로 어떻게 Union과 Find가 작동하는지 알아보도록 하자.

유니온 파인드

먼저, 각 노드별로 부모 노드가 어디인가를 저장하는 배열을 하나 선언해야 한다.

std::vector<int> Parents;

노드의 개수가 10개라고 했을 때, 배열을 표로 그려보자.

각 배열의 원소는 인덱스에 해당하는 노드의 부모 노드가 누구인가를 가리키는 것이다.

예를 들어, 2번 원소의 부모노드가 6번이라고 한다면 2번 원소의 값은 6이 되는 것이다.

최초에는 이 배열의 값을 인덱스로 초기화 할 것이다.

이 값은 Union과정을 거치면서 계속 바뀌게 될 것이다. 하지만, 변하지 않고 계속 자기 자신을 가리키게 될 노드들도 있다. 그건 바로 루트노드이다.

루트 노드의 경우엔, 부모노드가 존재하지 않는다. 그렇기 때문에 이 배열에서 인덱스와 원소의 값이 동일하다면 그 노드는 루트 노드라고 가정할 것이다.

먼저, 입력은 아래와 같이 주어진다고 가정하도록 하겠다.

1 2
2 3
3 4

5 6
5 7

8 10
9 10

먼저 주어진 1, 2에 대해서 확인해보자.

현재 배열 내부에서는 모든 노드가 본인 자신을 부모 노드로 가리키고 있다.

1번과 2번도 이렇게 연결되지 않고 분리되어 있는 상태인 것이다.

하지만, 입력을 보면 1과 2는 연결되어 있다는 것을 확인할 수 있다.

그러므로 1과 2를 이어주어야 한다.

이려렇게 트리구조로 연결해주도록 하겠다.

(노드를 연결할 때, 인덱스가 더 작은 노드를 부모로 둘 것인가 더 큰 노드를 부모로 둘 것인가를 생각해야 하는데, 어느 방식으로 하든 결과는 동일하다. 하지만 하나의 기준을 선택했다면 모든 노드에 대해 동일한 기준을 적용해야 한다. 본인은 인덱스가 더 작은 노드를 부모 노드로 연결하도록 하였다.)

이렇게 연결하고 나니, 2번 노드의 부모 노드는 1번이 되었다.

그렇다면, 배열의 값을 갱신해야 한다.

이렇게 값을 갱신하였다.

이번엔, 두 번째 입력을 보자.

2와 3이 연결되어 있다고 한다.

그렇다면, 이건 아래 그림과 같이 연결해줄 수 있다.

이렇게 연결하면, 배열에서 3번째 원소의 값은 2가 될 것이다.

하지만, 이렇게 연결하게 되면 문제가 있다.

이렇게 연결하게 되면 3의 루트 노드를 찾기 위해 3->2->1 이렇게 선형으로 탐색해야 한다.

노드가 적을 땐 문제가 없을지 몰라도, 노드가 1억개정도 된다고 치면 1억번을 타고 올라가서 루트 노드를 구해야 하는 것이다. 이 과정이 굉장히 비효율적이다.

그렇기 때문에 위 그림과 같이 연결해줄 것이다.

이 알고리즘에서 중요한 것은 2 3 이라는 입력이 주어졌을 때, 2와 3이 직접적으로 연결된다는 것이 아니라 두 숫자가 같은 속성을 공유한다는 것이다.

즉, 연결 관계는 중요하지 않고 같은 집합에만 존재하면 된다는 것이다.

그러므로, 위와 같은 트리로 구현할 것이다.

배열에는 3이 속한 트리의 루트 노드를 저장해주도록 하겠다.

똑같은 과정으로 다른 노드에도 적용을 하게 되면 아래와 같이 트리를 구성할 수 있다.

또한, 배열의 값은 아래와 같을 것이다.

이제 집합이 완성되었으니, Union과정은 끝난 것이다.

하지만, 문제가 한가지 있다.

항상 위의 트리처럼 깊이가 2인 깔끔한 트리구조를 구현할 수 있다면 좋겠지만 그렇게 되지는 않는다.

2 3, 3 1의 입력을 받았다고 가정해보자.

먼저 2와 3을 연결해주면 아래 그림과 같을 것이다.

여기서 1을 연결해주면?

이런 형태의 트리가 되고 만다.

그런데 이는 위에서 말했던 것처럼 비효율적인 트리 형태이다.

즉 완벽하게 깊이가 2인 트리를 항상 유지하는 것은 아니라는 것이다.

이걸 최적화하는 기법도 있는 걸로 아는데, 그 부분은 본인도 조금 더 찾아봐야 할 듯 하다.

이제 이 알고리즘을 코드로 구현해보자.

코드 구현

std::vector<int> Parents;

먼저, 부모 노드를 저장할 배열을 선언하였다.

입력은 아래와 같이 들어온다고 가정하도록 하겠다.

10
8
1 2
2 3
3 4
5 6
5 7
8 10
9 10

첫 번째 입력은 노드의 개수를 의미한다.

두 번째 입력은 이후에 주어질 집합 정보의 수를 의미한다.

다음은 집합 정보가 주어진다.

1 2 가 주어진다면, 1과 2는 같은 집합에 속한다는 의미이다.

입력을 저장해보자.

int NumOfNode = 0;
int NumOfLink = 0;

std::cin >> NumOfNode >> NumOfLink;

std::vector<std::pair<int, int>> Links(NumOfLink, {0, 0});
for(int i = 0; i < NumOfLink; i++)
{
    std::cin >> NumOfLink[i].first;
    std::cin >> NumOfLink[i].second;
}

입력은 이렇게 하면 끝이다.

이후, parents 배열의 값을 인덱스로 초기화해주었다.

Parents.resize(NumOfNode + 1);
for (int i = 0; i <= NumOfNode; i++)
{
	Parents[i] = i;
}

이제, Root노드를 구하는 함수를 먼저 만들어보자.

int GetRootParents(int _Num)
{
    if (Parents[_Num] == _Num)
    {
        return _Num;
    }
    else
    {
        return GetRootParents(Parents[_Num]);
    }
}

먼저, 현재 배열의 값과 인덱스가 동일하다면 그 노드는 루트노드라고 정의하였다.

그러므로, 루트 노드를 반환할 때까지 배열을 타고 올라가서 루트 노드를 반환하도록 하였다.

void SetParents(const int& _Left, const int& _Right)
{
    int LeftParents = GetRootParents(_Left);
    int RightParents = GetRootParents(_Right); 
    
    if (LeftParents < RightParents)
    {
    	Parents[RightParents] = LeftParents;
    }
    else
    {
    	Parents[LeftParents] = RightParents;
    }
}

이 함수가 union역할을 하는 함수이다.

루트노드를 확인하며 부모 노드를 수정해주면 된다.

다음은 아래와 같이 반복문을 돌며 부모 노드를 설정해주면 끝이다.

for (int i = 0; i < NumOfLinkInfo; i++)
{
    SetParents(Links[i].first, Links[i].second);
}

입력값에 대한 부모 노드 배열의 값을 확인해보자.

이와 같이 정확하게 저장되어 있음을 알 수 있다.

하지만, 똑같은 연결 관계더라도 입력을 아래와 같이 바꾼다면 어떨까.

10
7
4 3
2 1
1 4
7 6
5 6
9 10
9 8

결과는 아래와 같다.

이를 시각화 해보자.

이런 모양이 된다.

즉, 입력에 따라 아주 비효율적인 트리구조를 구성할 수도 있게 되는 것이다.

이를 최적화하기 위해 사용하는 몇가지 기법이 더 있는 것으로 알고 있는데, 그 부분에 대해선 본인도 찾아봐야 할 듯 하다.

관련 게시글을 추후에 올려보도록 하겠다. 

이렇게, 좌표평면에서 d보다 가까운 거리에 있는 점들의 개수를 출하면 된다.

모든 점을 다 세는 것은 아니고,x와 y가 2의 k의 배수인 경우만 세주면 된다.

문제 풀이

임의의 좌표 (a, b)를 보자.

(a,b)가 주황색 원 위의 점이라고 가정해보겠다.

a 좌표에 대해, 위쪽으로 점을 찍을 때, 점의 최대 y좌표는 b와 같다.

왜냐하면, 원점으로부터 거리가 d를 초과하는 좌표엔 점을 찍을 수 없다.

원의 성질을 생각했을 때, 원점으로부터 (a,b)까지의 거리가 정확히 d가 된다.

그렇기 때문에, x가 a일 때 y값이 b를 초과하게 되면 원점으로부터의 거리는 d를 초과하게 된다.

그렇다면, a와 b의 값을 안다면 x가 a일 때 위쪽에 점을 몇 개 찍을 수 있을지 계산할 수 있을 것이다.

예를 들어 b가 6.5라고 가정한다면 위 그림처럼 x가 a일 때 위쪽으로 6개의 점을 찍을 수 있을 것이다.

b는 어떻게 구할 수 있을까?

간단하게 피타고라스의 정리를 이용해서 구할 수 있다.

좌표평면에 위와 같은 빨간 삼각형을 그려볼 수 있다.

이 삼각형의 밑변의 길이는 a이고, 빗변의 길이는 d이다.

피타고라스의 정리를 이용하면, b^2 = d^2 - a^2 이다.

a와 d를 안다면, b를 쉽게 구할 수 있다.

a는 x좌표의 값이기 때문에

반복문을 통해 0~d까지 이동하며 위에 찍을 수 있는 점의 수를 계산한 뒤 모두 더하면 답을 도출할 수 있다.

하지만, 문제에는 조건이 하나 더 있다.

x와 y는 반드시 k의 배수여야 한다는 것이다.

이를 해결하는 방법은 간단하다.

먼저, x는 반복문에서 움직일 때 1씩 움직이는 것이 아니라 k씩 움직이면 된다.

어차피, x가 k의 배수가 아니면 점을 찍지 못하기 때문에 k씩 더해가며 해당 좌표에서만 점의 개수를 구하면 된다.

y에 대해서는 어떻게 해결할까?

k를 고려하지 않았을 때, 위에 찍을 수 있던 점의 개수를 k로 나누어 준 뒤 1을 더하면 된다.

k가 4이고, 위에 찍을 수 있는 점이 10개라고 가정해보자.

이 때, 10을 4로 나누면 몫은 2가 나온다. y값이 4일때, 8일 때 찍을 수 있는 것이다.

하지만, 이 문제의 경우 y값이 0인 경우에도 점을 찍을 수 있다.

그렇기 때문에 1을 꼭 더해주어야 한다.

풀이 코드

int Interval = k;
int Distance = d;

먼저 가독성을 위해, 변수의 이름을 새로 정의하였다.

long long DotCount = 0;
for (int i = 0; i <= Distance; i += Interval)
{
    long long SqrtValue = sqrt(pow(Distance, 2) - pow(i, 2)) / k;
    SqrtValue++;

    DotCount += SqrtValue;
}

return DotCount;

이후, 위에서 말한것 그대로 코드로 구현하면 된다.

i는 0부터 Distance까지 이동하며 점의 개수를 셀것이다.

다만, i가 Interval의 배수라는 조건이 있기 때문에 i를 1씩 증가시키는게 아니라 Interval씩 증가시켰다.

이후, 피타고라스의 정리를 이용하여, 위로 찍을 수 있는 점의 최대 개수를 구한 뒤 이를 k로 나눠주었다.

그 다음 1을 더해줌으로서 y좌표가 0인 점도 함께 세주었다.

그렇게 나온 값을  DotCount에 지속적으로 더해주면 끝이다.

이 문제는 알고리즘에 관한 문제라기보단 완전한 수학문제이다.

이런 유형의 문제가 코딩 테스트에 나올까 싶지만, 그래도 열심히 풀어보며 사고력을 꾸준히 높이는 것은 중요하다고 생각한다.

위 그림처럼, 철수는 10과 20의 카드를 지니고 있고 영희는 5와 17의 카드를 지니고 있다고 가정해보자.

철수의 모든 카드는 1, 2, 5, 10 으로 나눌 수 있다.

영희의 모든 카드는 1, 5, 17로 나눌 수 있다.

이 때, 철수의 모든 카드는 나눌 수 있으면셔, 영희의 카드는 단 1개도 나눌 수 없는 수를 구하면 된다.

철수의 모든 카드를 나눌 수 있는 숫자중, 2와 10은 영희의 카드를 단 1개도 나눌 수 없다.

이 때, 2와 10중 더 큰 값인 10이 정답이 된다.

문제 풀이

이 문제는 최대공약수를 이용하면 간단하게 풀 수 있다.

철수가 가진 모든 숫자 카드를 나눌 수 있는 수는 쉽게 말해서 공약수이다.

어떤 정수 A를 정수 B로 나눌 수 있다면, B를 A의 약수라고 칭한다.

어떤 정수 A와 B를 C로 나눌 수 있다면, C는 A와 B의 공약수라고 칭한다. (공통된 약수)

이러한 정의를 따져보면, 모든 숫자 카드를 하나의 숫자로 나눌 수 있다면, 그 숫자는 모든 숫자 카드의 공약수인 것이다.

문제는 그러한 숫자들 중에서 가장 큰 값을 구하는 문제이기 때문에 최대 공약수를 구하면 된다.

최대 공약수는 어떻게 구할까?

유클리드 호제법이라는 알고리즘을 사용하면 된다.

모른다면, 아래 링크를 참고하도록 하자.

알고리즘 - 유클리드 호제법 (두 수의 최대 공약수 구하기) (tistory.com)

이제 1명의 카드를 모두 나눌 수 있는 숫자는 구했으니, 그 숫자가 다른 1명의 카드를 나눌 수 있는가를 검사하면 끝이다.

간단하게, 반복문을 돌며 나누기 연산 혹은 나머지 연산을 하면 끝이다.

1. 철수의 모든 카드는 나눌 수 있으나 영희의 카드는 단 1개도 나눌 수 없는 숫자

2. 영희의 모든 카드는 나눌 수 있으나 철수의 카드는 단 1개도 나눌 수 없는 숫자

두 경우의 숫자를 구한 뒤, 둘 중 더 큰 값을 return하면 된다.

풀이 코드

int Answer_1 = 0;
int Answer_2 = 0;

먼저, 2개의 int형 변수를 선언하였다.

문제에선 2개의 경우가 나온다.

1. 철수의 모든 카드는 나눌 수 있으나 영희의 카드는 단 1개도 나눌 수 없는 숫자

2. 영희의 모든 카드는 나눌 수 있으나 철수의 카드는 단 1개도 나눌 수 없는 숫자

두 경우에 대한 숫자를 구한 뒤, 둘 중 최대값으로 반환할 것이기 때문에 2개의 변수를 선언한 것이다.

int GetGCD(int _A, int _B)
{
    int Remain = 0;
    while (_B > 0)
    {
        Remain = _A % _B;
        _A = _B;
        _B = Remain;
    }

    return _A;
}

위는 최대 공약수를 구하는 유클리드 호제법에 대한 코드이다.

int GCD_A = arrayA[0];
for (int i = 1; i < arrayA.size(); i++)
{
    GCD_A = GetGCD(GCD_A, arrayA[i]);
}

유클리드 호제법을 이용하여, 철수가 가진 모든 숫자의 공약수를 구해주었다.

(위와 같이 반복문을 이용하면 모든 원소에 대한 최대공약수를 구할 수 있다.)

Answer_1 = GCD_A;
for (int i = 0; i < arrayB.size(); i++)
{
    int Remain = arrayB[i] % GCD_A;

    if (Remain == 0)
    {
        Answer_1 = 0;
        break;
    }
}

이후, Answer_1엔 일단 최대 공약수를 넣어 주었다.

이 값으로 영희가 가진 숫자중 나누어지는 숫자가 단 1개도 없다면, 이 값을 답으로 픽스하면 되고

1개라도 나누어지는 숫자가 있다면, 값을 0으로 바꿔준 뒤 break해주면 된다.

{
    int GCD_B = arrayB[0];
    for (int i = 1; i < arrayB.size(); i++)
    {
        GCD_B = GetGCD(GCD_B, arrayB[i]);
    }

    Answer_2 = GCD_B;
    for (int i = 0; i < arrayA.size(); i++)
    {
        int Remain = arrayA[i] % GCD_B;

        if (Remain == 0)
        {
            Answer_2 = 0;
            break;
        }
    }
}

Answer_2는 영희와 철수만 바뀌었을 뿐 완전히 동일하게 계산하였다.

return std::max(Answer_1, Answer_2);

마지막으로 두 값중 최대값을 리턴하면 끝이다.

유클리드 호제법이란, 두 숫자가 주어졌을 때 최대 공약수를 간단하게 구하는 알고리즘이다.

일반적으로 두 수의 최대공약수를 구하기 위해선, 두 수를 1부터 차례대로 나누어 가며 두 숫자 모두 나머지가 0이 나오는 숫자를 구해야 한다.

숫자의 값이 N, M 이고, N < M 이라고 했을 때, 시간복잡도는 O(N)이 된다.

반면, 유클리드 호제법을 사용하게 되면 O(logN)의 시간 복잡도로 최대 공약수를 구할 수 있다.

유클리드 호제법

그렇다면, 유클리드 호제법은 어떻게 사용하는 것일까?

먼저 코드를 보자.

int GetGCD(int _A, int _B)
{
    int Remain = 0;
    
    while(_B > 0)
    {
    	Remain = A % B;
        A = B;
        B = Remain;
    }
    
    return A;
}

위와 같이 매우 짧은 코드이다.

A를 B로 나눈 나머지가 0이 될 때까지 반복문을 돌리면 된다.

R이 A % B이고, GCD(A, B)가 A와 B의 최대 공약수라고 했을 때,

GCD(A, B)  = GCD(B, R) 이 성립한다.

R1 = B % R이라고 한다면,

GCD(B, R) = GCD(R, R1)또한 성립하는 것이다.

반복문을 계속 실행하여, GCD(N, 0)이 될 때 까지 반복한다.

GCD(N,0)의 값은 N이므로, GCD(A,B) = N 이라는 결론이 난다.

즉, 위의 코드에서 보면 Remain이 0이 될 때의 A가 GCD가 되는 것이다.

아마, 왜 이렇게 되는지는 수학적 증명과정을 거치지 않으면 이해하기 힘들 것이다.

아래는 이해를 돕기 위한 수학적 증명 과정이다.

다만, 증명 과정을 꼭 알아야하는 것은 아니다. 오히려 이해를 더 어렵게 만들 수도 있다.

그러니, 관심이 없다면 증명과정은 그냥 스킵하고 위의 공식만 가져다 사용해도 사실 문제는 없다.

수학적 증명

이 유클리드 호제법을 사용하여 최소 공배수(LCM)또한 쉽게 구할 수 있다.

이건 증명과정이 어렵지 않으므로 간단히 참고하도록 해보자.

A와 B의 최소 공배수를 L이라고 해보자.

L은 A로도 나누어지고, B로도 나누어지는 수 중에서 최소인 수이다.

즉 A = aG, B = bG라고 했을 때 L = a * b * G; 라고 할 수 있다. (a, b는 서로소이며 G는 A와 B의 최대 공약수)

A * B = a * b * G * G

A * B / G = a * b * G = L

즉, L 은 A와 B의 곱을 A와 B의 최대 공약수로 나눈 수이다.

int GetLCM(int _A, int _B)
{
    int GCD = GetGCD(_A, _B);
    return (_A * _B) / GCD;
}

이렇게 사용하면 된다. 

매우 간단하다.

최소 공배수와 최대 공약수를 이용하여 푸는 문제가 생각보다 자주 나온다.

유클리드 호제법을 아는 것과 모르는 것은 문제 풀이에 생각보다 큰 영향을 미친다.

어려운 알고리즘이 아닌 만큼 반드시 숙지하도록 하자.

위 그림과 같이 두개의 선분이 주어졌을 때, 왼쪽처럼 두 선분이 만나고 있다면 1을 출력하고

오른쪽처럼 만나지 않는다면 0을 출력하면 되는 문제이다.

문제 풀이

이 문제는 CCW알고리즘을 활용하면 간단하게 풀 수 있는 문제이다.

CCW알고리즘을 모른다면, CCW알고리즘을 먼저 알아보고 오자.

알고리즘 - CCW (세 점의 방향 판별하기) (tistory.com) 해당 링크는 필자가 작성한 CCW알고리즘 설명이다.

먼저, 처음에 주어지는 4점의 위치관계를 그림으로 보자.

입력 받은 순서에 따라 4점을 A,B,C,D 라고 했을 때, 두 선분이 만난다면 위와 같은 위치관계를 가지게 될 것이다.

(물론, 수직이 아니라 다른 형태로 만날 수도 있지만 크게 봤을 때 위치관계가 위와 유사할 것이다.)

이 때, 두 선분이 어떤 모양으로 만나든 반드시 성립해야 하는 조건이 2가지가 있다.

1. 점C와 점 D는 선분 AB를 기준으로 서로 반대쪽에 위치해야 한다.

위의 그림처럼, 점 CD가 모두 AB를 기준으로 왼쪽에 위치하거나 오른쪽에 위치한다면 두 선분은 만난다고 할 수 없을 것이다.

(정확하게는 왼쪽 오른쪽이라기보다는, 직선 AB에 의해 분할되는 두 영역이 있다면, C와 D는 서로 같은 영역에 위치해서는 안된다.)

즉, ABC 세점의 위치관계가 반시계 방향이라면, ABD는 시계방향이어야 하고, 반대로 ABC가 시계방향이라면 ABD는 반시계 방향이어야 한다.

해당 그림처럼, ABC와 ABD는 서로 반대 방향으로 위치해야 한다.

CCW를 이용하여, ABC와 ABD의 위치관계를 판별한 뒤 서로 다르다면 두 선분이 만난다고 할 수 있을 것 같다.

하지만, 1가지 예외가 있다.

이런 경우를 보자.

분명, ABC과 ABD는 서로 반대의 위치관계를 가지고 있지만 두 선분은 만나지 않는다.

그렇기 때문에, 고려해야 하는 것이 한가지 더 생긴다.

이렇게, CDB와 CDA의 위치관계로 함께 고려하는 것이다.

4점의 위치관계를 모두 고려하게 되면 아래와 같은 명제를 세울 수 있다.

(CBD와 CBA의 위치관계가 서로 반대이다) && (ABC와 ABD의 위치관계가 서로 반대이다)

== 두 선분이 만난다.

풀이 코드

struct Point
{
	long long X = 0;
	long long Y = 0;
};

struct Line
{
	Point Start;
	Point End;
};

먼저, 점의 위치 X,Y를 담을 Point 구조체를 선언하였고, 선분의 시작과 끝이 되는 두 점을 담을 Line구조체를 선언하였다.

Line Line_1;
Line Line_2;

std::cin >> Line_1.Start.X >> Line_1.Start.Y;
std::cin >> Line_1.End.X >> Line_1.End .Y;

std::cin >> Line_2.Start.X >> Line_2.Start.Y;
std::cin >> Line_2.End.X >> Line_2.End.Y;

이후, 입력값을 저장해주자.

다음은, CCW알고리즘을 이용하여 시계방향인지 반시계방향인지 판별하는 함수를 만들어보자.

bool isClockWise(Point _First, Point _Second, Point _Third)
{
	Point Vector_1 = { _Second.X - _First.X, _Second.Y - _First.Y };
	Point Vector_2 = { _Third.X - _Second.X, _Third.Y - _Second.Y };

	long long CrossZ = { Vector_1.X * Vector_2.Y - Vector_1.Y * Vector_2.X };

	return CrossZ < 0;
}

정말 간단하다.

먼저 세 점을 입력받는다.

세 점을 외적하여 나온 벡터의 Z값이 양수인지 음수인지만 검사하면 되기 때문에 Z값에 대해서만 외적을 진행하고,

그 값이 양수인지 음수인지에 따라 bool값을 반환하였다.

해당 함수는 시계방향인가? 라는 이름으로 만들었기 때문에 Z값이 음수라면 true를 반환하도록 하였다.

그 다음은 위에서 그림으로 보았던 4가지의 위치관계를 구해서 확인해보면 된다.

bool isClockWise_1 = isClockWise(Line_1.Start, Line_1.End, Line_2.Start);
bool isClockWise_2 = isClockWise(Line_1.Start, Line_1.End, Line_2.End);

if (isClockWise_1 == isClockWise_2)
{
    std::cout << 0;
    return 0;
}

bool isClockWise_3 = isClockWise(Line_2.Start, Line_2.End, Line_1.Start);
bool isClockWise_4 = isClockWise(Line_2.Start, Line_2.End, Line_1.End);

if (isClockWise_3 == isClockWise_4)
{
    std::cout << 0;
    return 0;
}

std::cout << 1;

return 0;

먼저, 한 선분의 Start, End를 기준으로 다른 선분의 두 점에 대해 위치관계가 반대인가를 검사하였다.

두 위치관계가 만약 동일하다면, 다른 검사를 할 필요도 없이 두 선분은 만나지 않기 때문에 0을 출력하고 함수를 종료해주었다.

여기서 함수가 끝나지 않았다면, 다른 선분을 기준으로 다시 위치관계를 검사해준다.

여기서도 마찬가지로 위치관계가 동일하게 나왔다면 0을 출력하고 함수를 종료해주었다.

만약, 여기서 함수가 종료되지 않았다면 1을 출력해주면 된다.

외적을 활용하여 간단하게 풀 수 있는 문제였다.

본인은 이 문제에서 정말 여러 번 틀렸는데, 이유는 아주 단순한 이유였다.

struct Point
{
	long long X = 0;
	long long Y = 0;
};

이렇게, 위치를 저장하는 값은 long long 이어야 한다....

본인은 int로 했다가 계속 틀려서 머리가 터질 뻔 했다.

다들 본인처럼 실수하지 말고 문제를 풀 땐 자료형의 범위 주어진 입력값의 범위를 잘 비교해보자.

CCW 란 Counter Clock Wise 의 준말이다.

Counter Clock Wise 란 반시계 방향을 의미한다.

CCW 알고리즘은 세 점의 좌표가 주어졌을 때, 반시계 방향으로 위치하는가를 판별하는 알고리즘이다.

위의 두 그림에서 A->B->C의 방향을 보자.

첫 번째 그림은 반시계 방향으로 세 점이 위치하고 있고, 두 번째 그림은 시계 방향으로 세 점이 위치하고 있다.

이렇게, 세 점이 순서대로 주어졌을 때, 반시계 방향으로 위치하는지 시계 방향으로 위치하는지를 판별하는 알고리즘이 CCW이다.

CCW 알고리즘

CCW알고리즘은 기본적으로 벡터의 외적을 이용한 알고리즘이다.

이 알고리즘을 알기 위해선 외적에 대한 이해가 있어야 하며, 왼손 좌표계와 오른손 좌표계에 대한 이해가 있어야 한다.

모른다면, 찾아보고 나서 다시 알고리즘을 보는 것을 추천한다.

이 알고리즘은 상술했듯이 벡터의 외적을 기반으로 작동한다.

허나, 벡터의 외적은 해당 좌표계가 오른손 좌표계인지 왼손 좌표계인지에 따라 다른 결과를 나타낸다.

(수치는 같지만, 적용되는 방향이 다르다.)

만약 DirectX나 unreal Engine같은 환경에서 이 알고리즘을 사용하겠다면 왼손 좌표계를 기준으로 해야할 것이다.

수학에서 일반적인 좌표계는 오른손 좌표계이기 때문에 해당 게시글에선 오른손 좌표계를 기준으로 설명할 것이다.

일반적인 오른손 좌표계는 위와 같이 축이 설정되어 있다.

이 공간 안에, 그림에 보이는 것과 같이 벡터 1과 벡터 2가 존재한다고 해보자.

두 선분의 z값은 0이라고 가정하겠다.

이 떄, 두 선분을 외적하면 XY평면과 수직이며, z축과 평행한 벡터가 결과로 나오게 될 것이다.

이 때, 벡터 1과 벡터 2의 위치관계를 보자.

그림과 같이 위치한다면, 오른손 법칙에 의해, (벡터 1) X (벡터 2) 의 결과는 z축의 양의 방향으로 뻗어나가는 벡터일 것이다.

반면, 이 그림처럼 벡터 1과 벡터 2가 위치한다면, (벡터 1) X (벡터 2)의 결과는 Z축의 음의 방향으로 뻗어나가는 벡터가 될 것이다.

즉, 두 벡터의 위치관계에 따라 외적한 벡터의 Z값이 양수인지 음수인지 달라지는 것이다.

그럼 다시 이 그림을 보자.

세 점이 반시계 방향으로 위치할 때, 점을 제거하고 벡터만을 보게 되면 위와 같이 정리할 수 있다.

2차원 평면에 해당 그림과 같이 위치했을 때, 파란색 벡터와 빨간색 벡터를 외적하면?

오른손 법칙에 의해, Z축의 양의 방향으로 뻗어나가는 벡터가 나온다.

즉, (파란색 벡터 X 빨간색 벡터) 를 통해 나온 벡터의 Z값이 양수라면 세 점이 반시계 방향으로 위치한다고 생각할 수 있다.

이번엔 시계 방향으로 있는 상황을 보자.

그림과 같이 벡터의 관계를 정리할 수 있다.

이 때, 파란색 벡터와 빨간색 벡터를 외적하게 되면, Z축의 음의 방향으로 뻗어나가는 벡터가 결과로 나오게 된다.

즉, (파란색 벡터 X 빨간색 벡터) 를 통해 나온 벡터의 Z값이 음수라면 세 점이 시계 방향으로 위치한다고 생각할 수 있다.

이와 같이, 세 점의 좌표를 기준으로 벡터를 구한 뒤 벡터를 외적하게 되면 세 점이 시계방향으로 있는지 반시계 방향으로 있는지를 판별할 수 있다.

백준 17386- 선분 교차 1 (C++) (tistory.com)

위의 링크는 이 알고리즘을 적용하여 풀어볼 수 있는 문제이다.

문제를 먼저 풀어보고 나서 게시글을 참고하면 도움이 될 것 같다.