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

컴퓨터 - ACM ICPC

알고리듬(3/10) - 자료구조

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

힙은 완전이진트리에 특정 성질을 추가한 것

힙 (최소값 구할때 쓰는 것 기준)
1. 완전 이진트리
2. 부모 <= 자식

그러면 부모는 항상 최소값임

연산
1.삽입 O(logN)
2.삭제 O(logN)

그냥 최소값 찾는건 O(N) 이니, 비교적 빠름.


1. 삽입 연산
  1
2 5
4
여기에 3을 넣는다고 하면,
완전이진트리 특성상 추가할 공간은 하나밖에 없다
  1
2 5
4 3
현재 부모<=자식 조건을 만족하므로, 더 할 건 없다

그런데 만약 0을 넣는다고 하면
  1
2 5
4 0
부모<->자식 바꿔줘야 함
  1
0 5
4 2
그 상위도 똑같이 부모<->자식 바꿔주고, 이를 루트까지 반복
  0
1 5
4 2


2. 삭제연산
루트노트만 삭제가능
   x(0을 삭제)
1  5
4 2 3

완전이진트리를 만족하기 위해, 맨 마지막 노드를 루트로 올린다
   3
1  5
4 2

그 다음, 자식노드들 중에서 제일 작은 값을 부모와 바꿔줌 (1<->3)
   1
3  5
4 2

이를 마지막까지 반복 (3<->2)
   1
  2  5
4 3

이러면 N개의 높이가 logN이므로 간단해짐


* 부모, 자식 찾는 방법
인덱스를 순서대로 매기면
   1
2  3
4 5 6 7

x*2(홀수) = 왼쪽
x*2+1(짝수) = 오른쪽
x/2 = 부모
이렇게 간단히 접근이 가능하다


중화요리

그냥 배열로 풀면 시간초과가 날 것임
방법은 두가지
1. 링크드 리스트 사용 (서큘러)
   1->2->3->4->5->6->(맨 처음으로 연결)
     탕수육을 먹을때마다 노드 삭제
       2->3->4->5->6->맨처음
        2---->4->5->6->
2. 큐를 쓸 수도 있음
123456
1을 출력하면서 빼고
23456
k-1번을 빼면서 다시 넣어줌
   45623
4를 출력하면서 빼고
   5623
k-1번을 빼면서 다시 넣어주고... 반복
     2356

시간복잡도는 O(KN)로 같음


동맹의 동맹은 동맹

제일 간단한 방법을 생각해보자.

각자 그룹을 매겨주자
1 2 3 4 5
1 2 3 4 5 (그룹번호)

1,2 동맹이라면
1 2 3 4 5
1 1 3 4 5 (그룹번호)

3,4 동맹이라면
1 2 3 4 5
1 1 3 3 5 (그룹번호)

1,3 동맹이라면
1 2 3 4 5
1 1 1 1 5 (그룹번호)

그래서 1,3 동맹인지 물어보면
그룹번호가 1,1로 같으므로 확인 가능

--> 이러면 시간복잡도가 O(N^2)
   그룹번호를 다 바꿔줘야 되서...

이걸 조금만 바꾸면 O(NlogN)으로 줄일 수 있다.
그룹을 합칠때 작은 쪽을 큰 쪽으로 합치도록 하면, 합치는 비용이 N->logN으로 줄어든다.

1 2 3 4 5
1 2 3 4 5 (그룹번호)

각 그룹에 해당하는 숫자들을 따로 가지고 있는데
1 2 3 4 5

1,2 합치고
1 2 3 4 5
1 1 3 4 5 (그룹번호)
1  3 4 5 (그룹멤버)
2
(그룹 2는 없앰)

3,4 합치고
1 2 3 4 5
1 1 3 3 5 (그룹번호)
1  3  5 (그룹멤버)
2  4

3,5를 합치면
1 2 3 4 5
1 1 3 3 3 (그룹번호)
1  3   (그룹멤버)
2  4
   5

이때, (3,4)와 (5) 중에 (5)그룹이 더 작으므로
그룹번호 update를 (5)에 해당하는 것만 3으로 써준다. (이래야 줄어듬)

이것보다 더 빠른 풀이가 있음. 지금 설명하진 않겠음.


작은 소수들의 곱셈

