Junnnho

문제마다 다각형 내부점이 되는 기준이 다 다르다

지금 정리하는 기준은 다각형의 선분위에 있는 점 또한 내부점으로 판단한다고 가정한다

주어진 점이 다각형의 내부점이 되는지 안되는지 파악하기 전에 

이 다각형을 시계방향이든 반시계방향이든 정렬해서 선분으로 사용할 수 있도록 만들어 놓아야 한다

좌표정렬 : https://junho0956.tistory.com/285?category=879042

좌표를 정렬했으니 내부점 판단에 대한 정리 ㄱㄱ

베이스는 다음과 같다

임의의 점을 기준으로 반직선을 그었을 떄 다각형의 선분과 교차하는 지점이 발생하게 되는데 이 지점을 횟수 저장하자

모든 다각형의 선분에 대한 탐색이 끝났을 때 교차횟수가 홀수이면 내부점, 짝수이면 외부점으로 판단할 수 있다

근데 단순히 저 방식대로만 하면 반례가 많이 생긴다

그래서 좀더 정확하게 해결하는 방법을 풀이해보자

기준점 => (px,py)

첫번째 방법 => ccw를 이용한 내부점 판단

i번째 점과 (i+1)%N점을 기준으로 반직선이 교차하는지 확인

다음과 같은 코드로 교차횟수를 증가할지 말지 판단할 수 있다

P[i].y < py && P[(i + 1) % N].y >= py && ccw(P[i], P[(i+1)%N], 기준점) > 0 
P[(i + 1) % N].y < py && P[i].y >= py && ccw(P[(i+1)%N], P[i], 기준점) > 0

ccw를 하기전 코드는 단순히 교차를 하는지만 판단하는 부분이고,

ccw의 의미는 선분을 기준으로 기준점이 어디에 있는지 판단하는 부분이 된다

ccw값이 >0 이 되는 즉 기준점이 왼쪽일때 교차횟수를 증가시켜준다

두번째 방법

ccw를 사용하지 않고 단순히 직선의방정식 y = (y2-y1)/(x2-x1)*(x-x1)+y1 으로도 해결할 수 있다

convex hull을 다루는 문제에서 

좌표를 줄 때 시작부터 cw/ccw 방향으로 좌표를 주는 경우가 있다면

랜덤하게 좌표를 주는 경우 원하는 조건에 맞게 정렬하는 방법을 정리해보자

* 볼록껍질의 선분을 다루기 위해서 그 선분의 점이 되는 좌표들을 미리 정렬해야함

반시계 방향으로 정렬한다고 가정하고

기준점(보통 기준점으로 x,y의 끝값에 있는 좌표를 사용, 가장 바깥쪽에 있는 좌표면 충분)을 먼저 잡고

그 기준점을 기준으로 다른 모든 점들에 대한 각도(tan)를 구함

구한 각도를 기준으로 정렬(이때 반시계방향으로 좌표가 정렬됨)

point& a 에서 tan값은 a.q / a.p 가 되는데 위와같이 정렬하는 이유는

/ => 나눗셈을 이용하게 되면 값이 0이 되는 부분(x의 차가 없거나,y의 차가 없거나)이

분모에 올 경우 정확한 답을 찾을 수 없기 때문

tan을 위와 다르게도 정렬할 수 있다. 어쨋든 각도를 이용해서 정렬만 하면 된다

hull 의 내부점이 될지 선분의 기준점이 될지는 ccw으로 판단한다(당장 반시계방향의 좌표를 구하므로)

스택과 ccw을 이용해서 convex hull을 찾는다

첫번째 인자는 기준점, 두번쨰 인자는 반시계방향의 첫번째 좌표, 세번째 인자는 반시계방향의 두번째 좌표

3번째 인자에 대한 ccw가 >0 이 되면 왼쪽에 위치하는 점이므로 볼록껍질의 좌표가 될 수 있는 부분,

그 이외는 좌표가 될 수 없는 부분이 된다

ccw 가 >0 이면 두번째인자를 스택에 푸쉬(그래야 다음 확인때 첫번째로 사용가능함), 세번째 인자 역시 스택에 푸쉬

단, 비교해야할 선분(1,2번째인자로 만든 선분)이 필요하므로 최소한 스택의 값은 2이상 유지되야한다

이렇게 마지막 좌표까지 탐색하면 현재 스택에 남아있는 좌표가 반시계방향에 대한 좌표가 된다

비트마스킹의 개념을 알아두면 

값 하나에 여러가지 상태를 표시하는 기법을 알 수 있게 된다.

비트마스킹을 이용한 대표적인 문제가 외판원 순회(TSP) 인 것 같다.

예를 들어 집이 4개가 있고, 집 번호를 0~3, 이 집들을 방문한 정보들을 알고 싶다고 할 때,

