컴퓨터 - ACM ICPC
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]이면 가능성이 남아있다.