테이블 해시 함수
문제 링크 : 테이블 해시 함수
문제 설명
완호가 관리하는 어떤 데이터베이스의 한 테이블은 모두 정수 타입인 컬럼들로 이루어져 있습니다. 테이블은 2차원 행렬로 표현할 수 있으며 열은 컬럼을 나타내고, 행은 튜플을 나타냅니다. 첫 번째 컬럼은 기본키로서 모든 튜플에 대해 그 값이 중복되지 않도록 보장됩니다. 완호는 이 테이블에 대한 해시 함수를 다음과 같이 정의하였습니다.
- 해시 함수는 col, row_begin, row_end을 입력으로 받습니다.
- 테이블의 튜플을 col번째 컬럼의 값을 기준으로 오름차순 정렬을 하되, 만약 그 값이 동일하면 기본키인 첫 번째 컬럼의 값을 기준으로 내림차순 정렬합니다.
- 정렬된 데이터에서 S_i를 i 번째 행의 튜플에 대해 각 컬럼의 값을 i 로 나눈 나머지들의 합으로 정의합니다.
- row_begin ≤ i ≤ row_end 인 모든 S_i를 누적하여 bitwise XOR 한 값을 해시 값으로서 반환합니다.
테이블의 데이터 data와 해시 함수에 대한 입력 col, row_begin, row_end이 주어졌을 때 테이블의 해시 값을 return 하도록 solution 함수를 완성해주세요.
제한 사항
- 1 ≤ data의 길이 ≤ 2,500
- 1 ≤ data의 원소의 길이 ≤ 500
- 1 ≤ data[i][j] ≤ 1,000,000
-> data[i][j]는 i + 1 번째 튜플의 j + 1 번째 컬럼의 값을 의미합니다. - 1 ≤ col ≤ data의 원소의 길이
- 1 ≤ row_begin ≤ row_end ≤ data의 길이
입출력 예
| data | col | row_begin | row_end | result |
|---|---|---|---|---|
| [[2,2,6],[1,5,10],[4,2,9],[3,8,3]] | 2 | 2 | 3 | 4 |
풀이 방법
- 문제가 특별한 이해를 요구한다기보다는 1~4번까지의 과정을 구현하는 것에 초점이 맞춰져 있는 것으로 보여서 1~4번까지의 과정을 구현하는 것을 목적으로 문제를 풀었다.
- 2번 과정은 알고리즘 헤더에
sort()함수를 통해 직접 compare를 구현해서 풀 것이고, 3~4번 과정은 row_begin부터 row_end까지의 행을 각각 계산하면서 bitwise XOR 연산을 하면 될 것으로 보인다.
-> 2번 과정은 N이 데이터 길이일 때,O(N*logN)만큼의 시간복잡도가 걸릴 것으로 추정되고, 3, 4번 과정은 (row_end - row_begin) * data의 원소 길이만큼의 시간복잡도로O(N*d)가 걸릴 것으로 추정되기 때문에 총O(N*(logN+d))의 시간복잡도가 걸릴 것으로 추정되고 여기서 N은 최대 2,500이고 d는 최대 500이기 때문에 충분히 알맞은 알고리즘으로 보인다.
구현
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<vector<int>> data, int col, int row_begin, int row_end) {
int answer = 0;
// 정렬
sort(data.begin(), data.end(), [col](vector<int> a, vector<int> b){
if(a[col - 1] == b[col - 1]){
return a[0] > b[0];
}
return a[col - 1] < b[col - 1];
});
// i번째 행의 튜플에 대해 각 값을 i로 나눈 나머지의 합을 구하기
for(int i = row_begin - 1; i <= row_end - 1; i++){
int sum = 0;
for(int j = 0; j < data[i].size(); j++){
sum += data[i][j] % (i + 1);
}
// bitwise XOR 연산
answer = answer ^ sum;
}
return answer;
}하노이의 탑
문제 링크 : 하노이의 탑
문제 설명
하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.
- 한 번에 하나의 원판만 옮길 수 있습니다.
- 큰 원판이 작은 원판 위에 있어서는 안됩니다.
하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.
1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로 최소로 옮기는 방법을 return하는 solution를 완성해주세요.
제한 사항
- n은 15이하의 자연수 입니다.
입출력 예
| n | result |
|---|---|
| 2 | [[1,2],[1,3],[2,3]] |
풀이 방법
- 하노이의 탑의 경우, 매우 유명하다.
- 중간과정은 모르겠지만, (1)결국 가장 밑에 있는 것을 제외하고 그 위에 것들을 마지막 지점이 아닌 곳에 놔두고, (2)가장 밑에 있는 것을 마지막 지점에 놔두고, (3)가장 밑에 있던 것을 제외한 나머지를 마지막 지점에 놔두면 되는 과정을 통해 풀었다.
-> 시간복잡도는O(2^N)만큼이 걸릴 것으로 추정되고, N의 최대가 15기 때문에 알맞은 알고리즘으로 보인다.
구현
#include <string>
#include <vector>
using namespace std;
void hanoi(int n, int start, int end, int via, vector<vector<int>>& answer){
if(n == 1){
answer.push_back(vector<int>{start, end});
return;
}
hanoi(n - 1, start, via, end, answer);
answer.push_back(vector<int>{start, end});
hanoi(n - 1, via, end, start, answer);
}
vector<vector<int>> solution(int n) {
vector<vector<int>> answer;
hanoi(n, 1, 3, 2, answer);
return answer;
}
게임 개발자를 향해..