아.. 이거 그냥 자료 배열에서 구간 정해놓고 최솟값 찾는거라고 생각해서
아 이거 x밥인데 뭘 거창하게 강의를 하지..?
했는데 생각보다 이해 안되서 공부를 해야것다.. 애립네...
사실 찾고자 하는것은 굉장히 간단해 보인다.
배열이 주어지면,
주어진 a부터 b까지의 정해진 구간 내에서 최솟값을 찾는 것이다.
a가 더 작은 값이니 a는 0번 배열, 즉 첫번째 배열일 경우가 가장 작은 값, b는 배열 n-1번째까지(n개의 배열이 있다고 할 때)가 가장 마지막 배열이다.
하지만 알다시피, 멍청하게 하면 시간만 주어지면 누구나 할 수 있는 문제이다.
하지만 이런 문제를 해결함에 있어서 복잡도O(ଲ)안에 해결해야하는 부분이기에 노가다(Brute-force) 방법은 지양한다.
가장 시간이 긴 경우, 전부 읽게된다면 a가 0번째이고 b가 n-1번째이다.
어떤 전처리도 필요없고, 하나쓱 읽으니까 n개 읽으니 시간복잡도는 O(n)이 된다.
하지만 이 문제를 접근하는 방법은 Brute-force이외에도 다양하다.
ㄱ. O(n^2) 전처리, O(1) 질의 - (전처리를 해주는 경우)
세상에 공짜는 없다.
전처리가 길어지면 질의가 간단하고,
질의가 길어지모 전처리가 길어진다.. 호우 쉐엣.
열심히 살자.
전처리 : 가능한 a, b 모두에 대해서 미리 답을 B[a][b]에 저장하는 것이다.
-> RMQ(a,b) = B[a][b]
이 부분, ppt만 보고 머선 말인지 몰라서 부들부들거렸는데, 그럴 필요 없었다.
RMQ(a,b)를 2차원 배열로 놓았을 때, 나올 수 있는 a값과 b값이 있을 때, 그때 될 수 있는 RMQ값을
B[a][b]에 적어주는것이다.
이때, 이 처리를 해주는 복잡도는 O(n^2)이다.
복잡도 왜 O(n^2)냐면,
처음에, a값이 0부터 n까지 가능하니까 n개
b값은 a값 제외하고서 (n-a)개지만 시간복잡도로 하면 잡것들 다 띠니까 n으로 보고,
n*n하게되서이다.
B를 모두 계산하는데 걸리는 시간
-> 단순계산을 하는 경우는 O(n^3) - n^2칸을 채워야 하고, 한칸을 채우는데 최대 n시간이 걸린다.
이 때, O(n^3)이 되는 이유는 앞서 B의 배열을 구해준 경우가 n^2이고,
그 배열 한 칸을 채우는데 최소 0에서 최대 (n-1)이니까, n-1로 잡으면
n*(n-a)*(n-1)을 하면 시간복잡도는 O(n^2)이 되는 것이다.
O(n^2)시간에 계산한다.
ㄴ. 어헛? 그런데 구간을 하나씩 더 늘리고싶다!??
그건 문제가 안된다.
"재귀적 귀납법"으로 시간을 줄여나가면 된다.
예를들어, 범위가 a부터 a인 자기자신이 최소이자 최대인 단독인 수라고 하자
그렇다면, RMQ(a,a)와 같은 식으로 표현될 것이다.
RMQ(a,a) = A(a)이고
b값이 주어졌을 때, 거기서 구간 1이 더 늘어난다고 해도 다음과 같은 식으로 표현이 가능하다.
RMQ(a, b+1) = min(RMQ(a,b), A[b+1])
그러면 이 경우의 시간 복잡도는 기존의 구해놓은 값에서 늘어나는 구간 수(상수값)만큼 더해주면 되기에,
즉, (내가 채울 칸수 + n^2)이 되기에 시간복잡도는 O(n^2)이 된다.
ㄷ. O(n) 전처리, O(sqrt(n)) 질의
앞서 ㄱ,ㄴ문제에 대한 답을 생각해보면,
n^2시간 전처리 잡고 상수시간 질의하면, 어? 이거 개꿀인데? 할수도 있지만
만일 n의 갯수가 애기들 소꿉놀이가 아니라, 100만 단위로 넘어가버리면, n^2의 경우
조단위가 되어버리는 현상이 나타난다.
그럼 넘 곤란하다. ㅎ
추가적으로 a의 값이 바뀐다면,
a값이 가변적이라면, a값만 수정하면 되는 것이 아니라 새로생기는 최솟값이 있을 지 몰라
처음부터 다시 계산해야한다.
처음으로 돌아가보자 컴퓨터는 10^9의 일을 컴퓨터는 1초에 할 수 있다.
n^2의 시간이 걸리는 처리방식 채택해서 RMQ를 해결한다면,
n이 3만만 되어도, 컴퓨터의 처리가 1초안에 못들어오는 현상이 발생한다.
그렇다면 sqrt함수를 사용한 방법을 채택해보자.
sqrt 함수는 매개변수 x로 들어온 숫자에 루트를 씌워 계산한 값을 반환해주는 함수이다.
간단히 루트 x를 구해주는 함수이다.
답부터 이야기한다면, 루트 n개로 쪼갠다고 하자
그럼 3개씩 쪼개서 그림과 같이 쪼개질 것이다. (한개가 마지막에 남는다.)
처음 3개는 2,4,3,이고 그중에 제일 작은건 2, A[0]위치에 있다.
두번째 3개 중 가장 작은것은 1, A[3]위치에 있다.
세번째 3개중 가장 작은것은 1, A[8]위치에 있다.
9번 위치에서 가장작은건 자기자신이다.
이렇다면 루트 n개로 나누면 거의 루트 n개의 묶음이 나온다.
그리고 앞서서 그 묶음에서 가장 작은 값을 구했다.
그러면, 본격적으로 지금 구하고자 하는 것은 "구간 최소 트리"이니까
"구간" 최소 트리이니 구하고자 하는 구간 내에서 생각을 해보자
배열 2부터 7까지의 구간 내를 고려해야 하니,
다음과 같은 그림이 될 것이다.
구간 2부터 7까지의 수 중에서 두번째 묶음으로 나눴던 구간, M[1]에서의 최솟값은 1로 A[3]인 것을 구해두었다.
그렇다면, 구하고자 하는 것은 구간내의 값에서 최솟값 하나만 알면 되기에 M[1]구간에서 다른 수는 고려할 것 없이,
A[3]이고
그 전 묶음에서 걸쳐지는 수 하나 A[2]와, M[1]안에서 A[3]와 A[6], A[7]을 비교하면 된다.
이 때 시간이 얼마나 걸리는 지 알아볼까.
컴퓨터 문제 해결에 있어서는 시간이 제ㅇㄹ루 중요하니께,
뭐 해줘야하냐면, 일단 묶음을 루트 n개로 나누니까 root n개만큼 나누고
그다음에 root n개로 나눠준것들 말고 잡것들 중간에 구간에 짤리는 것들
A[2], A[6], A[7] 즉 3, 8, 9는 개개의 값으로 하나쓱 비교해줘야한다.
그럼 이제 진짜 max갯수를 구해보자.
2 * (루트 n - 1)개 + (루트n-1)개 = (답)
여기서 앞서 나온 항의 2는 양쪽 끝에 잘리는 갯수 두개다.(시간복잡도에서 -1은 무시해줘도 된다.(1은 root n에 비해서 느리게 증가하는 수이기 때문에) 모르면 시간복잡도 검색해보라)
뒤에 나온 항의 (루트n-1)은 (커다란 묶음)인 부분이다. 전부 다해서 루트 n이 딱 떨어지면 굳이 넣을 필요가 없으니까(이거 뭔말임? 존나 다시들어도 이해가 안됌)
이렇게 되면 답 시간복잡도는 루트n *3이 된다.
총 2sqrt(n) + sqrt(n) = 3sqrt(n)이다.
자 이렇게 시간이 계속 주는 과정이 보여요.
(설명 중 띵언)
Q. 시간이 줄면 좋은 거 아니에요?
A. 단점은 우리가 이해하기 힘들어지잖아요.
하지만 이해하기 힘들다는것은 근데 상대적이에요.
우리가 공부를 하면 할수록
우리가 점점 더 어려운걸 이해할 수 있으니까..
ㄹ. O(n lg n) 전처리, O(1) 질의
문자 그대로다. 모든 각가의 A[i]에서 i값을 a로 두고
b가 a+1일 경우,
b가 a+2일 경우,
b가 a+4일 경우의 답을 모두 구해놓는다.
"근데 이러면 개노가다로 시간 개오래걸리는거 아님????"
이라는 의문이 생긴다.
일단 화장실좀 갔다오겄다.
'Major > 문제 해결 기법(Application of algorithm)' 카테고리의 다른 글
| 네트워크 플로우 (0) | 2020.05.17 |
|---|---|
| 세그먼트 트리 - (Segment Tree) (0) | 2020.04.24 |
| 욕심쟁이 기법(Greedy Algorithm) (0) | 2020.04.24 |
| (4주차) - 문제해결기법 (0) | 2020.04.10 |
