컴퓨터 - ACM ICPC
16/08/08 23:39(년/월/일 시:분)
[DP]
#1 파스칼 삼각형
#2 배낭(knapsack) 문제
Weight
Cost
D[i][j]=1~i까지 보석이 있을때
j크기의 배낭에 넣을 수 있는 최대비용
1. i번째 보석을 사용 O D[i-1][j-W[i]]+C[i]
2. X D[i-1][j]
1,2번 중에 큰거
* i=1,2,3...를 덮어쓰면 D[j]만으로 풀수도 있음
메모리만 적게 쓰고 시간은 그대로임.
#3 최대구간합(MS)
누적합을 구해놓음
A = o o o o 주어진 값
S = o o o o 누적합
D[i]=1~i까지 있을때, i를 포함하는 구간의 최대합
D[i]=max(D[i-1]+A[i],A[i])
#4 Map Coin
(0,0) -> (i,j)에 도달할때 얻을 수 있는 최대 코인
D[i][j]=(i,j)에 도달할때 얻을 수 있는 최대 코인
↓
→o 2가지 경우가 있음
D[i][j]=max(D[i][j-1],D[i-1][j])+C[i][j]
1.최대한 구체적으로 정의. 나중에 줄이더라도
2.D[i]와 D[j]와의 관계를 파악, 점화식 만듬
3.2번까지 하고 최적화 팁: 그래프 모양을 보고 convex hull trick등을 사용 가능
* Recipe (일반적인 건 아니고 팁)
1. 1~i까지 있을때
(j상태) 문제에서 요구하는 SUM, MAX, MIN...
2. Knapsack
3. 사선 DP
: 채워나가는 방식이 사선인거
↘
↘↘
↘↘
구간의 크기에 의존
50% 이상이 이것일것
예) 팰린드롬 체크
D[i][j]=i~j 1
0
기본 정의하고
D[i][i]=1
D[i][i-1]=1
s~e 하고 문제에서 요구하는 조건
대체로 2차원인데, j상태에 따라 3차원으로 갈수도 있음
a
bab
cbabc
이렇게 넓어짐
4. Backtracking DP (예: 정올 등산로 찾기)
메모이제이션 활용
5. 트리 DP (예: 정올 SNS(사회망 서비스))
서브트리의 값들을 더함
Backtracking 가능하면 안 사용 -> 재귀로 가기 때문에 깊어지면 스택 메모리 초과
그렇다고 비재귀로 짜기엔 코드가 복잡해짐. 그냥 DP가 간단.
[탐색]
모든 경우를 탐색해야 함. 이게 가장 중요.
공간에 따라: 선형 구조, 비선형 구조
탐색) 선형 탐색 VS 이분 탐색
O(N) O(logN)
비선형 탐색은?
- 대부분의 문제의 해 공간은 선형이 아니다
각 경우마다 가지를 그으면 트리 모양이 나온다
n개
o→o o m개
↓
o o o
O(2^(n+m-1))
40,30,20,10 중 일부를 더했을때 50이 되는 경우
o
|| 40을 포함하거나, 포함하지 않거나
oo
|||| 30을 포함하거나, 포함하지 않거나
oooo
....
int a[30];
void f(int depth){
int i;
if(depth==n){
메모이제이션
return i;
}
for(i=0;i<2;i++){
a[depth]=i;
f(depth+1);
}
}
재귀로 짰음.
DFS(깊이)
50보다 큰 경우를 가지치기(pruning)하면 빨라짐
BFS(너비)는? 최대,최소 구할때. 큐 이용
갔던 데를 또 안 가는게 중요.
안 그러면 시간복잡도가 2^n이 됨.
최소 연산횟수 *2 -1
현재숫자큐 연산횟수큐
100만까지 갈수잇음
...
6 4
8 3
3 3
4 2
2 1
1 0
- 한붓그리기
오일러 법칙. 간선 짝수, 홀수
전부 순환하려면 전부 짝수여야 하고
시작점,끝점은 홀수
- 파라매트릭 서치
답이 선형일때
답이 가능한지를 계속 체크
입력에 대해 가능한지
↑
|
|
|
| *--------
o------- ___________답
|
|
|
--------*
o___________답
문) 중량제한 주어지면 최대 가능 무게 찾기
60키로 들어보고 -> 가능
100키로 들어보고 -> 불가능
80키로 들어보고 -> 가능
--> 이렇게 찾아나감
구간을 반씩 줄여가면 로그시간에 가능
int범위(21억)이면 31번, long이어도 62번이면 가능
인접한 비트의 갯수
D[i][j][k] = i자리 2진수에서 인접한 비트가 j개인, 끝자리가 k인 수열의 갯수(k=0,1)
초기값
D[1][0][0]=1;
D[1][0][1]=1;
점화식
D[i][j][0]=D[i-1][j][0]+D[i-1][j][1];
D[i][j][1]=D[i-1][j][0]+D[i-1][j-1][1];
롤러코스터
D[i][j]= i칸까지 j원을 이용해 만들 수 있는 최대 재미
초기값
D[0][0]=0;
D[0][i]=-1; (0
리스트 L 정의
L[i]= i를 끝점으로 하는 위치에 해당하는 부품의 인덱스
S[i]=갯수
L
1
2 - 3 (1개)
3 - 1 - 2 (2개)
4
5
6
7
테스트케이스 보고 하기보다는
점화식 만드는 연습을 해야 빨리 풀 수 있다.
점화식
D[i][i] = max(D[i-W[L[k]]][j-C[L[k]]] + F[L[k]])(D[i-W[L[k]]]!=-1,0<=k
now=L=[k] (리스트의 현재원소의 인덱스)
[.........][Wnow]
D[i][j] = MAX(i-W[now]칸까지 j-C[now]원을 이용해 만들 수 있는 최대 재미 + 부품 now의 재미도
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 단, 최대 재미가 가능해야 함. -1이면 안됨.
3중 for문
for(1~L)
for(1~B)
for(1~S[i]-1)
단, 원소의 갯수만큼 도니까 O(LB+n) = O(N)
N퀸
TREE 돌면서 모든 경우의 수 찾기
N factorial 수
permutation 순열
bool is_use[30];
int a[30];
void f(int w){
if(w==n)
if(대각X) cnt++; return;
{
for(i=0;i
if(is_use[i]) continue;
//메모이제이션
if(checkW[w+i+n]) continue;
if(checkW[-w+i+n]) continue;
checkW[w+i+n]=1;
checkW[-w+i+n]=1;
is_use[i]=1;
a[w]=i;
f(w+1);
is_use[i]=0;
checkW[w+i+n]=0;
checlW[-w+i+n]=0;
}
}
대각X:
y=x+a;
y=-x+b;
(i,a[i]);
a=-x+y;
b=x+y;
(i+a[i]+n, -i+a[i]+n)
소수경로 문제
소수 체크하는 방법
2 ~ 루트X까지 나눠봐도 됨
에라토스테네스 - 소거법
O(nlog^2n)
100만이어도 풀 수 있다
동굴 문제
정렬을 해주면 줄어듬
부딪치는 순서가 중요한게 아니라, 몇개 부딪치느냐만 찾으면 되니까
몇 개나 부딪치냐, 이분탐색으로 해도 되는데
앞에서 마지막 것을 h로 저장해서, 거기서부터 찾아가면 h+N 에 끝남
탐색은 merge sort
f(s,e) = s ~ e
f(s,(s+e)/2),f((s+e)/2+1,e)
등산
결정 알고리즘
h가 가능한지, 불가능한지 판단
파라메트릭 서치
BFS를 그냥 돌면 안됨
2^n 만큼 돌게 됨
knapsack + BFS
가능한 h_min에 대해 다 돌면
시간 n*n*h*logh
재밌는 게임
각 그룹을 하나의 노드로 간주, 연결선 그려줌
뒤집는다 -> 인접한 노드가 하나로 합쳐진다
즉, 그래프의 지름을 찾는 것과 같다
뒤집는 횟수 = (지름+1)/2
지름 찾는 법:
1. 모든 노드에 대해 가장 거리가 먼 것 구하여
2. 그 중에 최소를 찾으면 됨
[이전 목록]
[1] ... [2][3][4][5][6][7][8]
[다음 목록]
|
|