문제: www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제풀이 처음 문제를 접근한 방식은 N 크기의 배열을 만든 후 sort() 함수를 이용해 배열을 정렬 후 출력하려고 했다. 하지만 문제가 요구하는 최대 메모리의 크기는 8MB이기 때문에 메모리 초과로 정답을 맞히지 못했다. 다시 문제를 살펴보고 입력되는 숫자가 "10,000보다 작거나 같은 자연수" 인 것을 확인하고 배열 인덱스를 이용하여 문제를 풀었다. 10,000 크기의 배열을 선언, 0으로 초기화한 후 입력되는 숫자..

문제: www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 문제풀이 처음 문제를 풀 땐 브루트 포스로 문제를 풀었다. 하지만 범위가 1 ≤ M ≤ N ≤ 1,000,000 으로 큰 숫자여서 시간 초과가 나왔다. 이 문제는 "에라토스테네스의 체" 라는 알고리즘으로 풀어야 한다. 입력 범위만큼 배열을 선언하고 숫자 2부터 해당 숫자를 제외한 배수를 인덱스로 가지고 있는 배열을 1로 초기화한다. 배열 크기만큼 반복한 후 배열에 0이 있으면 해당 배열의 인덱스를 출력한다. 이때, 숫자 1은 소수가 아..

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