1. 1629번 - 곱셈
분할정복
a^n = a^(n/2) * a^(n/2) (n이 짝수인 경우)
a^n = a^((n-1)/2) * a^((n-1)/2) * a (n이 홀수인 경우)
나머지 연산은
(A*B)%C = ((A%C) * (B%C)) % C
위와 같은 식이 성립한다.
이 성질과 분할정복 없이는 시간초과가 떠서 도저히 해결할 수 없는 문제
위 방법으로 O(logn)의 시간복잡도로 해결 가능
가장 작은 단위로 분할해서 풀어감
function F(x):
if F(x)의 문제가 간단 then:
return F(x)을 직접 계산한 값
else:
x 를 y1, y2로 분할
F(y1)과 F(y2)를 호출
return F(y1), F(y2)로부터 F(x)를 구한 값분할정복은 이것만 기억하면 끝난다.
자꾸 이걸 간과하고 내멋대로 풀려해서 틀림.. ㅠ
2. set
set 에 in으로 접근하면 시간복잡도 O(1)
list는 in으로 접근하면 시간복잡도 O(n)
특정 원소가 있는지 확인할 때는 set으로 하면 시간 단축
3. 11053번 - 가장 긴 증가하는 부분 수열
LIS (longest increasing subsequence) 문제
다이나믹 프로그래밍 이용하면 O(n^2)
이진탐색은 O(nlogn)
* DP
i번째 원소를 마지막으로 하는 가장 긴 증가하는 부분수열의 길이를 dp[i]에 저장한다. 이중 포문 사용해서 i번째 원소까지 오면서 저장된 값 중 더 큰 값으로 갱신해주는 방식
* 이진탐색
새로운 리스트에 하나씩 옮겨담는데, 이진탐색으로 어느 위치로 들어갈지 확인한다.
이진탐색한 오른쪽 원소를 갱신해준다. (bisect_right)
4. 2493번 - 탑
스택에 인덱스랑 값을 같이 저장하여 관리
반복문이 중첩되어있다고 반드시 O(n^2)인 것은 아니다!
