공작소

문제 K사의 물류창고를 운영하는 도커 씨는 오늘 발주를 처리하기 위해 N 개의 컨테이너들을 적재해야 한다. 도커씨는 이 일을 하나의 로봇을 이용해 처리하려 한다. 로봇은 컨테이너를 옮길 때마다 컨테이너의 무게만큼 비용을 발생시킨다. 컨테이너마다 우선순위가 있는데 우선순위는 1 이상 M 이하의 정수로 표현된다. 우선순위가 1에 가까울 수록 높은 우선순위를 가지고, M에 가까울 수록 낮은 우선순위를 가진다. M개의 각 우선순위에 대하여 해당 우선순위를 갖는 컨테이너가 적어도 하나 존재한다. 컨테이너는 레일을 통해 하나씩 오고, 우선순위가 낮은 컨테이너를 먼저 적재한다. 낮은 우선순위의 컨테이너들이 모두 적재되지 않은 상태에서 높은 우선순위의 컨테이너가 온다면 레일의 처음으로 보낸다. 레일의 처음으로 보낼 때..

문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬..

문제 정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 여섯 가지이다. push X: 정수 X를 큐에 넣는 연산이다. pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 큐에 들어있는 정수의 개수를 출력한다. empty: 큐가 비어있으면 1, 아니면 0을 출력한다. front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. 입력 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 ..

문제 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) 출력 예제와 같이 요세푸스 순열을 출력한다. 풀이 과정 큐를 이용해 해당 문제 상황을 해결할 수 있다. N이..

Queue 큐 (Queue) 는 제일 먼저 넣은 데이터가 가장 먼저 나오는 FIFO (First In First Out) 자료 구조이다. Queue 구조에 대한 자세한 설명은 아래 게시글에서 확인할 수 있다. https://readytojoin.tistory.com/77 [ Algorithm ] 큐 도입 이 글은 자료구조에서 스택 다음으로 배우게 되는 큐에 대한 개념을 담고 있습니다. 스택과 유사하지만 다른 특징을 가지고 있으며, 큐 자료 구조에 대한 기반을 다져 놓으면 실전적으로 readytojoin.tistory.com C++에서 queue 는 C++ 표준 라이브러리 (STL; Standard Template Library) 로 정의되어 있기에, 필요할 때 선언한다면 편리하게 사용할 수 있다. Que..

도입 이 글은 자료구조에서 스택 다음으로 배우게 되는 큐에 대한 개념을 담고 있습니다. 스택과 유사하지만 다른 특징을 가지고 있으며, 큐 자료 구조에 대한 기반을 다져 놓으면 실전적으로 활용이 가능합니다. 큐는 다른 수많은 알고리즘 (BFS, 위상 정렬, 데이크스트라 등등) 을 배우는 데에 있어서 필수적인 기초가 되는 알고리즘이기 때문에, 큐의 개념을 이해하고 여러 문제에 활용하며 풀이한 뒤, 추후 적극적으로 응용이 가능하도록 능력을 기르는 것이 이 글의 목적입니다. 본 글은 C를 기반으로 작성되었습니다. 스택 자료 구조를 먼저 공부한 이후 큐를 공부하는 것을 추천드립니다. https://readytojoin.tistory.com/35 스택 (Stack) 스택 (Stack) 은 한 쪽 끝에서만 데이터를 ..