STL19 [C++] 백준 10866번 : 덱 https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제 풀이 덱의 기본 구현을 묻는 문제였다! 느낀 점 이번 기회에 덱을 공부할 수 있었다. 조만간 STL 컨테이너인 스택과 큐, 덱에 대해서 한번 정리글을 올려야겠다. 코드 #include #include #include using namespace std; int n, tmp; string command; deque dq; int main() { ios_base::sync_wit.. 2021. 7. 24. [C++] 백준 1966번 : 프린터 큐 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 문제 풀이 이번 문제는 idx와 중요도를 pair로 만들어서 큐에 저장하고, 중요도를 순서대로 정렬한 다른 컨테이너를 만들어서 비교하는게 중요하다. 중요도를 비교해서 맞으면 출력회수(cnt)를 늘리고 만약 m과 idx가 같다면 출력회수를 출력하고 종료한다. 느낀 점 문제를 해결하고 보니 많은 분들이 우선순위 큐를 이용하셨고 나보다 코드가 더 깔끔했다. 하지만 나는 우선순위 큐에 대해서 몰랐기 때문에 .. 2021. 7. 24. [C++] 백준 11866번 : 요세푸스 문제 0 https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 문제 풀이 요세푸스 문제에서는 k번째에 사람을 제거한다. 구현한 큐에서 k-1번 동안 front를 맨 뒤로 옮기고, k번째에 front 값을 출력한다. 큐가 비어있지 않다면 ', '를 출력해서 요구하는 출력 형식에 맞춘다! 느낀 점 그렇게 어려운 문제는 아니었지만 코드를 깔끔하게 구현하기 힘들었다. 깔끔하게 구현하기 위해서 시간을 조금 소모한 것 같다. 코드 #include #include using namespace std; int n, k; queue q; void func(i.. 2021. 7. 24. [C++] 백준 2164번 : 카드2 https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제 풀이 문제에 풀이법이 나와있다! 맨위 카드는 버리고 그 다음 카드는 맨 밑으로 넣는다. 느낀 점 어렵지 않은 문제였다. 코드 #include #include using namespace std; int n; queue q; void func(int n) { for (int i = 1; i 1) { q.pop(); q.push(q.front()); q.pop(); } cout > n; func.. 2021. 7. 24. [C++] 백준 18258번 : 큐 2 https://www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제 풀이 기본 큐 문제이다. STL에서 지원하는 컨테이너를 사용하면 쉽다! 느낀 점 이번 기회로 DS를 다시 복습하는 기분이라 만족스럽다. 코드 #include #include #include using namespace std; int n, tmp; string command; queue q; int main() { ios_base::sync_with_stdio(0);.. 2021. 7. 23. [C++] 백준 17298번 : 오큰수 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제 풀이 오큰수를 구하는 것 자체는 어렵지 않다. 하지만 이 문제에서 중요한 것은 시간 복잡도이다. 일반적인 for문을 구하면 시간 초과가 나서 스택을 활용해서 풀어야 한다. 스택의 LIFO를 이용하기 위해서 내림차순으로 쌓아준다. (Bottom은 최댓값, top은 최솟값) 스택의 top과 비교해서 arr [i] (입력받은 i번째 값) 보다 작다면 pop 해준다. 만약 스택이 비어있으면 '-1'을 저장해준다... 2021. 7. 23. 이전 1 2 3 4 다음