본문 바로가기
백준 #1966. 프린터 큐 큐와 우선순위 큐를 이용해 풀 수 있다. 문제에서 요구하는 index의 출력 순서를 찾아야 하므로, queue에 {문서의 우선순위 값, index} 이렇게 값을 추가해준다. 그리고 priority_queue에는 문서의 우선순위 값만 따로 넣어준다. 그래서 queue의 front().first (현재 큐의 제일 앞에 있는 문서 우선순위 값) 과 priority_queue.top (현재 가장 우선순위가 높은 문서) 를 비교해서 같으면 출력, 아니면 pop 한 뒤 다시 push해주는 형태로 문제를 풀면 된다. #include #include using namespace std; int main() { int testcase; //number of testcase cin >> testcase; int *answ..
백준 #9012. 괄호 '('와 ')'가 한 쌍을 이루는 VPS(Valid Parenthesis String)이고, 그 쌍들로만 이루어진 test case에 YES를 출력하는 문제이다. 입력받은 문자열을 stack에 넣어주고, stack의 top부터 체크한다. 그러므로 입력받은 순서가 아닌 거꾸로 체크하게 된다. 따라서 VPS가 되려면 ')'의 개수를 세는 right 변수는 항상 0 이상을 유지해야 한다. 이 문제에서 NO가 출력될 경우는 다음과 같다. 1. 입력된 test case가 홀수 개수일 때 (stack에 문자열을 넣을 필요 없이, 바로 문자열의 size를 체크한다. 문자열 길이가 홀수이면, continue를 통해 다음 test case로 넘어간다.) 2. right 변수가 음수일 때 (거꾸로 체크하므로, ( ) ) ..
백준 #11866. 조세퍼스 문제 0 큐를 이용해 풀어보았다. k번째에 해당하는 숫자는 pop이 되게 하고, k번째 숫자가 아니라면 임시 변수 tmp에 저장된 값을 pop한 다음, 다시 push해줘서 큐의 뒤로 보낸다. 주의할 점은 마지막 숫자일 경우 pop한 다음 숫자 뒤에 ", "을 출력하면 안된다는 것. //Josephus problem #include #include using namespace std; int main() { int n, k; //n: number of people, k: random positive integer queue q; cin >> n >> k; for (int i = 1; i
Google Kick Start 2019. Number Guessing Binary Search를 사용해 쉽게 구현할 수 있다. 변수가 알파벳 한 글자로 되어 있는데 (개인적으로 이런 변수 선언을 매우 싫어하지만 문제에 그렇게 나와있으니 그대로 진행...) 여러 번 반복 탐색을 통해 숫자 p가 무엇인지 맞추는 문제인데, t는 test case 개수, a와 b는 문제에서 제시하는 p의 minimum과 maximum, q는 나의 guessing이다. Kick Start에는 흥미롭게도 interactive 형식의 문제가 있다. 이 문제가 바로 그런 형식인데, Kick Start의 judging system과 내가 짠 코드가 동시에 실행되는 것이다. 쉽게 말해서, 코드에서 출력한 값을 기반으로 다시 input을 받는 형식이다. 여기서는 내가 guess한 q값이 p와 일치하면 "CO..
백준 #4344. 평균은 넘겠지 Vector를 사용해 문제를 풀어보았다. 주의할 점은 학생 수와 평균보다 높은 점수의 학생 수를 int로 설정해버리면 int / int 과정에서 비율이 정수로 떨어져버린다. 그러니 double type을 이용해야 한다. 이렇게 여러 test case가 있는 문제는 입력을 받는 for문 안에서 답을 구하는 작업까지 이루어져야 한다. 그래야 같은 변수를 재활용하면서 문제를 풀 수 있다. 그게 아니라면 배열이나 Vector 등을 사용해서 입력받은 변수들을 모두 저장해줘야 한다. Space-Time Trade Off를 볼 수 있는 부분이다. #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NU..
백준 #11650. 좌표 정렬하기 문제 링크 : https://www.acmicpc.net/problem/11650 이 문제를 해결하기 위해서는 vector와 pair를 결합해 STL sort()를 사용할 수 있다. vector를 사용하기 위해 헤더파일을, pair를 사용하기 위해 헤더파일을 include해주고 vector 변수를 하나 선언한다. 여기서 pair란 두 객체를 하나의 객체처럼 취급할 수 있는 class이다. pair p에서 첫 번째 int에 접근하려면 p.first(), 두 번째 int에 접근하려면 p.second()를 사용한다. 중요한 것은, cin을 통해 데이터를 입력받을 때 cout의 경우처럼 v[i].first 이렇게 접근할 수 없다. 해당 index가 아직 할당되지 않았기 때문! v.push_back()으로 차례차..

티스토리툴바