Junnnho

BOJ : https://www.acmicpc.net/problem/1074

문제를 다시 풀어보았다.

분할정복, 말그대로 분할을 이용한 문제인 것 같다.

2*2 형태 부분만 찾으면 되기 때문에

분할은 다음과 같이 했다.

왼쪽상단을 fx, fy 라고하고 오른쪽하단을 ly, lx 라고가정

str 은 현재 왼쪽상단에 오게 될 숫자이고 num은 현재 오른쪽하단에 오게 될 숫자이다.

이때 4등분을 하게 되면 fx,fy,lx,ly 에 대한 위치를 분할해서 줄 수 잇을 것이며,

str, num 또한 위치에 맞게 분할해줄 수 있다.

2번이나 틀린 문제인데.. long long 을 사용하지 않아서 틀렸다.

2^15 의 좌표만 생각하고 int로만 했다가 WA을 받았다

숫자는 2^15 * 2^15 를 표현해야하니 longlong을 사용하자

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

예를 들어 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 이라고 말했었다.

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

여기는 문제를 풀면서 기본으로 알고 있어야 하는 공식들을 정리한다.

-- 방정식

(중심이 (x.y)기준 (a.b) 이고 반지름이 r인 원의 방정식)

(x-a)^2 + (y-b)^2 = r^2

(기울기가 m이고 (x.y)기준 (a.b)를 지나가는 직선의 방정식)

y = m(x-a)+b

(두점 (x1.y1) (x2.y2) 를 지나가는 직선의 방정식)

y = ((y2-y1)/(x2-x1))*(x-x1) + y1

(2차 방정식 ax^2+bx+c = 0 의 근 x)

x = (B^2 (+-) sqrt(4*a*c)) / (2*a)

(3차 방정식 이상 => 미분을 통하여 기울기가 0이 되는 극점을 찾는 재귀를 반복)

(2개의 좌표를 기준으로 3등분하는 내분점 공식)

왼쪽좌표 : (x1,y1) => left // 오른쪽좌표 : (x2,y2) => right 로 생각할 때

3등분의 왼쪽좌표 : (left*2+right)/3

3등분의 오른쪽좌표 : (left+2*right)/3

세점이 주어졌을 때 삼각형의 넓이

기하 문제중 볼록껍질(convex hull) 을 다룰 때 좌표가 주어지면 

이를 선분으로 처리하는 방법을 정리해두자

보통 문제에서는 볼록껍질의 좌표를 시계방향/시계반대방향으로 주어진다.

볼록껍질에서 좌표가 주어지면 이를 선분처리해서 사용할 줄 알아야한다.

한 선분은 두 점으로 이루어져있으니 인접한 좌표를 기준으로 처리해야한다.

시계반대방향을 기준으로 정리해본다

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