문제: www.acmicpc.net/problem/15829 15829번: Hashing APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정 www.acmicpc.net 문제풀이 해시가 무엇인지 배워보는 맛보기 문제이다. 문제의 설명대로 따라서 구현하게 되면 50점을 받게 된다. 100점이 요구하는 50 길이의 문자열은 31^50 으로 크기가 어마어마하게 커지게 된다. 그래서 이 문제를 풀려면 모듈러 연산의 성질을 알아야 한다. 모듈러 연산은 덧셈, 뺄셈, 곱셉일 때 분배 법칙이 성립한다. (나눗셈일 땐 안됨) (A+B) % MOD = (A%MOD +B%MOD) % M..

문제: www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제풀이 이진 탐색 문제이다. 배열을 정렬한 후 이진 탐색을 진행하면 된다. 코드 #include #include using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(NULL); int N; cin>>N; int A[N]; for(int i=0; i>A[i]; sort(A, A+N);..

문제: www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제풀이 숫자카드에 적혀있는 숫자의 범위가 -10,000,000 ~ 10,000,000 으로 0 포함 20,000,001 의 크기의 int형 배열을 선언했을 때 80,000,008 바이트 약 80 MB의 메모리를 사용하게 되는데 문제의 메모리 제한은 256 MB로 넉넉하기 때문에 배열의 인덱스를 이용하여 문제를 풀었다. 배열 arr[20000001] 을 0으로 초기화시키..

문제: www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 문제풀이 모든 경우의 수를 비교하는 브루트 포스 문제이다. 입력값 N의 최소 생성자를 찾아내야 하는데 나는 1부터 N까지의 수 모두 N의 생성자가 될 수 있는지 여부를 확인해보는 코드를 작성했다. N % 10 과 N /= 10 연산을 이용해 분해합의 필요한 각 자릿수의 덧셈을 하였다. 코드 #include using namespace std; int main(){ ios::s..

문제: www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 문제풀이 모든 경우의 수를 비교하는 브루트 포스 문제이다. 먼저 땅의 높이 최솟값과 최댓값을 구한 뒤 땅을 최솟값으로 평탄화할 시의 시간부터 땅을 최댓값으로 평탄화할시의 시간까지 모두 비교하여 결과를 구했다. 만일 인벤토리가 0 미만이라면 물리적으로 평탄화가 불가능하기 때문에 continue() 함수로 패스한다. 코드 #include #include using namespace std; int main..

문제: www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제풀이 이분 탐색 문제 중에서도 조건을 만족하는 값들 중 최댓값을 구하는 문제이다. (나무길이) - (벌목기 높이)의 총합 >= M 을 만족하는 벌목기 높이의 최댓값을 구해야 한다. 최댓값을 구하기 위해서 위의 조건을 만족하더라도 루프를 멈추지 않고 계속 탐색한다. 코드 #include using namespace std; int main(){ ios::sync_..