우리는 비트마스킹 즉, 비트라는 값을 이용해서 하나의 값으로 여러 상태를 표현할 수 있다.

우선 집이 4개 => 4개의 집에 대한 정보를 표현하기 위한 크기가 필요하다.

이를 4비트(2^4 = 16(0~15))로 표현해보자

이 때, 4비트에 대한 비트 표현법은 1<<4 (2^4) 가 된다.

만약 0번 집만 방문했다면 0001 (실제로는 1이 저장된다)

만약 1번 집만 방문했다면 0010 (실제로는 2가 저장된다)

만약 1, 3번 집만 방문했다면 1010 (실제로는 2^1+2^3 => 10이 저장된다)

여기서 비트1은 방문을 했고 비트0은 방문을 하지 않았음을 나타낸다.

비트마스킹 정보를 배열에 저장한다고 가정하면 array[1<<4] 와 같이 선언하여 사용하면 된다.

----------- 연산 -------------

어떤식으로 사용되는지 알았다면, 이용할 수 있는 연산이 뭐가 있는지 알아보자

기본적인 비트연산은 알고 있을 것이다.

&연산의 의미는 두 비트값 모두 1이면 1, 아니면 0을 반환하고

| 연산의 의미는 둘중 한 값이라도 1이면 1, 아니면 0을 반환하고

~연산의 의미는 모든비트를 뒤집는 연산 0->1, 1->0 을 반환하게 된다.

비트의 크기는 N, 현재 비트값을 current 라고 할 때

. 모든 비트가 1인지 확인해보고 싶다 => current & (1<<N)-1 

. 모든 비트가 0인지 확인해보고 싶다 => current & 0

. K번째 비트가 1인지 0인지 확인해보고 싶다 => current & (1<<K)

K번째 비트만 둔채로 나머지 비트는 다 버려야 된다

이때 1<<K 의 의미는 K번째 비트만 1 처리하고 나머지 비트는 0 처리한다는 뜻이다.

(만약 K가 4라면 1<<4 => 16이 되고, 이를 비트로 나타내면 10000 (= 16) 가 된다는 뜻이다.

N이 4보다 큰 값이라고 할 때 좀더 정확히는 ...0000...0010000 이라는 의미가 된다)

. K번째 비트를 1로 만들고 싶다 => current | (1<<K)

위의 설명을 이해했다면 | (OR) 연산자를 사용해야 함을 알 수 있을 것이다.

K번째 비트를 1로 만들고 싶다면 K번째 비트를 1로 만들고 나머지 비트는 current 값 그대로 가져오면 된다.

. K번째 비트를 0으로 만들고 싶다 => current & ~(1<<K)

K번째 비트를 1로 만든 후, NOT연산 ~을 이용하여 뒤집어버리면

K번째 비트만 0이 되고 나머지는 1이 된다.

& 연산을 하면 K번째 비트는 강제로 0이 될 것이고, 나머지 비트들은 원래 값을 가지게 된다.

소인수분해의 뜻은 임의의 수(소수 또는 합성수)를 소수의 곱으로 표현한 것을 말한다

예를 들어 28을 소인수분해하면 2*2*7 이 된다.

소인수분해나 소수를 관련하여 문제를 풀 때는

항상 N이라는 수를 p*q 로 나타낼 때

p가 sqrt(N)보다 크거나 같다면 q는 sqrt(N)보다 작거나 같다는 것을 이용해야 한다.

소인수분해를 가장 간단히 하는 방법은

N을 기준으로 2부터 sqrt(N)까지 가능한 수를 모두 나누어보는 것이고

이 때의 시간복잡도는 sqrt(N)이 된다

만약 폐구간[a,b] 에 대한 범위를 다루어야 한다면,

에라토스테네스의 체를 이용하여 좀 더 쉽게 해결할 수 있다.

에라토스테네스의 체를 구현하되, 소인수분해를 적용하려면 다음과 같다

factor[i]의 의미는 "i라는 수를 만들기 위해 곱해야할 최소의 수" 를 뜻한다.

factor[2] 는 2가 될 것이고, factor[12] 역시 2가 될 것이고

2의 배수가 아닌 3의 배수만 생각해봐도 factor[9] 는 3이 됨을 뜻한다.

32줄의 조건문을 확인해주는 경우는

예를 들어 6을 생각했을 때

2가 먼저 factor[6] 에 담기게 된다.

그 후 3에 대한 반복문을 돌 때 factor[6]을 거치기 때문에 조건처리를 안해주면

factor[6] = 3 으로 수정되면서 6을 만들기 위한 최소곱의 값이 2가 아닌 3이 되기 때문이다.

위에서 28이라는 수를 소인수분해하면 2 2 7 이라고 말했었다.

코드가 제대로 구현되었는지 확인해보았다.