11번째 수업

이 글들은 백준 온라인 저지의 백준님이 2020년 1~2월에 강의하시는 강의 내용을 듣고 복습한 뒤 간단하게 정리하여 올리는 글이다. 이 글을 쓰는 이유는 그날그날 들은 강의 내용을 복습하고 정리함으로써 배운 것을 확실히 머리에 남김과 동시에 나중에 다시 상기시킬 때 도움이 되도록 하기 위함이다.

---

○ 쿼리문제

△ 팰린드롬?

선처리: preprocessing

다이나믹에서는 미리 답을 다 확인해놓고 O(N^2)

답을 그냥 0 또는 1로 출력 O(1)

쿼리는 M개, 1번씩 다 돔.

총 O(N^2+M)의 시간복잡도

 

△ 1,2,3,더하기 4

구성이 같은데 순서가 다르면 같은 것으로 친다.

예) 1+1+2 = 1+2+1 = 2+1+1

각각의 그룹마다 대표를 하나 결정한다. 순서가 오름차순인 것만 대표로 친다고 하면, 오름차순인 것은 하나씩이므로 대표로 하나씩 선정된다.

or

1만 써서 수를 만들고, 그 다음에 2만 써서 수를 만들고, 이런식으로 수를 증가시키며 만들어나간다.

1 뒤에 반드시 2가 오고 그 뒤에 3이 오게 된다.

1,2,3더하기 4

 

△ 파일 합치기

각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다.

소설의 여러장들이 연속이 되도록 파일을 합쳐나가고, 합칠 때 필요한 비용을 두 파일 크기의 합이라 할때, 완성본을 만드는데  필요한 비용의 합을 구하는 문제.

브루트포스로 풀면 (N-1)x(N-2)x....x1 = (N-1)!

N이 500 제한이라 너무 커서 풀 수 없다.

 

A1 / A2A3A4A5 : (1~1) (2~5)

A1A2 / A3A4A5 : (1~2) (3~5)

A1A2A3 / A4A5 : (1~3) (4~5)

A1A2A3A4 / A5 : (1~4) (5~5)

(i~j) = i부터 j까지 합침 =  N^2 = 25만

(i~k) (k+1~j) i≤k≤j

D[i][j] = i부터 j까지 합침

           = D[i][k] + D[k+1][j] + (i~j)파일 크기 합

시간복잡도는 N^3. i~j 구하는게 N^2, i~j에서 k구하는게 N

 

△ 기타리스트

i번 곡을 연주하기 전에 볼륨을 V[i]만큼 바꿔야한다. 이때 마지막으로 연주할 수 있는 볼륨의 최댓값.

N번 곡이 있으면 2^N가지 경우가 나온다. 2^100은 너무 큰수라 브루트포스로 푸는건 힘들다.

but, 가능한 볼륨의 범위가 0~M으로 경우가 줄어든다.

비둘기집의 원리 = 비둘기 집이 N개가 있고 비둘기가 N+1이 있으면 적어도 한개의 집에는 비둘기가 2마리 있다.

즉, 적어도 2개는 같은 값ㅇ르 갖게 된다. 2^100가지가 아니라 M가지가 된다.

다이나믹으로 해결 가능하다. D[i][j] = i번 곡을 볼륨 j로 연주할 수 있으면 1, 아니면 0

 

△ 1학년

마지막 두 숫자 사이에 =을 넣고, 나머지 숫자 사이에는 +,-를 넣어 등식을 만든다.

중간에 나오는 모든 수가 0이상 20이하

D[i][j] = i번째까지 사용해서 j를 만드는 방법의 수

A[1] +/- A[2] ...+/- A[i] = j

+일때 : D[i-1][j-A[i]]

-일때 : D[i-1][j+A[j]]

D[i][j] = D[i-1][j-A[j]] + D[i-1][j+A[j]]

 

△ 괄호

L=2 : 정답 : 1 ()

L=4 : 정답 : 2 ()(), (())

L=6 : 정답 : 4 ((())), ()(()), (())(), ()()()

※ 올바른 괄호 문자열 = vps

 

1. 빈문자열, vps다.

2. A가 vps면 (A):vps

3. A,B가 vps면 AB:vps

 

첫번째 글자 '('와 대응하는 ')'가 어디있을까? -> 알수없다. i번째 글자라 하자.

첫번째 글자 '('와 그에 대응하는 ')' 사이에 있는 부분은 길이가 몇일까? i-1

뒷부분은? L-i

vps당 올수 있는 개수를 구하면된다.

길이가 i-2인 vps = 2개, 길이가 L-i인 vps = 4개라 하면, 길이가 L인 vps는 총 8개가 된다.

D[L] = 길이가 L인 올바른 괄호 문자열

           = ∑D[i-2]*D[L-i]    (2≤i≤L) i는 짝수

 