힙을 쓰면 됨
2,3,5,7을 곱해서 만들 수 있는 수들

먼저 힙에 1을 넣고 시작
   1
그리고 1을 빼고
2,3,5,7을 곱해서 힙에 넣어줌
   2
  3 5
7
그 다음에 2을 빼주고
2*(2,3,5,7) 곱해서 힙에 넣어줌

3 4 5 6 10 14

3을 빼고,
3*(2,3,5,7) 곱해서 힙에 넣어줌

이렇게 하다보면
빼놓은 수와 중복되는 경우가 있는데, 이건 그냥 힙에 안 넣어주면 됨

그렇게 5842번 돌리면 20억까지 나옴 (int 범위 넘어갈 수 있으니 long long 사용)

-------
또 다른 풀이
이 문제는 7번 문제와 비슷하다. 비슷하게 풀 수 있음

큐 4개를 만듬 (2,3,5,7)에 대해

2 1___________
3 1___________
5 1___________
7 1___________

답 1___________

여기에서 각 큐에 값을 곱한다

2*1=2 1___
3*1=3 1___
5*1=5 1___
7*1=7 1___

이 곱한 값들(2,3,5,7) 중에 최소값을 답에 넣는다

답 12___

2에서 뺐으므로 2의 큐에서 1을 뺀다
2 ____
3 1___
5 1___
7 1___

그리고 방금 답에 넣었던 2를 각 큐에 넣는다
2 _2__
3 12__
5 12__
7 12__

이제 각 큐의 최소값을 곱해서 후보값들을 구한다
2*2=4 _2__
3*1=3 12__
5*1=5 12__
7*1=7 12__

후보값들(4,3,5,7) 중에 최소값=3을 답에 넣고, 3 큐에서는 뺀다

2 _2__
3 _2__
5 12__
7 12__

그리고 답에 넣은 값(3)을 각 큐에 넣는다

2 _23_
3 _23_
5 123_
7 123_

이렇게 반복하면 답을 구할 수 있다.
소수의 갯수(2,3,5,7)을 K라고 하면, 시간복잡도는 O(NK)
아까 방법이 O(NlogN)이므로 더 빠르다.

여기서 메모리를 더 절약할 방법: 큐 대신 포인터를 활용한다.
큐에서 가리키는 값들이, 답의 값들이므로
답 큐에 포인터를 한칸씩 이동하는 식으로

답 123456....
  ^ ^^ ^
  2의 포인터, 3의 포인터, 5의 포인터, 7의 포인터





스택을 쓰면 됨.
성질을 하나 찾아야 됨.

성질: 1. 큰 놈 하나가 앞에 것들을 다 가려버림
      = 큰 놈 앞의 것들은 정보가 필요없음
     2. 적당히 작은 애들 중에서도, 큰 놈과 그 다음 큰 놈 사이의 것들은 필요없음
    
     --> 필요없는 것들은 제외하고 생각하자
    

    <--
6 9 5 7 4
     4의 시점에서 보면, 필요한 것들은 높이가 오름차순(높아지는 순으로) 으로 보인다
     이것은 진행방향의 역방향이므로, 정방향으로 생각해보자.

스택
| 3 |
| 1 |
+----+
직전 (스택) 값과 비교하면서,
필요하면 넣고, 필요없으면 뺀다.
그러면서 답을 바로 구할 수 있는데, 스택의 맨 마지막 값이 현재위치의 답이다.

시간복잡도는 스택에 넣고 빼는 횟수를 생각해보면
최악의 경우 넣는게 N번, 빼는게 N번 = 그러므로 O(N)


구간합

새로운 자료구조를 써야 함.
인덱스 트리. (자주 변하는 값들의 대표값(합,최대/최소..)을 빨리 구할 때)

아까 완전 이진트리를 알려드렸는데
전 이진트리는 조금 다르다.

전 이진트리 = 완전 이진트리인데 리프 노드가 다 꽉 찬거

   o
o  o
o o o o
1 2 3 4

인덱스 트리 = 맨 마지막 노드에만 값을 넣는다.

그 상위 노드들은 필요한 연산을 함. SUM,MAX...

     8=3+5
3=1+2 5=3+4
1 2   3 4

