쌓고 쌓다

https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net #include using namespace std; int N, M; int parent[1000001]; int find(int a) { if (parent[a] == a) return a; return parent[a]=find(parent[a]); } void Union(int a, int b) { a = find(parent[a]); b = find(parent[b]); if (a ..

https://www.acmicpc.net/problem/1935 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net 전체 코드 #include #include using namespace std; stack s; string str; int arr[26]; int N; double cal(char c) { double op1, op2; op2 = s.top(); s.pop(); op1 = s.top(); s.pop(); switch (c) { case '+': return op1 + op2; case..

큐(Queue) : FIFO(First In First Out) 구조로, 먼저 들어온 데이터가 먼저 나가는 자료구조이다. 선형 큐의 문제점 사용하며 front, rear 값이 계속 증가하여 앞부분이 비어있음에도 불구하고 더 이상 삽입이 불가능한 경우가 생긴다. 위와 같은 공간 낭비가 이루어 진다. 위의 문제를 해결하기 위해 요소를 계속 이동시켜 줄 수도 있지만 비효율적이다. 해결방법 : 원형 큐를 구현해 사용하자. 변수 #define MAX_SIZE 10 typedef int element; typedef struct { element queue[MAX_SIZE]; int front; int rear; }QueueType;​ front : 첫 번째 요소의 하나 앞의 인덱스이다. ( 초기값 : 0 ) re..

https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 후위 표기식으로 바꾸는 방법은 저번에 작성했었다. 저것을 참고... 설명 -> https://non-stop.tistory.com/91 전체 코드 #include #include using namespace std; string str; int prec(char ch) { switch (ch) { case '+': case '-': return 1; case '*': case '/': retu..

문자열을 탐색하는데 피연산자(숫자)라면 스택에 그냥 저장해줍니다. 연산자라면 피연산자가 2개 필요하겠죠? 스택에서 피연산자 2개를 꺼냅니다. 먼저 꺼낸 것은 op2 ( 연산자 뒤에 쓸 피연산자) 2번째로 꺼낸것은 op1 ( 연산자 앞에 쓸 피연산자)입니다. op1, op2를 연산자로 계산하여 스택에 넣어줍니다. 연산자가 / 라면 op1/op2를 스택에 넣어줍니다. 이 과정을 문자열 끝까지 실행 시 스택에는 결괏값만 남아 있을 것입니다. 전체 코드 #include #include using namespace std; int solve(string str) { stack s; int idx = 0; while (idx < str.length()) { char ch = str[idx]; if (ch != '+..

피연산자(숫자)를 만난다면 그냥 바로 피연산자를 출력해준다. 연산자를 만난다면 스택에 넣을 것이다. 그런데, 우선순위가 항상 높은 것이 스택의 맨 위에 있도록 스택을 유지하게 넣을 것이다. ( 우선순위가 같다면 먼저 스택에 있던 연산자가 먼저 출력해주는게 맞다 그러므로 같아도 출력해주며 pop해줄것이다.) 왼쪽 괄호 '(' 는 스택에 바로 넣어줄 것이다. ( 우선순위를 제일 낮게 설정 ) 오른쪽 괄호 ')' 는 '(' 가 스택에 맨 위에 있을 때까지 스택 안의 연산자들을 출력하면서 pop을 해줄 것이다. 모든 과정을 문자열 끝까지 한 후 스택에 남아있는 연사자들을 모두 출력해준다. 중위 표기법 후위 표기법 1+3*8 138*+ 전체 코드 #include #include using namespace std..

[(()){}{}] 와 같은 괄호가 있다. 이 괄호가 올바른지 확인하는 방법으로 스택을 사용한다. 여는 괄호는 스택에 그냥 넣어주면 된다. 닫는 괄호에서는 스택을 열어봐서 비교해봐야 한다. 현재 닫는 괄호가 ')'일 경우 스택의 맨 위 요소는 '(' 여야만 한다. 아니라면, 괄호 짝이 안 맞아 괄호를 닫을 수가 없다... 그래서 닫는 괄호가 나올 때마다 스택의 맨 위 요소가 짝이 맞는지 확인을 해주어야 한다. 짝이 맞다면 닫는 괄호를 push 하지 말고 스택의 맨 위(확인한 여는 괄호)를 pop 해준다. 이 과정을 문자 하나하나 돌면서 문자열 끝까지 한다. 괄호가 올바르다면 스택에는 아무것도 없어야 한다. 왜냐하면, 다들 짝을 맞춰 pop을 했을 테니 소스 코드 #include #include using..

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 전체 코드 #include #include #include using namespace std; int N; int arr[1000001]; int res[1000001]; stack s; // 번호와 등장횟수 vector v; void solve() { //첫 시작은 무조건 오큰수가 없음. s.push(make_pair(v[N - 1], arr[v[N - 1]])); res[N - 1] = -1; for(i..