궤도

문제 풀이 대충 상상을 해보자 지금 프린터를 하려는 문서 하나를 띄워놓고 있고(front) 프린트 버튼만 누르면 되는데 이 문서보다 우선 순위가 높은 문서가 있다면 그걸 먼저 출력해야 한다. 그래서 뒤에 대기 중인 문서를 하나하나 살펴보며 우선순위를 확인하는데, 만약 이 문서보다 더 높은 순위의 문서가 있다면 다시 대기줄의 맨 뒤로 보낸다.(pop->push) 이걸 반복하면 된다. 우리가 목표로 하는 문서가 출력될 때까지. 소스코드 #include #include using namespace std; struct paper { //우선순위와 체크여부 저장 int pri; bool checked; }; bool endLoop(queue q) { //타겟 데이터가 빠지면 루프 종료 queue tmp = q;..

문제 풀이 TMI지만 고등학교 수학선생님께선 원순열을 가르치실 때 약간 과격한 비유를 사용하셨다. 뭐...총으로 쏜다거나...기절을 시킨다거나 아무튼 그 덕에 그 파트를 제대로 배우고 지금까지 기억하니 나쁘지 않았던 것 같다. 아무튼 원을 일자로 펴보고 제일 앞에 총을 든 괴한이 있다고 하자. 너무 잔인하니까 마취총이라고 하자. 이 괴한은 3(=K)번째 사람만 공격한다. 1~8(=N)명의 사람들은 두려움에 떨며 그 괴한 앞에 줄서있다. 괴한은 3번째 사람만 공격하니 1번 사람을 다시 줄 뒤로 보낼 것이다.(pop->push) 2번 사람도 다시 줄 뒤로 보내고, 3번 사람을 만났을 때 마취총을 쏠 것이다.(pop) 모든 사람이 마취총에 맞을 때까지(size=0) 진행하면 되겠다. 소스코드 #include ..

문제 풀이 1~N까지의 카드가 순서대로 있다고 한다. 제일 위에 있는 카드를 버리고(pop) 그 다음에 있는 제일 위의 카드를 제일 아래로 옮긴다.(pop->push) 이걸 카드가 1장 남을 때까지 반복한다고 한다.(size가 1이면 반복문 종료) 이대로 작성하면 된다. 소스코드 #include #include using namespace std; int main() { queue q; int N; cin >> N; for (int i = 1; i

문제 풀이 지난번에 C++의 STL중 하나인 스택을 사용해봤다. 이번에는 큐다. 큐는 FIFO(First In First Out)인 자료구조다. www.cplusplus.com/reference/queue/queue/?kw=queue queue - C++ Reference container_typeThe second template parameter (Container)Type of the underlying container www.cplusplus.com 소스코드 #include #include #include using namespace std; int main() { cin.tie(NULL); ios_base::sync_with_stdio(false); queue q; int N, num; str..

문제 풀이 이중 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;..