예를 들어 2 4 1 3 -5 7 -4 9 이면
     17
  10     7
6  4   2   5
2 4 1 3 -5 7 -4 9

여기서 숫자 하나가 변하면, 상위 노드들만 업데이트 해주면 됨 (logN)

그럼 구간합은 어떻게 구하나?
리프 노드부터 상위로 올라가면서, 필요한 것만 추린다.

      17
  10     7
6  4   2   5
2 4 1 3 -5 7 -4 9
s     e
start ~ end 범위를 구한다고 하면
1.left=오른쪽 자식
2.right=왼쪽 자식
종료조건=left>right

      17
  10     7
6  4   2   5
2 4 1 3 -5 7 -4 9
^    ^^^       4가 필요함 (오른쪽 -5,7은 상위노드에서 구할 수 있음)

      17
  10     7
6  4   2   5
   ^   ^       4,2가 필요함
2 4 1 3 -5 7 -4 9


      17
  10     7
  ^^     ^     아무것도 필요없음
6  4   2   5
2 4 1 3 -5 7 -4 9

      17
      ^^       아무것도 필요없음
  10     7
6  4   2   5
2 4 1 3 -5 7 -4 9

               이렇게 루트 노드까지 도달해서,
                     필요한 것들(4,4,2)의 합을 구하면 됨
                    
또는, start ~ end 이외의 구간을 모두 0으로 바꾸어서 전체 합을 구하는 식으로 해도 됨



중앙값

2개의 힙 구조를 이용

max힙  중앙값   min힙
   (언제나 하나)
       1
       맨 처음 값을 일단 중앙값에 넣고
    값을 새로 입력할때마다 중앙값과 비교해서
    큰 값을 min힙에 넣고, 작은 값을 max힙에 넣는다.
    (입력값은 항상 홀수개이므로, 이것을 2개씩 넣어서 짝을 맞춘다)
    
    그러면 min힙에는 중간값보다 큰 것들중에 제일 작은 값,
         max힙에는 중간값보다 작은 것들중에 제일 큰 값이 들어간다.
          
    근데 이러고 나서, max힙의 갯수와 min힙의 갯수가 다를 수 있다.
    그러면 더 이상 중간값이 중간값이 아니다.
    
    이를 해결하기 위해: min힙의 최소값을 빼서 중간값에 넣고, 기존 중간값을 max힙에 넣거나
                  max힙의 최대값을 빼서 중간값에 넣고, 기존 중간값을 min힙에 넣어서
                         min힙, max힙의 갯수를 같게 한다 -> 그러면 중간값이 구해짐


소수들의 곱셈

위의 작은 소수들의 곱셈 문제에서 소수 4개를 100개로 확대한 것
풀이는 같음.
큐를 쓴다면 100개를 써야 함. 아니면 포인터로.



태양이와 울타리 (수퍼롤러)

N개의 숫자가 주어짐
0 1 2 3 4 5 6 7 .... N
X너비를 칠함

전체에 대해 얼마나 올라갈지 미리 계산을 해둠
정의
G[i]=i를 왼쪽 끝으로 할때 최대로 올라갈 수 있는 높이

인덱스 트리를 활용할 수도 있고,
안 써도 활용할 수 있음. greedy한 접근

예를 들어)
N 0 1 2 3 4 5 6 7
  3 1 8 4 6 2
  X
     X
   X
     X
       X   ==>유효하지 않을 조건은 무엇일까?
               1. x앞에 x보다 큰 값은 유효하지 않다.
                  2. 구간을 벗어나는 순간 유효하지 않다.
G 1 1 4 2 2 2

deck을 쓰면 됨

0 1 2 3 4 5 6 7
4 3 5 4 6
값덱  인덱스덱
| |   | |
| |   | |
| |   | |
| |   | |
|4|   |0|
3이 들어오는데 더 작으니, 4를 빼고 3을 넣음

| |   | |
| |   | |
| |   | |
| |   | |
|3|   |1|
5가 들어가면 더 크니, 넣음

| |   | |
| |   | |
| |   | |
|5|   |2|
|3|   |1|
인덱스 지나간건 빼줌

이제 G를 가지고 계산하면
G[i] G[i]>G[i+1]이면 가능성이 남아있다.

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

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

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

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

최근 글

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