이미지 텍스트 확인
(1)자유게시판
(2)이거 개웃기네 ㅋㅋㅋ
(3)교수님 좀 치시네
(4)나라가 어떤 유행에 휩쓸리다 보니 부모의 성을 다 사용하여 성을 지어야 하도록 법령이 개정되었다. 이렇게 세대를 거치면 성의 길이가 2’의 속도로 늘어난다. 예를 들어, ‘최전두환’과 ‘박이’순자’가 결혼하여 재용을 낳으면 이 사람은 ‘최전박이 재용’이 된다. ‘최전박이 재용’과 ‘박김이전’지숙’이 결혼하여 소라를 낳으면 이 사람은 ‘최전박이박김이전 소라’가 된다. 이렇게 하여 몇백년이 흐르고 나니 성이 너무 길어져 도저히 호적을 관리하기가 힘들어지게 되었다. 이에 국가에서는 국민들의 성에서 중복이 일어난 부분을 모두 제거하고 남은 성들을 가나다순으로 정렬한것으로 성을 삼기로 결정하였다. 예를 들어, ‘김박박이최전이전천방박박마박천’이란 성을 가진사람의 성에서 중복을 제거하면 ‘김박이 최전천방마’가 된다. 이것을 가나다 순으로 정렬하면 김마박방이전천최’가 된다. 이것이 이 사람의 새 성이 된다. ‘남궁’ 같은 2자 성은 없다고 가정한다.모든 국민에 대해 이 작업을 하고자 하니 효율적인 알고리즘이 필요하게 되었다. 길이가 충분히큰 n에 대해 이 작업을 효율적으로 하기 위해 레드 블랙 트리를 사용하여 중복되는 성들을 제거한 다음 이로부터 가나다순으로 추출하기로 하였다.
(5)이것은 개략적인 스케치만 한 것으로 여러분은 이 목표를 달성하는 과정을 좀 더 구체적으로 설명하여 이 과정을 이해하고 있다는 점을 드러내보시오. 그리고 이 방법의 평균적인 경우의 수행시간을 표기로 제시하시오. 수행 시간은 성의 길이 2과 이 중 서로 다른 성의 개수 가 사용된 점근적 표현을 써야 한다. 이것은 k가 아주 작은 값일 수도 있고, 거의 n에 근접하는 큰 수일수도 있기 때문에 분석 과정에서 무시할 수 없다.
(6)‘나라가 어떤 유행’
!
