Seondalgorithm

https://www.acmicpc.net/problem/1655 문제백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.입력첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이..

https://www.acmicpc.net/problem/4358 문제생태학에서 나무의 분포도를 측정하는 것은 중요하다. 그러므로 당신은 미국 전역의 나무들이 주어졌을 때, 각 종이 전체에서 몇 %를 차지하는지 구하는 프로그램을 만들어야 한다.입력프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어진다.출력주어진 각 종의 이름을 사전순으로 출력하고, 그 종이 차지하는 비율을 백분율로 소수점 4째자리까지 반올림해 함께 출력한다. 풀이문제 풀이보다 입출력이 더 까다로운 문제 C++에서 출력 소숫점을 고정하는 법cout  C++에서 소수점 아래 n개 숫자를..

https://www.acmicpc.net/problem/25192 문제 알고리즘 입문방 오픈 채팅방에서는 새로운 분들이 입장을 할 때마다 곰곰티콘을 사용해 인사를 한다. 이를 본 문자열 킬러 임스는 채팅방의 기록을 수집해 그 중 곰곰티콘이 사용된 횟수를 구해 보기로 했다.ENTER는 새로운 사람이 채팅방에 입장했음을 나타낸다. 그 외는 채팅을 입력한 유저의 닉네임을 나타낸다. 닉네임은 숫자 또는 영문 대소문자로 구성되어 있다.새로운 사람이 입장한 이후 처음 채팅을 입력하는 사람은 반드시 곰곰티콘으로 인사를 한다. 그 외의 기록은 곰곰티콘을 쓰지 않은 평범한 채팅 기록이다.채팅 기록 중 곰곰티콘이 사용된 횟수를 구해보자!입력첫 번째 줄에는 채팅방의 기록 수를 나타내는 정수 N$N$ 이 주어진다. (1≤N..

https://www.acmicpc.net/problem/1822 문제몇 개의 자연수로 이루어진 두 집합 A와 B가 있다. 집합 A에는 속하면서 집합 B에는 속하지 않는 모든 원소를 구하는 프로그램을 작성하시오.입력첫째 줄에는 집합 A의 원소의 개수 n(A)와 집합 B의 원소의 개수 n(B)가 빈 칸을 사이에 두고 주어진다. (1 ≤ n(A), n(B) ≤ 500,000)이 주어진다. 둘째 줄에는 집합 A의 원소가, 셋째 줄에는 집합 B의 원소가 빈 칸을 사이에 두고 주어진다. 하나의 집합의 원소는 2,147,483,647 이하의 자연수이며, 하나의 집합에 속하는 모든 원소의 값은 다르다.출력첫째 줄에 집합 A에는 속하면서 집합 B에는 속하지 않는 원소의 개수를 출력한다. 다음 줄에는 구체적인 원소를 빈..

https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다..

https://www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 풀이 각 숫자들의 갯수는 입력을 받는 중에 cnt 벡터를 업데이트하며 구했다 입력을 다 받은 후에는 입력에 해당하는 각 숫자와 해당 숫자의 개수를 pair로 만들어서 f 벡터에 저장해준다 이제 f벡터를 거꾸로 돌면서 스택을 이용해 오등큰수를 구해준다 스택안에 있는 숫자들은 본인보다 오른쪽에 있는 숫자이므로 해당 스택 내에서 본인의 빈도보다 더 큰 빈도를 가진 수가 나올 때까지 pop한다. 그렇게 구한 오등큰수..

https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 풀이 피연산자는 바로 답 문자열에 넣는다. 연산자는 스택에 넣어서 관리한다. 닫힌 괄호가 나오면 스택 내에 열린 괄호가 나올 때까지 스택에 있는 연사자들을 뽑아서 답 문자열에 넣는다. 연산자를 스택에 넣을 때 스택 내 연산자가 현재 연산자보다 우선순위가 높거나 같다면 스택에 있는 연산자를 다 뽑아서 답 문자열에 넣는다 #include #include using namespace std; int..

https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 풀이 자료구조 을 이용하여 풀이 #include #include using namespace std; int main() { set s; int m, n; string input; cin >> m >> n; while(m--) { cin >> input; s.insert(input); } int ans = 0; while(n--) { cin >> input; if(..

https://www.acmicpc.net/problem/20301 20301번: 반전 요세푸스 첫째 줄에 정수 $N$, $K$, $M$이 주어진다. ($1 \leq N \leq 5\ 000$, $1 \leq K, M \leq N$) www.acmicpc.net 문제 요세푸스 문제는 다음과 같다. 1$1$번 사람 오른쪽에는 2$2$번 사람이 앉아 있고, 2$2$번 사람 오른쪽에는 3$3$번 사람이 앉아 있고, 계속하여 같은 방식으로 N$N$명의 사람들이 원을 이루며 앉아 있다. N$N$번 사람 오른쪽에는 1$1$번 사람이 앉아 있다. 이제 K$K$(≤N$\leq N$)번 사람을 우선 제거하고, 이후 직전 제거된 사람의 오른쪽의 K$K$번째 사람을 계속 제거해 나간다. 모든 사람이 제거되었을 때, 제거된 ..

https://www.acmicpc.net/problem/14911 14911번: 궁합 쌍 찾기 첫째 줄에 빈 칸으로 구분된 정수가 2개 이상, 10개 이하 주어진다. 둘째 줄에는 정수가 하나 주어진다. 주어지는 정수는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 첫째 줄에 주어진 여러 개의 정수 중에서 합이 둘째 줄에 주어진 수와 같은 서로 다른 위치에 있는 두 수의 쌍을 모두 출력하고 맨 아래에 이 쌍의 개수를 이어서 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 빈 칸으로 구분된 정수가 2개 이상, 10개 이하 주어진다. 둘째 줄에는 정수가 하나 주어진다. 주어지는 정수는 100,000보다 작거나 같은 자연수이다. 출력 찾은 수의 쌍을 한 줄에 하나씩 출력하고 맨 ..