Doby's Lab

이번 문제 논리는 굉장히 어려울 줄 알았다. 어떻게든 솔루션을 발견하려고 각 값의 연관성을 찾으려 했다. 그 결과 TC에서 논리를 찾을 수 있었다. Input 10 12 3 9 Output 33 10과 12 즉, M과 N의 차이는 +2다. x와 y의 차는 +6이다. 이를 보고, +6은 +2의 3배니까 3바퀴 정도 돌면 차이가 3배만큼 벌어질 거 같다는 생각에 10을 기준으로 3바퀴를 돌려보니 30과 30 각각의 M과 N으로 나눈 나머지는 0과 6이 나온다. (정확히 말하면 10은 3바퀴, 12는 2바퀴 돌고 6번의 해가 지난 것이다.) 여기서 3번의 해가 더 지나면 3 9가 x, y값과 일치하면서 맞아떨어진다. (10을 기준으로 3바퀴 돌렸으므로) 10 * 3 + (3번의 해가 지났으므로) 3 = 33 ..

이번 문제는 50점과 100점으로 나뉘어 채점을 하게 되며 계속해도 100점이 나오지를 않았다. 해싱의 개념과 Mod의 연산을 알아보며 풀어보자. 개념 해싱(Hashing)이란 데이터를 관리하는 비법으로 이분 탐색 혹은 다른 탐색보다 시간 복잡도를 O(1) 안에서 해결할 수 있다. 어떠한 데이터를 저장하려 할 때 그 데이터를 보관하는 곳을 해시 테이블(Hash Table)이라고 한다. 그리고 각 버킷(bucket, 각 행)이 고유한 주소를 가지게 되는데 데이터를 해시 함수(Hash Function)를 통해 데이터를 주소 값으로 바꾸어서 해시 테이블에 저장한다. 각 버킷에 얼마큼 저장할 수 있는 지를 알 수 있는 곳이 슬롯(slot, 각 열)이다. 한 슬롯에 계속 데이터가 들어오면 이를 충돌(Hash Co..