Doby's Lab

https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 이번 문제는 학교에서 자료구조 과제로 나왔던 키워드이지만 그 당시에 안 했어서 이번 기회에 구현을 해보려 했다. 솔루션 [1] 식을 문자열로 받아서 피연산자인지 연산자인지 구분을 한다. [2] 연산자나 괄호를 스택에 우선순위로 처리해야 하는 *, / 의 조건과 +, -의 조건, (, ) 두 괄호의 조건을 따로따로 처리를 해줘야 한다. A+B*C 다음 경우를 예로 들어보자. 답으로는 ABC+*가..

https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 이번 문제 또한 스택을 사용해야 할 거 같다는 확신이 들었다. 하지만, 스택을 이용해서 트릭을 만들어낼 수 있는 능력이 이번 문제의 포인트다. 솔루션 "IOIOI"라는 문자열에 n이 1이라면 답은 2가 출력되어야 한다. 내가 만든 트릭은 첫 "IOI"가 발생할 때, 이를 스택에 담고 n이 1인 경우를 만족시켰으므로 하나를 coun..

(이번 문제는 첫 골드 문제이다 (울컥)) 이번 문제의 유형이 'Monotonic Stack'이라고 하는데 이 유형의 문제를 처음 접한 것은 아니다. 예전 SCPC 준비를 할 때, 같이 준비하던 친구들과 영어 문제를 풀면서 접했었던 경험이 있다. 많은 시간을 썼었지만 풀리지 않았었고, 해답을 찾다가 Monotonic Stack에 대한 자료가 많이 없어서 나중에 또 이런 유형을 만나게 되면 정리를 해둬야겠다고 생각했었다. (해당 영어문제 링크) https://www.acmicpc.net/problem/6105 6105번: Look Up Farmer John's N (1 a; arr.push_back(a); } vector answer(n, 0); stack s; for (int i = arr.size() ..