gumdung   5년 전

안녕하세요.백준에 처음으로 문제관련이 아닌 질문을 올리네요.

현재 selection in worst case linear time algorithm (최악의 경우 선형 시간 알고리즘)에 대해서 공부중인데 너무나 이해가 안가서 이렇게 질문을 드립니다.

일단 알고리즘의 과정은

1)만약 원소의 수가 5 이하이면 찾고자 하는 i 번째 원소를 찾아 return 시켜준다

2)전체 원소의 수 n 을 n/5의 그룹들로 각각 나누어준다. - O(n)

3)각 그룹에서 median 을 찾는다(즉 각 그룹에서 3번째 원소를 찾는다) - O(n)

4)각 그룹의 median 의 집합 ={m(1),m(2),.....,m(n/5)} 들중에서의 median = (M) 을 재귀적인 방법으로 구한다 - T(n/5)

5)M을 기준으로 원소들을 왼쪽에는 x보다 작은값들 오른쪽에는 x보다 큰값들로 분할한다. - O(n)

6)분할된 두 그룹중 적합한 쪽을 선택해 윗 과정을 반복한다 - T(7n/10+6)

따라서 T(n) = T(n/5)+T(7n/10+6) + O(n) 라고 알고있습니다. http://www.cs.fsu.edu/~burmeste/slideshow/chapter10/10-3.html 이 링크를 기반으로 보고있습니다.하지만 윗 링크에 보시면 

How many elements are greater than x?

  1. Half the medians, or half of the  é n/5 ù  groups contribute 3 elements greater than x
  2. Except the "mod" group and the group with x itself.

이라고 적혀있는 문장이 잘 이해가 되지가 않습니다.

일단,총 n개의 원소를 기반으로 x에 대해 확실히 작은값들은 왼쪽 윗부분,확실히 큰 값들은 오른쪽 아랫부분,크거나 작거나 알지 못하는 부분들은 왼쪽 아랫부분 과 오른쪽 윗부분인건 이해가 됩니다.
하지만 이를 통해 "중앙값들의 중앙값 = x" 보다 큰 원소의 개수는 "3*((1/2)*(n/5) - 2)  = 3n/10 -6" 인지 도통 모르겠습니다.
(1/2)*(n/5)*3 의 의미는 x보다 큰 값들은 오른쪽 아래 부분이니 (전체 n의 절반) * (5개의 원소 중 3개가 포함) 이라고 이해를 하고,따라서 3n/10 이 나오는 구나!라고 일단 생각을 했습니다.
그런데 왜 여기서 6을 빼는지 이게 잘 이해가 가질 않습니다.....윗 링크에는 
Except the "mod" group and the group with x itself.

이렇게 적혀있는데 이게 의미하는 바가 뭘까요??

조그만한 도움을 주실수 있는 어떤말이라도 감사합니다.
너무 두서 없이 쓰고 말을 잘 못해서 읽는데 불편하셨다면 미리 죄송하다는 말씀을 드리겠습니다.

lovinix   5년 전

문자 그대로라면 x자신이 들어있는 집합과 5개씩 나누었을 때 남는 나머지 집합을 제외하는 것 같습니다.

gumdung   5년 전

ㅠㅠ하루종일 구글링하고 생각하고 해서 깨달았습니다 ㅠㅠㅠㅠ 

자문자답 하겠습니다.

d93e162b-8b8e-419e-bb45-f28cf33c0174

총 n개의 원소를 5개씩 n/5 개의 그룹으로 나누어 줍니다.

이때 x 보다 큰 값들은 회색빛으로 색칠된 부분이죠.

이때 5개의 원소로 이루어 지지 않은 집합(맨 마지막 집합)과 x가 포함된 집합을 제외를 해줍니다.(이건 왜 그러는지는 아직도 모르겠습니다;;;)

그러면 (1/2)*(n/5) - 2 의 그룹수가 됩니다.이 중에 각 그룹 중 x 보다 큰 값들은 3,4,5 번째 원소들이니 3을 곱해줘서 

(3n/10 -6) 이라는 식을 도출해 낼수 있습니다.

더 정확한 설명은 여기에 나와있습니다.

86bea879-f67a-43c6-a7b8-492367e8280e

제가 설명한 부분이 틀린 곳이 있을 수도 있으니 혹시나 이 글을 본 보신 분께서 수정하여 덧붙여 주시면 더 감사하겠습니다.

감사드립니다 ㅠㅠㅠㅠㅠ

olenmg   2년 전

조금 오래된 글이긴 하지만, 

이때 5개의 원소로 이루어 지지 않은 집합(맨 마지막 집합)과 x가 포함된 집합을 제외를 해줍니다.(이건 왜 그러는지는 아직도 모르겠습니다;;;)

라고 말씀해주신 부분은 x보다 큰 값이 3개 있는 그룹만을 추려내기 때문입니다.

x가 포함된 집합은 x보다 큰 값이 2개이고, 완전하지 않은 집합도 마찬가지로 x보다 큰 값이 3개인지 확실하지 않습니다.

댓글을 작성하려면 로그인해야 합니다.