최근 알고리즘 테스트 공부를 위해서 파이썬을 꽤나 자주 이용하는데, 문제에서 빈번하게 사용되는 deque에 대해서 알아봅시다! Deque, 왜 쓰나요? 먼저 주 언어가 Javascript였던 제가, 파이썬으로 알고리즘을 하게 된 가장 큰 이유가 바로 deque의 유무였습니다. 자바스크립트에서 후입선출 방식의 Queue나 양쪽에서 삽입 삭제가 가능한 Double-ended Queue 같은 자료구조를 구현하기 위해선, 링크드리스트를 거의 필수로 사용해야 했습니다. 예를 들어 1, 2, 3이 있는 배열을 큐 방식으로 넣고 뺀다고 생각해 봅시다. 1, 2, 3에서 가장 먼저 들어왔던 1의 값만 뺀다고 생각 해봅시다. 그럼 1을 빼기 위해서, 뒤에 있는 모든 index들이 한 칸 앞으로 와야 하는 귀찮은 일이 발..
https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 사용언어 : node.js 알고리즘 : 자료구조, 큐 Solved.ac Tier : Silver IV node.js 코드 1. 문제 정리 선입 선출 방식의 큐를 사용하면 쉽게 해결 할 수 있는 문제이다. 반복문을 사용하여 계속 돌면서 shift로 맨 앞의 값을 뺀 뒤, 반복 횟수가 K의 배수인 경우엔 값을 다시 넣지 않고 아닌 경우엔 그냥 값을 넣는 방식으로 큐를 사용하여 문제를 해결 하였다. 2. 완성 코드 const filePath = process.platform === "linux..
https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 사용언어 : node.js 알고리즘 : 자료구조, 큐 Solved.ac Tier : Silver IV node.js 코드 1. 문제 정리 간단하게 사진 한장으로 정리되는 문제이다. 항상 맨 위에 있는 카드는 없애고, 삭제되고 난 뒤 젤 위에 있는 카드를 맨 아래로 보내면 되는 문제이다. 위에 카드는 사라지고 아래 카드는 들어오는 구조는 바로 큐이다. 선입 선출 방식을 이용하여 먼저 코드를 짜보았다..
https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 사용언어 : node.js 알고리즘 : 자료구조, 큐 Solved.ac Tier : Silver IV node.js 코드 1. 문제 정리 기존에 우리가 쉽게 아는 큐와 같은 문제이다. 이미 C#과 C로 풀어 본 적 있는 문제이지만, 주 언어가 된 JS엔 자료구조가 없기 때문에 직접 구현해야 한다. 따라서 앞으로 상위 문제를 풀 때 필요한 자료구조인 스택, 큐, 덱 같은 기초부터 시..
백준 온라인 저지 / 10845번 큐 https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 사용언어 : C# (.NET) 알고리즘 : 자료 구조, 큐 C#코드 1. 문제 정리 이번 문제는 테스트 케이스 값을 받아와 그 값만큼 명령어를 받아오는 문제이다. 전에 풀어 봤던 스택과 다를 게 없는 문제이다. 그때 스택을 잠깐 살펴보았을 때 스택은 LIFO 후입 선출이라고 칭했지만, 큐는 그와 반대인 선입 선출 FIFO의 개념과 같다. 이 문..
