문제: www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 문제풀이 간단한 구현문제 코드 #include #include using namespace std; vector v(20); //크기 20의 전역 벡터 선언 void add(int); void remove(int); void check(int); void toggle(int); void all(); void empty(); int main(){ ios::sync_with_stdio(false); cin.tie(NULL); int M; ci..

문제: www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 문제풀이 산술평균, 중앙값, 최빈값, 범위를 코드로 구현하는 문제였다. 입력되는 숫자의 절댓값이 4000 이하이므로 8001 크기의 배열을 선언하여 배열 인덱스를 이용해 문제를 풀었다. (해당 숫자의 개수 기록) 1. 산술평균 산술평균은 숫자의 개수와 인덱스에서 4000을 뺀 수의 곱을 모두 합쳐 N으로 나누었다. 이때 문제에서 요구하는 조건은 소수점 첫째 자리에서 반올림한 값이다. 때문에 N을 double형으로 형 변환한 후 round(..

문제: www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제풀이 큐 문제이다. C++ STL queue를 이용하여 문제를 풀었다. 코드 #include #include using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(NULL); int N; cin>>N; queue q; for(int i=1; i 1){ 큐에 값이 하나가 남을 때까지 반복 q.pop(); //제일 앞장을 버리고 q...

문제: 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..