ConvexHull2 KMP DP 트리 그래프 기하학 최근 푼 문제 1701 Cubeditor KMP idx(0~N-1)부터 N까지의 부분문자열에 대해 Pi를 구한다. idx에 대하여 최대 Pi값 - idx = 두 번 이상 나오는 가장 긴 부분문자열의 길이 * Pi를 구하는 시작점의 인덱스가 0이 아님에 주의해서 풀면 됨 16900 이름 정하기 KMP 주어진 문자열 S가 최소 K번 부분문자열로 등장하는 새로운 문자열 길이의 최솟값을 구한다. Pi를 구해 문자열 S에서 K-1번 반복해줄 부분 문자열을 구한다. 아래는 예시 S ada 3 pi 001 => (3-2)+2*3 S abc 2 pi 000 => (3-3)+3*2 S rr 5 pi 01 => (2-1)+1*5 S abcabcabca 3 pi 0001231234 => (10-3)+3*3 1509 팰린드롬 분할 DP 주.. 2021. 4. 16. Convex Hull과 CCW * Convex Hull: 볼록 껍질 * CCW: counter clockwise, 시계 반대 방향 외적을 이용하는 기하학 문제에서 쓰인다. 주어진 점을 모두 포함하는 볼록 다각형의 꼭짓점을 찾아야 한다. 1. 볼록 껍질의 한 꼭짓점을 찾는다. y좌표가 가장 크거나 가장 작은 점, x좌표가 가장 크거나 가장 작은 점 중 아무거나 고르면 된다. 해당 점을 모두 포함하는 MBR(Minimal Bounding Rectangle)과 볼록 껍질이 무조건 접해야하기 때문 이때는 간단한 비교 함수를 사용해 점을 정렬하고 첫 번째 원소를 기준점으로 잡는다. 2. 기준점을 기준으로 다른 점을 시계방향으로 정렬한다. 이때 외적이 쓰인다. 벡터 OA와 OB의 외적 < 0 ⇒ O를 기준으로 A, B가 시계방향으로 존재한다. .. 2021. 4. 9. 이전 1 다음
