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

컴퓨터 - ACM ICPC

알고리듬(2/10) - DP, 정렬

16/08/09 21:36(년/월/일 시:분)

막대기

d[i][j]=1~i번 막대기를 사용해서 총 j길이를 만드는 경우의 수
d[0][0]=1
d[1][0]=d[0][0]
d[1][1]=d[0][1]+d[0][0]...

1,2,3으로 5를 만드는 경우
0 1 2 3 4 5
0 1 0 0 0 0 0 (한번도 안쓰는 경우를 1로 침. 즉 0을 0번 써서 0을 만드는 것)
1 1 1 1 1 1 1
2 1 1 2 2 3 3 (2를 뺀 경우, 위에서 2칸 앞의 것들을 가져옴) 하나 뺸 경우 2칸 앞, 두개 뺸 경우 2칸 앞 + 4칸 앞....
3 1 1 2 3 4 5 (3을 뺸 경우, 위에서 3칸 앞의 것들을 가져옴) 3칸앞+6칸앞+....

정렬이 안되있어도 상관없음

1,2,5 막대기를 사용할 경우
0->1->2->5 순서로 풀던
0->5->2->1 순서로 풀던 상관없음. 답이 같음.

O(KN^2) D[i][j] += D[i-1][j - k*L[i]];
O(KN) D[j] += D[j-a];


합분해

d[i][j]=i까지의 정수 j개를 써서 합이 i가 되는 경우의 수 (순서가 바뀐 경우도 다른 경우로 세고, 같은 수도 여러번 쓸 수 있음)
d[i][j][0] 0을 포함하는 경우
     [1] 0을 포함하지 않는 경우

----
d[i][j]=숫자를 i번 더해서 j를 만드는 경우의 수
     =d[i-1][j]      +d[i-1][j-1]   + .... + d[i-1][0]
마지막에 0을 더하는 경우 1을 더하는 경우
     매번 더할때마다 MOD연산 해줘야 함 %1000...
                   --> V=A+B if(V>=MOD) V -= MOD; 이렇게 하면 MOD 연산횟수를 줄일 수 있어서 조금 빨라짐


new night

한 나이트가 다른 나이트를 한번에 잡을 수 있는 위치에 놓아서는 안된다.

나이트의 방향상, 윗줄 먼저 하고 아랫줄을 판단하면 된다.
현재 줄에서 윗줄만 겹치는지 파악하면 된다.

윗줄을
1번째: [0][0][1][0][0][1] 이렇게 배열로 표현하고
     0=불가능
        1=가능
2번째: .................. 배열로 표현
--> 이를 2진수로 간략하게 표현한다

1번째: 2^10 가지수
2번째: 2^10 가지수
     = 2^10 * 2^10
      
d[1][000000(2)]
   101001(2)
     001001(2)
d[2] = d[1] 중에 max() + d[2] 1의 갯수


3칸 예를 들면
[1] = 000
    100
     010
     001
     101 5가지
그러면 그 다음에
[2] = 000 이면 max([1]...) + (000)의 1의 갯수
    100 --> 이러면 [1]에서 불가능한 경우가 생긴다. 이것을 빼고 max() + (100)의 1의 갯수
    
    단, 장애물이 있는 경우는 제외해야 하므로 마이너스 무한대 값(예: -1, 0...)을 넣어주면, max() 구하면서 자연스럽게 빠질 것
    
이렇게 하면 한칸 한칸 찾는게 아니라,
        한줄 한줄 찾으므로 속도가 더 빠르다.


가장 많은 수
1. 일단 정렬을 시키고 : O(NlogN)
2. 앞에서부터 순차적으로 찾아나간다 : O(N)


지은이가 지은 집

수열 A 중에서
A[i],A[j]를 골라서
A[i]+A[j]=X가 되는 값을 찾는 문제. (답이 여러개일 경우, 가장 차이가 큰 것)

일단 정렬을 시켜놓고,
1 2 7 8
합이 10인 경우
맨 앞에 1에 대해서, 9을 찾으면 된다. (이때 이분탐색)
그런 식으로 1,2,7,8 차례차례 찾아보고
여러 답 중에서 A[j]-A[i]가 제일 큰 것으로 찾음.
-->근데 1 2 5 5 7 이렇게 5가 겹칠 경우 처리가 복잡해진다.

다른 풀이)
1 2 7 8
x-> <-y
x+y>10인 경우, y--
x+y<10인 경우, x++
근데 답을 찾은 경우, x=y이면 중복이니 답이 아님
1 2 5 5 7 이렇게 되면 5,5를 찾아도 x 1 2 5 7  이렇게 되면 5,5를 찾으면 x=y

시간복잡도는 (정렬 제외)
1번 풀이는 O(NlogN)
2번 풀이는 O(N)


집합

A,B가 정렬되어있다고 하면,
C를 만들때 A,B를 꼬이게 꺼내는 것은 항상 손해임
A 10 20 35
B 30 40
C 5 10

증명
A1 <= A2
B1 <= B2 일때,

  꼬이게 하는 경우: |A2-B1|+|A1-B2| 이것이
안 꼬이게 하는 경우: |A1-B1|+|A2-B2| 이것보다 항상 크거나 같다.

꼬이면 더 커진다.

