반응형

문제

선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.

함수 R은 배열에 있는 숫자의 순서를 뒤집는 함수이고, D는 첫 번째 숫자를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.

함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 숫자를 버리는 함수이다.

배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.


입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다.

각 테스트 케이스의 첫째 줄에는 수행할 함수 p가 주어진다. p의 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.

다음 줄에는 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000)

다음 줄에는 [x1,...,xn]과 같은 형태로 배열에 들어있는 수가 주어진다. (1 ≤ xi ≤ 100)

전체 테스트 케이스에 주어지는 p의 길이의 합과 n의 합은 70만을 넘지 않는다.


해설

백준 알고리즘의 10866번을 풀때 작성해놓은 Deque 클래스를 그대로 활용하여 코드를 작성하였다. Deque 클래스에 print() 함수를 추가하였다. print함수는 방향을 True, False값으로 받아 출력을 할 수 있도록 만들었다.

이 문제를 풀다 막혀서 검색을 하는 경우에는 class의 내용보다는 아래 입력을 받고 처리하는 코드를 먼저 보고, 필요에 따라 클래스에서 해당 함수가 어떤 작업을하는지 확인하면 편하게 확인이 가능할것 같다.


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
import ast
class Deque():
    def __init__(self, size):
        self.queue = [0 for x in range(size + 1)]
        self.front_flag = 0
        self.rear = 0
        self.max_size = size
        self.list_size = size + 1
 
    def push_back(self, num):
        if (self.rear + 1) % self.list_size == self.front_flag:
            return -1
        self.queue[self.rear] = num
        self.rear = (self.rear +1) % self.list_size
 
    def push_front(self, num):
        if (self.rear + 1) % self.list_size == self.front_flag:
            return -1
        self.front_flag = self.list_size - 1 if self.front_flag == 0 else self.front_flag - 1
        self.queue[self.front_flag] = num
 
    def pop_front(self):
        if self.size() == 0:
            return -1
        temp = self.queue[self.front_flag]
        self.front_flag = (self.front_flag + 1) % self.list_size
        return temp
 
    def pop_back(self):
        if self.size() == 0:
            return -1
        self.rear = self.list_size - 1 if self.rear == 0 else self.rear - 1
        return self.queue[self.rear]
 
    def size(self):
        if self.front_flag == self.rear:
            return 0
        elif self.rear > self.front_flag:
            return self.rear - self.front_flag
        else:
            return self.max_size - (self.front_flag - self.rear) + 1
 
    def empty(self):
        return 1 if self.front_flag == self.rear else 0
 
    def front(self):
        if self.size() == 0:
            return -1
        return self.queue[self.front_flag]
 
    def back(self):
        if self.size() == 0:
            return -1
        return self.queue[self.rear - 1]
 
    def print(self, isFront):
        if self.size() == 0:
            print("[]")
            return
        output = "["
        if isFront:
            i = self.front_flag
            while(True):
                output = output + "%d"%self.queue[i]
                i = (i + 1) % self.list_size
                if i == self.rear:
                    output = output + "]"
                    break
                output = output + ","
        else:
            i = self.rear
            while(True):
                i = (i - 1) % self.list_size
                output = output + "%d"%self.queue[i]
                if i == self.front_flag:
                    output = output + "]"
                    break
                output = output + ","
        print(output)
#n개의 테스트 케이스
= int(input())
 
for i in range(n):
    #명령어 리스트
    operator = list(input())
    #m크기의 배열
    m = int(input())
    deque = Deque(m)
    #배열
    str = input()
    array = ast.literal_eval(str)
    for i in array:
        deque.push_back(i)
 
    isFront = True
    isValid = True
    for op in operator:
        if op == "R":
            isFront = not isFront
        elif op == "D":
            temp = 0
            if isFront:
                temp = deque.pop_front()
            else:
                temp = deque.pop_back()
 
            if temp < 0:
                print("error")
                isValid = False
                break
        else:
            print("unacceptable op")
 
    if isValid:
        deque.print(isFront)
 
