행성 X3 문제 문제 설명 상근이는 초등학교 졸업 여행으로 외계 행성 X3에 방문했었다. 이 행성에 사는 사람들의 이름은 모두 자연수이다. 행성의 거주민은 모두 서로를 알고 있다. 두 X3인은 그들의 친밀도를 자신의 이름을 이진수로 바꾸어서 계산한다. 두 이름을 이진수로 바꾸고, 자리수가 짧은 쪽을 기준으로 정렬한다. 이때, 두 이진수의 각 자리 아래에 두 자리가 같으면 0을, 다르면 1을 적는다. 이 결과 이진수를 다시 10진수로 바꾸면 그들의 친밀도가 된다. 예를 들어, 10과 19의 친밀도는 25이다. 1 0 0 1 1 = 19 0 1 0 1 0 = 10 -------------- 1 1 0 0 1 = 25 행성의 가치는 이 섬에 있는 모든 친밀도의 합이다. 행성 거주민들의 이름이 주어졌을 때, 행..
문제 문제 설명 그린닷컴의 운영자 연두는 비밀번호를 평문 그대로 저장하는 과오를 뒤로하고, 이제부터 암호에 해시 함수를 적용해 저장하려고 한다. 연두가 아는 해시 함수라고는 알고리즘 문제 풀이에 많이 사용되는 롤링 해시 함수밖에 없기 때문에 이것을 응용하여 사용하기로 했다. 그린닷컴의 비밀번호 규칙은 꽤 특이한데, 길이가 정확히 N이어야 하며, 비밀번호를 이루는 문자는 지정된 M개의 문자 중 하나여야 한다. 따라서, 사용 가능한 각 문자를 0부터 차례대로 정수에 대응시키면, 비밀번호를 길이가 N이고 모든 원소가 0이상 M−1이하인 배열 P=[P0,P1,…,PN−1]로 나타낼 수 있다. 이렇게 비밀번호를 배열 P로 나타낸 후, 미리 정해진 정수 A를 이용하여 다음과 같은 해시 함수 h를 적용한다. h(P)..
