작도닷넷 블로그
작도닷넷 블로그

컴퓨터 - ACM ICPC

알고리듬(1/10) - DP, 탐색

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. 그 중에 최소를 찾으면 됨

http://xacdo.net/tt/rserver.php?mode=tb&sl=2555

이름
비밀번호
홈페이지 (없어도 됩니다)

비밀글로 등록
작도닷넷은 당신을 사랑합니다.

[이전 목록]   [1] ... [2][3][4][5][6][7][8]   [다음 목록]

최근 글

이웃로그 관리자 옛날 작도닷넷 태터툴즈 ©현경우(xacdo) since 2001