cs


반응형
반응형

문제

조세퍼스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 M(≤ N)이 주어진다. 이제 순서대로 M번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, M)-조세퍼스 순열이라고 한다. 예를 들어 (7, 3)-조세퍼스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 M이 주어지면 (N,M)-조세퍼스 순열을 구하는 프로그램을 작성하시오.


입력

첫째 줄에 N과 M이 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ M ≤ N ≤ 1,000)


해설
이 문제는 원형큐를 이용해서 풀 수 있을것 같네요. 첫번째 코드는 일반 큐를 사용하여 문제를 풀었고, 두번째 코드는 원형큐를 사용해서 문제를 풀었습니다.
제가 원형큐를 사용하여 문제를 푼 가장 큰 이유는 기본 Queue에서의 pop() 때문인데요. pop의 구현 내용을 보면 python list의 pop(0)을 호출한것을 확인하실 수 있습니다. pop(0)의 경우 가장 앞의 요소를 pop하는 대신에 전체 리스트를 전부 왼쪽으로 이동(shift)시키는 작업이 동반되는 O(N)의 작업입니다.  p.s.그냥 pop()의 경우 마지막 요소만 pop하기 때문에 O(1)입니다.
반면에 원형큐의 경우는 front와 rear를 사용하여 문제를 풀기 때문에 전체 배열을 shift하는 과정 없이 사용이 가능합니다.

* 백준 알고리즘 파이썬 코드가 시간초과 나는 경우
파이썬 자체가 실행속도가 느리다보니 다른 언어에서 시간초과가 나지 않는 코드를 파이썬으로 구현하였을떄 시간초과가 나는 경우가 있다고 합니다.
이런 경우에 pypy3를 언어로 설정하는 경우에 해결이 될 수 있습니다.
단, 알고리즘 자체의 시간 복잡도가 큰 경우에는 pypy3를 사용해도 시간초과가 나게 됩니다.
예를들어 아래 일반 Queue를 사용한 경우에는 pypy3를 사용해도 시간초과가 나지만 원형큐를 사용한 경우에는 pypy3를 사용하는 시간초과가 나지 않습니다.

