본문 바로가기

Problem Solving96

[Stack] 내림차순 수열 N개의 양의 정수를 원소로 가진 수열 A가 주어졌을 때, A의 원소로 내림차순 수열을 만들고자 한다. 내림차순 수열은 A에서 가장 큰 원소에서 순차적으로 더 작은 값들로 구성된 수열을 말한다. 예를 들어, N=6, A=[6, 9, 7, 6, 4, 6]일 때 A의 내림차순 수열은 다음과 같다. 9 7 6 수열 A가 주어졌을 때, A의 내림차순 수열을 출력하시오. Hint: 스택을 이용하여 더 작거나 같은 값들은 모두 pop()한 후에 push()를 하는 전략을 사용할 수 있다. Input 첫째 줄에 원소의 개수 N이 주어진다. 1 2022. 12. 13.
[Stack] 괄호의 완성 어떤 문자열 S에 앞뒤로 괄호를 추가하여 S를 올바른 괄호열로 만들고자 한다. 괄호로만 구성된 문자열 S가 주어졌을 때, S를 올바른 괄호열로 만들기 위해 앞과 뒤에 붙여할 할 괄호의 최소 개수를 출력하시오. 예를 들어, S = "((()" 인 경우에는 S="((()))"로 뒤에 2개의 괄호를 추가하면 된다. S="()))("인 경우에는 S="((()))()"로 앞에 2개, 뒤에 1개의 괄호를 추가하면 된다. 단, 올바른 문자열을 만들 수 없는 입력은 주어지지 않는다고 가정해도 된다. Input 첫째 줄에 괄호로만 구성된 문자열 S가 주어진다. [1] )))() [2] )(() [3] ))()(( [4] )(()(())) Output 첫째 줄에 S를 올바른 괄호열로 만들기 위해 앞뒤로 추가해야 할 괄호의.. 2022. 12. 13.
[Queue] 요세푸스의 선물 큐: 한쪽 끝에서는 삭제만 가능하고 다른 한쪽 끝에서는 추가만 가능한 추상 데이터 타입 FIFO: First-In, First-Out enqueue: 큐의 rear에 새로운 항목을 추가 dequeue: 큐의 front에 있는 항목을 제거 요세푸스는 N명의 제자들에게 선물을 주고 싶었으나, 선물이 하나 밖에 없었다. 그래서 다음과 같은 규칙을 가지고 게임을 해서 마지막으로 남은 한 사람에게만 선물을 주기로 했다. 모든 제자들은 무작위로 1번부터 N번까지 번호를 부여받아 번호 순서대로 시계방향으로 원을 이루어 앉는다.게임의 각 단계에서 시작 위치에 있는 제자는 1을 외치고, 시계방향으로 돌아가며 1씩 증가한 숫자를 외친다.t번째 단계에서 t^3, 즉, t의 세제곱수를 외치는 제자는 게임에서 탈락한다.t+1번.. 2022. 12. 13.
[Stack] 주차 관리인 스택: LIFO(Last-In, FIrst-Out) 스택 정렬: 스택의 내용을 빈 스택 하나를 이용해서 정렬하는 알고리즘 강의교재에서 본 주차장의 주차 관리인에게 주차 주문이 도착했다. 이 주차 주문에 따르면, 1번부터 N번까지의 차량이 오른편에서 차례대로 도착하고 있을 때, 왼편의 주차 공간에 주차 주문의 차량 번호 순서에 따라 주차를 해야 한다. 이 주차장은 스택처럼 생긴 하단부의 임시 공간을 이용해서 주차 순서를 조정할 수밖에 없음을 알고 있을 것이다. 또한, 한 번 주차장 안으로 들어온 차량은 거꾸로 빼낼 수도 없다. 그렇기 때문에, 때로는 주차 주문에 적힌 주차 순서가 주차하기가 불가능한 순서일 수도 있다. 예를 들어, 주차 계획의 차량 번호 순서가 다음과 같다고 하자. 5 4 1 2 3 차량의.. 2022. 12. 13.

티스토리툴바