Seondalgorithm

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/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/4889 4889번: 안정적인 문자열 입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가 2000을 넘는 경우 www.acmicpc.net 문제 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 여기서 안정적인 문자열을 만들기 위한 최소 연산의 수를 구하려고 한다. 안정적인 문자열의 정의란 다음과 같다. 빈 문자열은 안정적이다. S가 안정적이라면, {S}도 안정적인 문자열이다. S와 T가 안정적이라면, ST(두 문자열의 연결)도 안정적이다. {}, {}{}, {{}{}}는 안정적인 문자열이지만, }{, {{}{, {}{는 ..

https://www.acmicpc.net/problem/18115 18115번: 카드 놓기 수현이는 카드 기술을 연습하고 있다. 수현이의 손에 들린 카드를 하나씩 내려놓아 바닥에 쌓으려고 한다. 수현이가 쓸 수 있는 기술은 다음 3가지다. 제일 위의 카드 1장을 바닥에 내려놓는다. www.acmicpc.net 문제 수현이는 카드 기술을 연습하고 있다. 수현이의 손에 들린 카드를 하나씩 내려놓아 바닥에 쌓으려고 한다. 수현이가 쓸 수 있는 기술은 다음 3가지다. 제일 위의 카드 1장을 바닥에 내려놓는다. 위에서 두 번째 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다. 제일 밑에 있는 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다. 수현이는 처음에 카드 N장을 들고 있다..

https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 문제 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램..