※ LCS 문제

Longest Common Subsequence

두 문자열이 있을 때 가장 길면서 공통된 부분수열을 구하는 문제

순서만 맞으면 연속되지 않아도 된다.

2차원 다이나믹

D[i][j] = A는 i까지 B는 j까지 LCS의 길이

① A[i] == B[j]인 경우, 앞에까지의 정답에서 +1

D[i][j] = D[i-1][j-1]+1

② A[i] != B[j]

A[i]                          |          A[i]

        B[j]인 경우와    |   B[j]        인 경우가 있다.

왼쪽은 D[i][j-1], 오른쪽은 D[i-1][j]

D[i][j] = max(D[i][j-1], D[i-1][j])

 

△ 팰린드롬 만들기 1695

A = [1, 2, 3, 4, 2]  N≤5000

답: 1 2 '4' 3 4 2 '1'

 

① LCS를 이용하는 방법

A = [1, 2, 3, 4, 2]

Aⁿ = [2, 4, 3, 2, 1]=  A 뒤집은거

N-LCS(A, Aⁿ)

5 - (=3) =2

팰린드롬이 될수 있는 애들은 그대로 둔다. 2, 3, 2

4와 1을 적절한 위치에 추가한다.

 

② 팰린드롬을 이용하는 방법

첫번째가 마지막과 같으면 팰린드롬이다.

D[i][j] = i~j 팰린드롬

① A[i]==A[j]

이미 팰린드롬. 수를 끼워넣지 않아도 된다.

② A[i] != A[j]

수를 항상 끼워 넣어야 한다. 둘 중 하나

- j에 해당하는 수를 끼워넣는다. D[i][j-1]+1

- i에 해당하는 수를 끼워넣는다. D[i+1][j]+1

 

● 기하 알고리즘 1

난이도가 쉬움부터 무지 어려움까지 무궁무진하다.

게임같은 경우가 기하알고리즘의 천국.

 

○ CCW

모든 기하 알고리즘의 기초.

의미: 반시계 방향(Counter Clock Wise)

점 3개가 이루고 있는 방향이 반시계인지, 시계인지, 일직선인지

두 벡터 P1P2 x P1P3가 양수면 반시계, 0이면 일직선, 음수면 시계

신발끈 공식(외워야 함)

신발끈 공식

x1*y2+x2*y3+x3*y4-y1*x2-y2*x3-y3*x4

벡터곱=평행사변형의 넓이

 

○ 다각형의 넓이

점3개로 이루어진 삼각형

벡터곱으로 ½해서 구하면 됨. = 이론

실제로 구할때는 그냥 ccw를 5개로 늘려서 구하면 됨.

x1 x2 x3 x4 x5 x1

y1 y2 y3 y4 y5 y1

∑Xi*Yi+1 - ∑Yi*Xi+1

 

○ 선분의 교차

ccw를 이용해서 구할 수 있다.

하나의 선분을 잡고 (P1, P2) P3와 P4의 방향이 다르다면 교차한다.

(P1, P2, P3) * (P1, P2, P4) < 0 이렇게

but, 반례가 있다. 방향이 다른데, 교차하지 않는 경우. 이 경우에는 다시 P3, P4를 기준으로 ccw를 구해보면 된다.

 

보통 예외처리를 많이 하면 알고리즘이 잘못된 경우가 많은데,

기하는 예외처리의 천국이다.

 

이도 반례가 있다. 세점이 일직선 위에 있는 경우

즉, ccw가 0이 나오는 조건이 있을때

 

△ 선분교차2
세 점이 일직선 위에 있을 수도 있다.

슬라이드의 3가지 경우를 판단하는 방법

1. P3P4를 기준으로 P1과 P2의 부호가 다름

2,3. P3P4를 기준으로 P1은 +- P2는 0

앞의 식에 부등호만 추가해주면 된다. ≤

but, 모든 점이 일직선 위에 있는 경우... ccw=0인 경우

P2에 대한 P3의 위치와 P1에 대한 P4의 위치를 조사해 한다.

 

○ 다각형의 내부/외부

어떤 점이 다각형의 내부/외부에 있는가?

바깥에 점을 하나 찍고, 그 점과 연결했을때 지나가는 선분의 수를 센다.

짝수면 외부, 홀수면 내부

선분의 교차문제와 같다. 

 

홀/짝으로 계싼하기 어려운 경우, 일직선 위에 있는 점이 없도록 외부의 점을 잘 정하면 된다.

(-10000, 10000)일때 기울기 최대 (0, -10000), (1, 10000) 2만

보통 int의 최대치를 고른다.

 

 

이날 수업은 사실 어려워서 잘 못알아들은게 많다.