반응형

문제

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

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(0) if 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[0] if self.size() != 0 else -1
 
    def back(self):
        return self.queue[-1] if 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


반응형

'끄적 > Algorithm' 카테고리의 다른 글

[알고리즘] 백준 - 5430 AC 파이썬 구현  (0) 2019.01.17
[알고리즘] 백준 - 1021 회전하는 큐 파이썬 구현  (0) 2019.01.16
[알고리즘] 백준 - 1966 프린터큐 파이썬 구현  (0) 2019.01.12
[알고리즘] 백준 - 1260 DFS와 BFS 파이썬 구현  (0) 2019.01.12
[알고리즘] 백준 - 10845 큐 파이썬 구현  (0) 2019.01.10
반응형

문제

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 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(0) if 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[0] if self.size() != 0 else -1
 
    def back(self):
        return self.queue[-1] if 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


반응형

'끄적 > Algorithm' 카테고리의 다른 글

[알고리즘] 백준 - 1021 회전하는 큐 파이썬 구현  (0) 2019.01.16
[알고리즘] 백준 - 11866, 1158 조세퍼스 문제 파이썬 구현  (0) 2019.01.13
[알고리즘] 백준 - 1260 DFS와 BFS 파이썬 구현  (0) 2019.01.12
[알고리즘] 백준 - 10845 큐 파이썬 구현  (0) 2019.01.10
[알고리즘] 백준 - 1874 스택 수열 파이썬 구현  (0) 2019.01.09
반응형

문제


그래프를 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(0) if 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[0] if self.size() != 0 else -1
 
    def back(self):
        return self.queue[-1] if 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[-1] if 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


반응형

'끄적 > Algorithm' 카테고리의 다른 글

[알고리즘] 백준 - 11866, 1158 조세퍼스 문제 파이썬 구현  (0) 2019.01.13
[알고리즘] 백준 - 1966 프린터큐 파이썬 구현  (0) 2019.01.12
[알고리즘] 백준 - 10845 큐 파이썬 구현  (0) 2019.01.10
[알고리즘] 백준 - 1874 스택 수열 파이썬 구현  (0) 2019.01.09
[알고리즘] 백준 - 1874 스택 수열 파이썬 구현  (0) 2019.01.08

+ Recent posts

티스토리툴바