궤도

문제 풀이 1년 반전에 자료구조 시간에 이미 배운 문제라...풀이 방법도 그때에서 전혀 달라지지 않았다. 이게 정석이기도 하구 스택에 연산자를 쌓다가 적절한 때에 출력하는게 중요한데, 여기에 연산자 우선순위를 사용한다. 다들 알겠지만 연산자의 우선순위는 괄호, 곱셈나눗셈, 덧셈뺄셈이다. 그리고 스택에 연산자를 쌓을 건데 절대로 나보다 우선순위가 높거나 같은 연산자 위에 쌓일 수는 없다. 그니까 곱셈이 이미 스택에 들어온 상태에서 덧셈이 들어오려 한다면 곱셈이 스택에서 나와야 한단 것이다. 피연산자인 A~Z는 스택에 쌓이지 않는다. 그냥 간단히 말해서 우선순위가 그 어떤 연산자보다 높다고 생각하는게 맘 편할 수도 있겠다. 그래서 이 2가지 규칙 1. 스택에 쌓이는건 오직 연산자 2. 나보다 우선순위가 높은..

문제 풀이 이 문제의 핵심은 커서 위치 정보를 따로 저장하지 않은 채 문제를 푸는 것이다. 그러려면 스택을 2개 사용해야 한다. s1에 입력을 char 단위로 쪼개어 넣었다. 커서는 처음에 문장 맨 뒤에 위치한다. 이때 커서의 왼쪽 문자는 d고 이는 s1.top과 일치한다. 그럼 각 명령에 대해 해야할 일은 무엇일까? L d를 가리키던 커서가 c를 가리키도록 해야한다. s1.top이 c가 되기 위해선 d가 없어져야 한다. 하지만 d를 완전히 없앨 수는 없다. 그래서 d를 s2에 옮겨준다. D c를 가리키던 커서가 다시 d를 가리키도록 해야한다. 그럼 s1.top이 다시 d가 되어야 한다는 것이다. s2.top에 있던 d를 다시 s1으로 옮겨온다. B 현재 커서의 왼쪽 문자를 지워야 한다. 이는 s1.to..

문제 풀이 이중 for문을 쓰면 아주 쉬운데...시간제한때문에 시간복잡도를 줄여야한다. 이 문제를 푸는 아이디어는 오큰수를 구하지 못한 수를 스택에 저장하는 것이다. 더 자세하게 말하자면 오큰수를 구하지 못한 수의 인덱스를 스택에 저장하면 되겠다. 오큰수를 구하지 못한 수(A)를 스택에 저장하고, 그 뒤로 입력되는 수(B)에 대해 B가 A의 오큰수가 될 수 있는지 확인한다. 될 수 있다면 배열의 A 인덱스 값을 B로 바꿔준다. 마지막까지 스택에 남아있는 수는 오큰수를 구하지 못한 것이므로 -1로 바꿔준다. 소스코드 #include #include using namespace std; int num_arr[1000000]; void oaken(int length) { stack index; //오큰수를 구..

문제 풀이 스택과 만들어야할 수열이다. 스택에는 1~8까지 순서대로 들어올 것이다. 1 2 3 4를 순서대로 스택에 쌓다보니 수열의 첫번째 숫자인 4를 만났다. pop 해주자. 마침 그 다음이 3이니 한번 더 pop해주자. 다시 5부터 push하자. 6을 만나서 pop했다. 입력 예제 2번은 직접 해보시길 1 2 5까지만 만들어질 것이다. 소스코드 #include #include #include using namespace std; void isStack(vector arr) { int index = 1; stack s; vector pm; for (int i = 0; i < arr.size(); i++) { while (index input; arr.push_back(input); } isStack(a..

문제 풀이 myunji.tistory.com/236 [백준] 9012번 : 괄호 문제 풀이 스택 문제에는 나혼자 정했지만 아마 일반화도 가능할 듯한 네임드 문제 2개가 있다. 후위표기법 사칙연산과 괄호 맞추기다. 유명한 문제들이니만큼 풀이법도 세뇌수준으로 들어서 myunji.tistory.com 이 문제의 응용판이다. 사실 이 문제에서 제일 어려운건 입력을 처리하는 것이다. 괄호야 뭐...왼쪽 괄호 나오면 스택에 쌓고 오른쪽 괄호 나오면 짝 맞는지 확인해서 pop하면 그만이다. 그럼 띄어쓰기가 있는 입력을 어떻게 처리할지 살펴보자. 소스코드 #include #include #include using namespace std; void bracket(string input, int length) { sta..

문제 풀이 스택 문제에는 나혼자 정했지만 아마 일반화도 가능할 듯한 네임드 문제 2개가 있다. 후위표기법 사칙연산과 괄호 맞추기다. 유명한 문제들이니만큼 풀이법도 세뇌수준으로 들어서 툭 건드리면 툭 나올만큼 외웠다. 왼쪽 괄호가 나오면 스택에 넣고(push) 오른쪽 괄호가 나오면 pop하는데 pop을 하려할 때 이미 스택이 비어있거나, 문자열의 끝까지 탐색을 완료했는데 스택이 비어있지 않으면 올바른 괄호 문자열이 아니다. 자세한 설명을 원한다면...나보다 훨씬 잘 설명한 블로그가 정말 많다. 그만큼 유명한 문제라는 것이다. 소스코드 #include #include #include using namespace std; void bracket(string input, int length) { stack s;..

문제 풀이 입력을 계속 스택에 push로 쌓다가 0을 만나면 pop해주면 되겠다. 입력이 끝나면 스택에 남아있는 모든 수를 더해주자. 소스코드 #include #include using namespace std; int main() { int K, input, sum = 0; stack s; cin >> K; for (int i = 0; i > input; if (input == 0) //0이면 가장 위에 있던 수 pop으로 뺌 s.pop(); else s.push(input); } while (!s.empty()) { //스택에 쌓인 모든 수 더해줌 sum += s.top(); s.pop(); } cout

문제 본문 과거 자료구조 수업시간에 C로 스택을 하나하나 정성스레 구현하던 때가 떠오른다. 그때 C++을 잘 모르던 때인데 다행이라고 생각한다. 만약 알고 있었다면 한줄로 해결할 수 있는걸 하나하나 작성하느라 홧병이 나서 죽었을 테니까... C++의 표준 템플릿 라이브러리(STL)중에는 스택이 있다. 그전에 스택이 뭔지 모를 수 있으니 간략히 설명하면 LIFO(Last In First Out) 형식의 자료구조이다. 이 문제는 스택의 기본 사용법을 배우는 그런 문제라고 볼 수 있겠다. www.cplusplus.com/reference/stack/stack/?kw=stack stack - C++ Reference container_typeThe second template parameter (Containe..