코드 - Queue
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Queue:
    def __init__(self):
        self.queue = []
 
    def push(self, num):
        self.queue.append(num)
 
    def pop(self):
        return self.queue.pop(0if len(self.queue) != 0 else -1
 
    def size(self):
        return len(self.queue)
 
    def empty(self):
        return 1 if self.size() == 0 else 0
 
    def front(self):
        return self.queue[0if self.size() != 0 else -1
 
    def back(self):
        return self.queue[-1if self.size() != 0 else -1
 
    def max(self):
        return max(self.queue)
 
n, m = map(int, input().split())
 
queue1 = Queue()
output_str = "<"
 
for i in range(1, n+1):
    queue1.push(i)
 
while(True):
    for i in range(m-1):
        queue1.push(queue1.pop())
 
    output_str = output_str + str(queue1.pop())
    if queue1.empty() == 1:
        break
    else:
        output_str = output_str + ", "
 
print(output_str + ">")
 
cs


코드 - CircularQueue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class CircularQueue():
    def __init__(self, size):
        self.queue = [0 for x in range(size + 1)]
        self.front = 0
        self.rear = 0
        self.max_size = size
        self.list_size = size + 1
 
    def push(self, num):
        if (self.rear + 1) % self.list_size == self.front:
            return -1
        self.queue[self.rear] = num
        self.rear = (self.rear +1) % self.list_size
 
    def pop(self):
        if self.size() == 0:
            return -1
        temp = self.queue[self.front]
        self.front = (self.front + 1) % self.list_size
        return temp
 
    def size(self):
        if self.front == self.rear:
            return 0
        elif self.rear > self.front:
            return self.rear - self.front
        else:
            return self.max_size - (self.front - self.rear) + 1
 
    def empty(self):
        return 1 if self.front == self.rear else 0
 
    def max(self):
        return max(self.queue)
 
    def print(self):
        print(self.queue)
        print(self.front)
        print(self.rear)
 
n, m = map(int, input().split())
 
queue = CircularQueue(n)
 
output_str = "<"
 
for i in range(1, n+1):
    queue.push(i)
 
while(True):
    for i in range(m-1):
        queue.push(queue.pop())
 
    output_str = output_str + str(queue.pop())
    if queue.empty() == 1:
        break
    else:
        output_str = output_str + ", "
 
print(output_str + ">")
 
cs


반응형
반응형

문제

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.

  1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
  2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.

예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.

여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.


입력

첫 줄에 test case의 수가 주어진다. 각 test case에 대해서 문서의 수 N(100이하)와 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue의 어떤 위치에 있는지를 알려주는 M(0이상 N미만)이 주어진다. 다음줄에 N개 문서의 중요도가 주어지는데, 중요도는 적절한 범위의 int형으로 주어진다. 중요도가 같은 문서가 여러 개 있을 수도 있다. 위의 예는 N=4, M=0(A문서가 궁금하다면), 중요도는 2 1 4 3이 된다.


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Queue:
    def __init__(self):
        self.queue = []
 
    def push(self, num):
        self.queue.append(num)
 
    def pop(self):
        return self.queue.pop(0if len(self.queue) != 0 else -1
 
    def size(self):
        return len(self.queue)
 
    def empty(self):
        return 1 if self.size() == 0 else 0
 
    def front(self):
        return self.queue[0if self.size() != 0 else -1
 
    def back(self):
        return self.queue[-1if self.size() != 0 else -1
 
    def max(self):
        return max(self.queue)
 
num_of_case = int(input())
 
for _ in range(num_of_case):
    num_of_doc, current_index = map(int, input().split())
    current_list = map(int, input().split())
 
    queue = Queue()
    print_count = 0
    for i in current_list:
        queue.push(i)
 
    while(True):
        if queue.front() < queue.max():
            queue.push(queue.pop())
            current_index -= 1
            if  current_index < 0:
                current_index = queue.size() - 1
        elif current_index == 0:
            print(print_count + 1)
            break
        else:
            queue.pop()
            current_index -= 1
            if  current_index < 0:
                current_index = queue.size() - 1
            print_count += 1
 
cs


반응형
반응형

문제


그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.


입력


첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.



백준에서 Queue로 분류가 되어있는 문제입니다. 이 문제를 풀때 Queue로 분류되어 있다고 Queue만 사용한다면 문제를 푸는데 조금 힘들 수 있습니다.

DFS(깊이 우선 탐색)의 경우 Stack, BFS(너비 우선 탐색)의 경우 Queue를 사용해서 풀면 간단하게 구현이 가능합니다.


DFS의 경우 Stack을 사용하는데, 각 노드를 방문하고 자식노드를 찾으러 가야하는 경우에 Stack의 현재 노드를 push해줍니다. 이후에 다시 이 노드로 돌아오게 되는 경우에 이 Stack에 저장된 값을 가지고 이 노드로 돌아와서 나머지 자식노드들을 탐색 할 수 있게 저장하는 것입니다.


BFS의 경우 Queue를 사용하는데, 노드를 방문할때마다 Queue에 저장을 합니다. 즉 현재 노드의 자식노드들을 전부 Queue에 push를 합니다. 모든 자식 노드를 push를 하였으면 Queue에서 pop해서 queue의 넣은 자식노드들 중 가장 먼저 넣었던 노드 번호를 꺼내오고 그 노드의 자식 노드를 전부 Queue의 넣습니다. 위 과정을 반복하면 너비 우선 탐색으로 모든 노드들을 탐색 할 수 있습니다.


코드

아래 코드의 경우 이전에 백준 문제를 풀며서 구현해놓은 Queue와 Stack을 사용하여 문제를 풀었습니다. Queue와 Stack의 push, pop이 어떤 상황에 쓰이는지 확인해보시고 문제를 풀면 도움이 될것 같네요. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
class Queue:
    def __init__(self):
        self.queue = []
 
    def push(self, num):
        self.queue.append(num)
 
    def pop(self):
        return self.queue.pop(0if len(self.queue) != 0 else -1
 
    def size(self):
        return len(self.queue)
 
    def empty(self):
        return 1 if self.size() == 0 else 0
 
    def front(self):
        return self.queue[0if self.size() != 0 else -1
 
    def back(self):
        return self.queue[-1if self.size() != 0 else -1
 
class Stack:
    def __init__(self):
        self.list = []
 
    def push(self, num):
        self.list.append(num)
 
    def pop(self):
        if self.size() == 0:
            return -1
        return self.list.pop()
 
    def size(self):
        return len(self.list)
 
    def empty(self):
        return 1 if len(self.list) == 0 else 0
 
    def top(self):
        return self.list[-1if self.size() != 0 else -1
 
node, edge, start = map(int, input().split())
 
#graph
graph =  [[0 for cols in range(node)]for rows in range(node)]
for _ in range(edge):
    source, target = map(int, input().split())
    graph[source-1][target-1= 1
    graph[target-1][source-1= 1
 
#dfs
stack = Stack()
dfs_visited_flag = [0 for clos in range(node)]
current_node = start-1
output = []
while(True):
    visit_count = 0
    if current_node + 1 not in output:
        output.append(current_node + 1)
        dfs_visited_flag[current_node] = 1
    for i in range(node):
        if graph[current_node][i] == 1 and dfs_visited_flag[i] != 1:
            stack.push(current_node + 1)
            current_node = i
            visit_count += 1
            break
    if visit_count == 0:
        current_node = stack.pop() - 1
 
    if current_node < 0:
        break
 
print(" ".join(str(x) for x in output))
 
#bfs
queue = Queue()
bfs_visited_flag = [0 for clos in range(node)]
queue.push(start)
current_node = start-1
bfs_visited_flag[current_node] = 1
output = []
while(True):
    for i in range(node):
        if graph[current_node][i] == 1 and bfs_visited_flag[i] != 1:
            queue.push(i+1)
            bfs_visited_flag[i] = 1
    output.append(queue.pop())
    current_node = queue.front()-1
    if current_node < 0:
        break
 
print(" ".join(str(x) for x in output))
 
cs


반응형
반응형

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

  • push X: 정수 X를 큐에 넣는 연산이다.
  • pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
  • size: 큐에 들어있는 정수의 개수를 출력한다.
  • empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
  • front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
  • back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

 

반응형

예제 입력 1 

15 push 1 push 2 front back size empty pop pop pop size empty pop push 3 empty front 

예제 출력 1 

1 2 2 0 1 2 -1 0 1 -1 0 3

 

 

 

 

 

 

  구현 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Queue:
    def __init__(self):
        self.queue = []
 
    def push(self, num):
        self.queue.append(num)
 
    def pop(self):
        return self.queue.pop(0if len(self.queue) != 0 else -1
 
    def size(self):
        return len(self.queue)
 
    def empty(self):
        return 1 if self.size() == 0 else 0
 
    def front(self):
        return self.queue[0if self.size() != 0 else -1
 
    def back(self):
        return self.queue[-1if self.size() != 0 else -1
 
#몇개의 숫자를 받을건지
num = int(input())
queue = Queue()
for _ in range(num):
    tokens = input().split()
 
    if tokens[0== "push":
        queue.push(tokens[1])
    elif tokens[0== "pop":
        print(queue.pop())
    elif tokens[0== "size":
        print(queue.size())
    elif tokens[0== "empty":
        print(queue.empty())
    elif tokens[0== "front":
        print(queue.front())
    elif tokens[0== "back":
        print(queue.back())
    else:
        print("it's not acceptable operator")
 
cs

 

반응형

+ Recent posts