분류 전체보기(97)
-
[백준/C++] 1620번 나는야 포켓몬 마스터 이다솜
문제: www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 문제풀이 이분 탐색 문제이다. 포켓몬 이름이 입력으로 들어오면 포켓몬의 번호를, 포켓몬의 번호가 입력으로 들어오면 포켓몬의 이름을 출력해야 한다. 벡터를 두 개 선언해서 하나는 포켓몬 이름을 저장하고 다른 하나는 번호와 이름을 같이 저장한다. 번호와 이름을 같이 저장한 벡터는 sort() 함수를 이용해 사전 순으로 정렬해준다. 문제에 대한 입력을 받을 때 string 형으로 ..
2021.02.06 -
[백준/C++] 11723번 집합
문제: 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..
2021.02.04 -
[백준/C++] 2108번 통계학
문제: 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(..
2021.02.04 -
[백준/C++] 2164번 카드2
문제: 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...
2021.02.03 -
[백준/C++] 10989번 수 정렬하기 3
문제: 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으로 초기화한 후 입력되는 숫자..
2021.02.03 -
[백준/C++] 1929번 소수 구하기
문제: 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은 소수가 아..
2021.02.03