1.큐2
#include <iostream>
#include <string>
#include <queue>
using namespace std;
queue<int> q;
string command;
int cnt, num;
int main()
{
cin.tie(NULL);
cin.sync_with_stdio(false);
cin >> cnt;
for (int i = 0 ; i < cnt ;i++)
{
cin >> command;
if (command == "push")
{
cin >> num;
q.push(num);
}
else if (command == "pop")
{
if (!q.empty())
{
cout << q.front() << '\n';
q.pop();
}
else
{
cout << "-1" << '\n';
}
}
else if (command == "size")
{
cout << q.size() << '\n';
}
else if (command == "empty")
{
cout << q.empty() << '\n';
}
else if (command == "front")
{
if (!q.empty())
cout << q.front() << '\n';
else
cout << "-1" << '\n';
}
else if (command == "back")
{
if (!q.empty())
cout << q.back() << '\n';
else
cout << "-1" << '\n';
}
}
return 0;
}c++내의 큐 라이브러리를 이용하여 문제를 해결했다 cin을 통해 command를 입력받아 해당하는 명령을 호출해줬다 계속 시간초과가 발생하는 문제가있었는데 cout시 endl은 시간이 오래걸려 '\n'을 사용해서 해결하였다.
덧붙여 큐란 FIFO형식의 자료구조로 먼저 들어간것이 먼저 나오는 구조를 가지고있다.
큐는 주로 데이터가 들어온 시간순서대로 처리되어야할때 사용된다.
2.카드2
#include <iostream>
#include <queue>
using namespace std;
queue<int> q;
int num;
int main()
{
cin.tie(NULL);
cin.sync_with_stdio(false);
cin >> num;
for (int i = 1; i <= num; i++)
{
q.push(i);
}
while (q.size() != 1)
{
q.pop();
q.push(q.front());
q.pop();
}
cout << q.front() << '\n';
}1부터 num까지 큐에 집어넣은후 q.size가 1이될때까지 맨 앞의 데이터를 팝하고 그 다음 데이터를 뒤로 넣어주는곳을 반복한다 마지막으로 q.front를 출력하면 답을 알수있다.
3.요세푸스문제0
#include <iostream>
#include <queue>
using namespace std;
queue<int> q;
int num,k;
int main()
{
cin.tie(NULL);
cin.sync_with_stdio(false);
cin >> num;
for (int i = 1; i <= num; i++)
{
q.push(i);
}
cin >> k;
cout << '<';
while (!q.empty())
{
for (int i = 0; i < k - 1; i++)
{
q.push(q.front());
q.pop();
}
cout << q.front();
q.pop();
if (!q.empty())
cout << ", ";
}
cout << ">" << '\n';
}우선 num까지 데이터를 큐에 집어넣는다 다음 k를 입력받은뒤 반복문을 통해 q.empty 일때까지 수행을 반복한다 수행은 반복문을통해 k-1번 q.front()를 푸쉬해주고 팝해준다 다음 front를 출력해주고 팝해주면 k번째의 숫자를 출력할수있다 다음 마지막일경우가 아닐땐 ,출력해준다 마지막으로 >을 출력해서 답의 양식을 맞춰주면된다.
4.프린터 큐
#include <iostream>
#include <queue>
using namespace std;
int main()
{
int count;
int test_case,num,m,printer;
cin >> test_case;
while (test_case--)
{
cin >> num >> m;
count = 0;
queue<pair<int, int>> q;
priority_queue<int> pq;
for (int i = 0; i < num; i++)
{
cin >> printer;
q.push({ i,printer });
pq.push(printer);
}
while (!q.empty())
{
int index = q.front().first;
int value = q.front().second;
q.pop();
if (pq.top() == value)
{
pq.pop();
++count;
if (index == m)
{
cout << count << '\n';
break;
}
}
else
q.push({ index,value });
}
}
return 0;
}해당문제는 우선순위큐를 사용해 쉽게 해결할수있다 값을 인덱스와같이 저장하는 일반큐와 우선순위큐에 각각 집어넣어 일반큐를 푸쉬팝하고 이때 우선수위 큐의 정렬된 값과 같다면 출력해주는것이다
우선 값 printer를 큐와 우선순위큐에 넣어준다 이때 큐에는 인덱스까지 페어로 넣어준다
다음 q.empty일때 까지 반복한다
index,value의 q.front의 값을 넣어주고 pop한다( 우선순위 큐의 값과 일치하지않을경우 뒤로 다시 넣어주기위함)
다음 우선순위의 큐에의해 내림차순으로 정렬되었기떄문에 우선순위큐에는 가장 큰값의 printer가 들어있을것이다 이값이 value와 같다면 해당 우선순위이므로 우선순위큐에서도 팝을 해주고 count++를 해준다 이때 만약 처음 입력해준 인덱스가 m과 같다면 원하는 값이 출력된것이므로 count를 출력해주면된다 아닐경우엔 값을 다시 큐에넣고 다음 우선순위에 맞는 값을 출력할때까지 반복하면 된다.
5.덱
#include <iostream>
#include <deque>
#include <string>
using namespace std;
deque<int> d;
int main(void)
{
int count,num;
string command;
cin >> count;
while (count--)
{
cin >> command;
if (command == "push_front")
{
cin >> num;
d.push_front(num);
}
else if(command == "push_back")
{
cin >> num;
d.push_back(num);
}
else if (command == "pop_front")
{
if (!d.empty())
{
cout << d.front() << '\n';
d.pop_front();
}
else
cout << "-1\n";
}
else if (command == "pop_back")
{
if (!d.empty())
{
cout << d.back() << '\n';
d.pop_back();
}
else
cout << "-1\n";
}
else if (command == "size")
{
cout << d.size() << '\n';
}
else if (command == "empty")
{
cout << d.empty() << '\n';
}
else if (command == "front")
{
if (!d.empty())
{
cout << d.front() << '\n';
}
else
cout << "-1\n";
}
else if (command == "back")
{
if (!d.empty())
{
cout << d.back() << '\n';
}
else
cout << "-1\n";
}
}
}c++내의 라이브러리를 이용해 덱을 구현해보는 문제였다 큐와 같은 방식으로 command를 입력받아 구현을 진행했다.
덱은 앞으로 삭제를 하고 뒤에서 입력을 받는 큐와는 달리 앞뒤 모두에서 출력과 입력을 진행할수있다.
- AC
#include <iostream>
#include <deque>
#include <string>
using namespace std;
int main()
{
cin.sync_with_stdio(false);
cin.tie(0);
int cnt;
cin >> cnt;
while (cnt--)
{
string command;
string parse;
deque<int> d;
int len,num = 0;
bool error = false;
bool reverse = false;
cin >> command;
cin >> len;
cin >> parse;
for (int i = 0; i < (signed)parse.length(); i++)
{
if (parse[i] == '[')
{
continue;
}
else if (parse[i] == ',' || parse[i] == ']')
{
if (len != 0)
{
d.push_back(num);
num = 0;
}
}
else if (parse[i] >= '0' && parse[i] <= '9')
{
num = num *10 + parse[i] - '0';
}
}
for(int i = 0; i < (signed)command.length() ; i++)
{
if (command[i] == 'R')
{
reverse = !reverse;
}
else if (command[i] == 'D')
{
if (!d.empty())
{
if (!reverse)
d.pop_front();
else
d.pop_back();
}
else
{
error = true;
break;
}
}
}
if (error == true)
{
cout << "error\n";
}
else
{
cout << "[";
while (!d.empty())
{
if (!reverse)
{
cout << d.front();
d.pop_front();
if (!d.empty())
cout << ',';
}
else
{
cout << d.back();
d.pop_back();
if (!d.empty())
cout << ',';
}
}
cout << "]\n";
}
}
}문제를 해결하는 핵심요소는 R명령어가 들어왔을때 정말로 함수를 뒤집는것이 아닌 bool변수 reverse를 사용해 현재 덱이 반전된 상태인지 아닌지를 구분해주는것이 R이 들어올때마다 배열을 뒤집는다면 매우 비효율적이고 시간이 많이 소모 될것이다 여기서 덱의 장점인 앞과 뒤에서 모두 팝이 가능 하다는 점을 이용해 reverse = false 일경우에는 뒤집히지 않은경우 이므로 출력과 pop을 front해서 해주고 true일때는 반대인 false에서 해주는것이다
먼저 테스트케이스의 갯수를 받아 반복문을 통해 반복하고 각 테스트케이스는 command,len,parse를 받는다 command는 앞에서부터 하나씩 R과D일경우 명령을 실행해줄것이고 len은 0일때를 확인해 parse를 파싱할때 빈배열일경우를 그냥 넘겨줄것이다
먼저 parse에는 [1,2,3] 이런식으로 [,]과 숫자로 구성된 문자열이 들어왔을것이다 여기서 우리는 덱 D에 정수만을 파싱해서 넣어줘야하므로 [일경우는 컨티뉴 ,] 경우에는 저장된 num값을 덱에 넣어준다 여기서 len이 0인경우는 아무것도 들어올것이없는경우이므로 예외처리해준다
0~9사이의 숫자가 들어온경우는 몇자리숫자인지 알수없으므로 다음 숫자가 나올때까지 num값에 기존값을 한자리 올려주며 저장해준다 여기까지 파싱이 완료되었고
다음 command를 앞에서부터 탐색하여 R인경우엔 reverse = !reverse해주고 넘어간다 D일경우엔 위에 설명한바와같이 reverse에따라 pop해준다 여기서 만약 D가 이미 비어있다면 error변수를 true로 만들어주고 반복문을 탈출한다.
마지막으로 출력에서 error변수가 true인상태라면 error를 출력해주고 아니라면 reverse에따라 정순 혹은 역순으로 덱의 인자들을 하나씩 pop해서 출력해준다.
8.피보나치수 6
#include <iostream>
using namespace std;
typedef long long ll;
const long long M = 1000000007;
void matrix_multi(ll a[2][2], ll b[2][2])
{
ll temp[2][2] = { { 0,0 }, { 0,0 } };
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < 2; j++)
{
for (int k = 0; k < 2; k++)
{
temp[i][j] += a[i][k] * b[k][j];
}
temp[i][j] %= M;
}
}
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < 2; j++)
{
a[i][j] = temp[i][j];
}
}
}
int main()
{
ll m[2][2] = { {0,1}, {1,1} };
ll ans[2][2] = { {1,0}, {0,1} };
long long num;
cin >> num;
while (num > 0)
{
if (num % 2 == 1)
{
matrix_multi(ans, m);
}
matrix_multi(m, m);
num /= 2;
}
cout << ans[0][1] << endl;
return 0;
}피보나치수를 분할정복을 통해 구하는 문제이다 n이 매우크기때문에 이전문제에서 해결한 브루트포스 동적계획으로는 문제를 해결할수 없다.
우선 기본적인 알고리즘 피보나치를 행렬을 통해 구현하는것이다 {{0,1},{1,1} } = {{f(n-1),fn},{fn,f(n+1)} 이고 이를 제곱하면 다음 피보나치를 구할수있다 이를 분할정복을 통해 구현하는것이다.
우선 원하는 num은 매우 큰수이므로 모든 자료형은 long long을 사용한다 다음 단위행렬 ans를 선언하고 이를 정답행렬로 사용한다 다음 num/2하며 ans에 행렬 제곱을 하면 ans[0][1]은 f(num)이 되므로 이를 출력해주면 정답이다.