안 꼬이게 하려면, 작은 쪽을 기준으로 생각을 했을때
A 큰 집합
B 작은 집합

d[i][j]=A에서 1~i번 사용
     B에서 1~j번 사용
                하는 C배열의 합

d[i][j]=min(d[i-1][j],    d[i-1][j-1]+|A[i]-B[i]|_
        Ai를 제외한 값
최종 답은 d[n][m]

A B 0 30           40
0  0 무한대         무한대
10 0 20           무한대
     =min(무한대,0+|20-10|)
20 0 10           40
     =min(20,0+|30-20|) =min(무한대,20+|40-20|)
35 0 5            15
     =min(10,0+|30-35|) =min(40,10+|40-35|)


개구리

여기서 N^2 배열을 다 찾으려고 하면 너무 오래 걸리고
4방향으로만 움직인다고 한정해서 풀어야 함

정렬을 2번 할 것임

x,y축을 단순화

(x-d,y+d) (x+d,y+d)
↖     ↗
   o(x,y)
↙     ↘
(x-d,y-d) (x+d,y-d)

이것을
X=x+y
Y=x-y
이렇게 바꾸면 X,Y축에서 상하좌우로 움직이는 것과 같다

  ↑
← o(X,Y) →
  ↓

이것을 다시 x,y를 찾으려면
x=(X+Y)/2
y=(X-Y)/2
이러면 됨.

그 다음, 연잎들을 Y축,X축 순서로 정렬해서 번호를 매기면

Y
↑     9 10 11
   4 5 6 7 8
     1 2 3
→X

여기서 1,2번은 Y축이 같고 인접하므로, 움직일 수 있다.
3,4번은 Y축이 다르므로, 움직일 수 없다.
이를 기억한다.

1 2 3 4 5 6 7
A 2 3
B
C  1 2
D

이러면 A,C방향만 찾을 수 있다.
B,D방향도 찾으려면 X축,Y축 순서로 다시 정렬을 하고 찾는다.

이러면 그래프 순서대로 따라가면 된다.
근데 문제는, 움직이면 현재 연잎이 가라앉는 것.

예를 들어 6번을 지나서 없어진다고 하면,
그래프를 업데이트 해줘야 한다.

Y
↑     9 10 11
   4 5 x 7 8
     1 2 3
→X

6번이 있던 자리가 없어지면,
5,7번이 직접 이어질 것이고 (A,C방향에 직접 이어지도록 찾아서 업데이트)
2,9번이 직접 이어질 것이다.(B,D방향 업데이트)

그래프가 끊어지는 경우에는, 값이 지워지도록 업데이트

이렇게 하면 답을 찾을 수 있다.


개구리

여기서 N^2 배열을 다 찾으려고 하면 너무 오래 걸리고
4방향으로만 움직인다고 한정해서 풀어야 함

정렬을 2번 할 것임

x,y축을 단순화

(x-d,y+d) (x+d,y+d)
↖     ↗
   o(x,y)
↙     ↘
(x-d,y-d) (x+d,y-d)

이것을
X=x+y
Y=x-y
이렇게 바꾸면 X,Y축에서 상하좌우로 움직이는 것과 같다

  ↑
← o(X,Y) →
  ↓

이것을 다시 x,y를 찾으려면
x=(X+Y)/2
y=(X-Y)/2
이러면 됨.

그 다음, 연잎들을 Y축,X축 순서로 정렬해서 번호를 매기면

Y
↑     9 10 11
   4 5 6 7 8
     1 2 3
→X

여기서 1,2번은 Y축이 같고 인접하므로, 움직일 수 있다.
3,4번은 Y축이 다르므로, 움직일 수 없다.
이를 기억한다.

1 2 3 4 5 6 7
A 2 3
B
C  1 2
D

이러면 A,C방향만 찾을 수 있다.
B,D방향도 찾으려면 X축,Y축 순서로 다시 정렬을 하고 찾는다.

이러면 그래프 순서대로 따라가면 된다.
근데 문제는, 움직이면 현재 연잎이 가라앉는 것.

예를 들어 6번을 지나서 없어진다고 하면,
그래프를 업데이트 해줘야 한다.

Y
↑     9 10 11
   4 5 x 7 8
     1 2 3
→X

6번이 있던 자리가 없어지면,
5,7번이 직접 이어질 것이고 (A,C방향에 직접 이어지도록 찾아서 업데이트)
2,9번이 직접 이어질 것이다.(B,D방향 업데이트)

그래프가 끊어지는 경우에는, 값이 지워지도록 업데이트

이렇게 하면 답을 찾을 수 있다.


K번째 수
quick sort 응용
1. pivot을 잡음 --> 맨 앞에걸 가져오기보다는,
              랜덤으로 찍어야 속도가 더 잘 나옴
  pivot 기준으로 작은거, 큰거로 파티션을 나눠줌
2. 원래는 양쪽 파티션을 다 들어가야 하나,
  우리가 관심있는 부분은 k 번째이므로, k보다 작은 부분은 정렬이 안되도 상관없다.
   그러므로 k보다 큰 부분만 정렬을 시킨다.

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

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

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

[이전 목록]   [1] ... [4][5][6][7][8][9][10][11][12] ... [235]   [다음 목록]

최근 글

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