7일차 강의 (18 ~ 19강)

18강 (수학)

소수 판정법

소수 = 1과 자기 자신으로만 나누어지는 수

= 약수가 2개인 수

= 2부터 n-1까지의 수로 나누어지지 않는 수 O(n)

 

O(sqrt(n))의 방법?

→ 합성수 n에서 1을 제외한 가장 작은 약수는 sqrt(n) 이하이다.

→ 따라서 2부터 sqrt(n) 까지만 나눠보면 됨

하지만, sqrt(n)은 오차가 발생할 수 있음 (실수연산이기 때문)

→ for문이 계속될 조건을 i*i <= n으로 사용

 

범위 내에서의 소수 판정법

1. 각 수가 소수인지 반복해서 판정

2. 에라토스테네스의 체

n까지 배열 생성 (해당 칸이 소수일경우 true 아닐경우 false)

커서 생성

2부터 n까지 진행

2는 내버려두고 4,6,8, ... 을 모두 false로

커서 이동

3을 내버려두고 6,9,12,... 을 모두 false로

4는 소수가 아니므로 skip

... n에 도달할 때까지 반복

위와 마찬가지로 2 ~ 루트n까지만 검사하면 됨.

추가적으로 내부에서는 i^2부터 n까지만 검사해도 무방 함

for (int i = 2; i*i <= n; ++i) 

 for (int j = i*i; j <= n; j += i)

bool 배열보다 vector<bool>이 빠름

 

소인수 분해

정수를 소수의 곱으로 나타내는 것

i*i > n일때 종료하고 n이 1이 아닐경우 그 수를 소인수 목록에 추가함으로써 시간복잡도 개선가능

 

결론 : 소수판정과 소인수분해는 모두 O(루트N)

 

약수 판정 또한 루트n까지만 처리해도 됨 (제곱수일 때에는 예외처리 필요)

 

최대공약수 (GCD)

유클리드 호제법 사용

두 수 A, B에 대해서 A를 B로 나눈 나머지를 r이라고 하면 

GCD(A, B) = GCD(B, r) 이다.

 

GCD(20, 12) = GCD(12, 8) = GCD(8, 4) = GCD(4, 0) = 4

 

int gcd(int a, int b) {

 if(a == 0) return b;

 return gcd(b % a, a);

}

 

최소공배수 (LCM)

A * B = GCD(A, B) * LCM(A, B)

int lcm(int a, int b) {

 return a / gcd(a, b) * b;

}

 

연립합동방정식

나머지의 목록 사이클로 다른 식의 나머지를 찾기위한 반복문을 돌리면 시간복잡도가 줄어듦.

대회에서는 중국인의 나머지정리로 풀이가능 (강의에선 생략) - 모듈로 역수

 

이항계수

nCk, n과 k가 작으면 일반적인 계산식으로 계산 가능

n과 k가 커지면 (1000) n-1Ck-1 + n-1Ck 성질 활용

 

19강 (이분탐색)

응용이 되면 엄청 어려워짐

이분탐색 = 정렬되어 있는 배열에서 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법

STL 존재 - binary_search(a, a+n, t)

가장 왼쪽 위치 구하기 lower_bound(a, a+n, t)

가장 오른쪽 위치 구하기 upper_bound(a, a+n, t)

주의사항

- 이분탐색을 하고자 한다면 주어진 배열은 정렬되어 있어야 한다.

- 무한루프에 빠지지 않게 mid 값을 정해야 한다. (절반으로 잘 쪼개도록 해주어야 함) mid = (st+en+1)/2

직접 구현해야 하는 경우가 많음

 

unique - 정렬된 배열에서 실행을 시켜야 함, 중복 제거, garbage index를 반환

erase를 통해 정리하면 된다.

 

이분탐색 응용

a[i] + a[j] + a[k] = a[l]

O(N^4) 풀이 : i, j, k, l에 대한 4중 for문

O(N^3logN) 풀이 : i, j, k 3중 for문, a[i]+a[j]+a[k]가 배열 a에 있는지 이분탐색

two[m] + a[k] = a[l]

two[m] 배열을 O(n^2)에 생성

O(N^2logN) 풀이 : k,l 2중 for문, a[l] - a[k]가 배열 two에 있는지 이분탐색

 

★뭔가 2개를 묶거나 한 후 어느 한쪽의 값을 이분탐색으로 찾아서 시간복잡도를 낮추는 idea

중복을 허용하지 않으면 훨씬 복잡해짐.

 

Parametric Search (매개변수탐색)

문제 자체가 Parametric Search인 것을 파악하기 힘듦

 

조건을 만족하는 최소/최댓값을 구하는 문제(최적화 문제)를 결정 문제로 변환해 이분탐색을 수행하는 방법

 

(최적화문제) N개를 만들 수 있는 랜선의 최대 길이

(결정문제) 랜선의 길이가 X일 때 랜선이 N개 이상인가 아닌가?

 

최적화문제를 결정문제로 바꿀수있는지 생각, 결정 문제로 얻어낸 함수가 감소 혹은 증가함수인지 따져봐야함