반응형

문제

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.

크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.

***

* *

***

N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.

입력

첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.

출력

첫째 줄부터 N번째 줄까지 별을 출력한다.

 

해설

이 문제는 그림을 그리면서 먼저 패턴을 파악하면 쉽게 풀 수 있을 것 같다.

입력값이 3 일때를 생각해보면

x x x
x   x
x x x

인데, 이 경우에 1,1이 공백을 출력해야 하는 위치인 것을 알 수 있고,

이 패턴이 반복되기 때문에 i, j의 1 % 3(1 나머지 3)의 값이 1인 곳은 공백으로 처리를 하면 첫번째 단계는 해결이 된다.

이 경우가 재귀에서 처리해는 최소범위의 값이다.

 

이 코드를 그래도 9로 넘어갈 경우

x x x x x x x x x
x   x x   x x   x
x x x x x x x x x
x x x x x x x x x
x   x x   x x   x
x x x x x x x x x
x x x x x x x x x
x   x x   x x   x
x x x x x x x x x

색칠된 부분이 정답과는 다른 부분이 된다.

즉, 첫번째 우리가 공백으로 처리한 부분 이외에 추가로 공백으로 처리해야하는 좌표는 아래와 같다.(좌표를 편의상 i, j로 작성합니다. for loop에서 자주 사용되는 변수입니다.)

 

(3,3) (3,4) (3,5)

(4,3) (4,4) (4,5)

(5,4) (5,4) (5,5)

 

여기서 i, j 의 범위는 모두

3^1 <= i,j < 3^1 + 3^1 이다.(^1은 1승, 제곱인 경우 ^2로 표현합니다.)

 

즉, 3^1부터 3^1 크기의 정 사각형이 빈 공백으로 표시가 된다.

 

입력값이 27이라면

3^2 부터 3^2+3^2까지 (9 ~ 17) 공백으로 표현이 된다.

 

이 규칙에서 나온 코드가 아래 코드에서 30번째 라인의 코드이다.

3~5까지는 모두 공백(n%3==1일때)으로 출력이 되도록 3으로 나눈 값의 몫만을 취해서 재귀로 호출한다.

그렇다면 9,9는 3,3이 되고, 다시 1,1이 되면서 빈 공백을 출력하게 된다.

나머지는 제외한 몫만을 취급하기 때문에

(17,17, 27) => (5,5,9) => (1, 1, 3)이 되면서 num이 1이 되기전에 line 20에서 분기에 걸려 " " 빈 공백을 출력하게 된다.

코드

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
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const num = parseInt(input[0])
 
const lines = []
 
printStars(num);
console.log(lines.join(""))
 
function printStars(num) {
  for(let i = 0; i < num; i++) {
    for(let j = 0; j < num; j++) {
      star(i, j, num)
    }
    lines.push("\n")
  }
}
 
function star(i, j, num) {
  if(i % 3 == 1 && j % 3 == 1) {
    // (1,1), (1,4), (1,7)...
    lines.push(" ")
  } else {
    if(num == 1) {
      lines.push("*")
    } else {
      // (3,3) = (1,1)이 되고,
      // (3,4) = (1,1)이 된다.
      // (9,9), (27,27)도 동일한 방식으로 재귀 호출된다.
      star(parseInt(i/3), parseInt(j/3), parseInt(num/3))
    }
  }
}
 cs

 

반응형

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

[알고리즘] 백준 - 2798 블랙잭 해설, node js 구현  (0) 2021.09.24
[알고리즘] 백준 - 11729 하노이의 탑 이동 순서 해설, node js 구현  (0) 2021.09.18
[알고리즘] 백준 - 10879 피보나치 수 5 해설 및 node js구현  (0) 2021.08.31
[알고리즘] 백준 - 1002 터렛 해설, node js 구현  (0) 2021.08.28
[알고리즘] 백준 - 3053 택시 기하학 해설, node js 구현  (0) 2021.08.28
반응형

문제

한수는 지금 (x, y)에 있다. 직사각형은 각 변이 좌표축에 평행하고, 왼쪽 아래 꼭짓점은 (0, 0), 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 x, y, w, h가 주어진다.

 

출력

첫째 줄에 문제의 정답을 출력한다.

제한

  • 1 ≤ w, h ≤ 1,000
  • 1 ≤ x ≤ w-1
  • 1 ≤ y ≤ h-1
  • x, y, w, h는 정수

 

해설

문제를 쉽게 풀어서 설명한다면

"직사각형 내부에 있는 점 (x,y)에서 직사각형의 변까지의 최소 거리" 를 구하는 문제이다.

결국 최솟값을 찾으면 되는 문제이다. 무엇중에 최소값을 구하는지만 생각하면 해결된다.

사각형이니까 변이 4개, 우리에게 주어진 점은 1개(x, y)

그렇다면 (x, y)에서 사각형 각 변까지의 거리 총 4개를 구하고 그중에 최솟값을 취하면 된다.

아래 코드는 4개의 거리값을 구하고, 정렬을 이용하여 최솟값을 구하는 코드이다.

 

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().split(' ');
 
var [x, y, w, h] = input.map(el => parseInt(el));
 
 
//w, h 는 x, y보다 크기 떄문에 항상 양수
const xDiff = w-x
const yDiff = h-y
 
// 네개의 변수 중 최소값이 문제에서 하는 최소 거리이다.
const arr = [xDiff, yDiff, x, y]
// js의 기본 sort는 ascii 문자를 기준으로 정렬하기 때문에 반드시 비교함수를 넣어줘야한다.
arr.sort((a, b) => {
  return a - b
});
console.log(arr[0])
 cs
반응형

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

[알고리즘] 백준 - 3009 네 번째 점 node js 구현  (0) 2021.08.22
[알고리즘] 백준 - 1003 피보나치 함수 node js 구현  (0) 2021.08.20
[알고리즘] 백준 -11653 소인수분해 node.js 구현  (0) 2021.08.16
[알고리즘] 백준 -1463 1로 만들기 파이썬 구현  (0) 2019.02.12
[알고리즘] 백준 - 1149 RGB 거리 파이썬 구현  (0) 2019.02.01
반응형

문제

선영이는 주말에 할 일이 없어서 새로운 언어 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개의 테스트 케이스
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


반응형

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

[알고리즘] 백준 - 11718 그대로 출력하기 파이썬 구현  (0) 2019.01.23
[알고리즘] 백준 - 1003 피보나치 함수 파이썬 구현  (0) 2019.01.18
[알고리즘] 백준 - 1021 회전하는 큐 파이썬 구현  (0) 2019.01.16
[알고리즘] 백준 - 11866, 1158 조세퍼스 문제 파이썬 구현  (0) 2019.01.13
[알고리즘] 백준 - 1966 프린터큐 파이썬 구현  (0) 2019.01.12
반응형

문제

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

  1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
  2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
  3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.


입력

첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.


해설

deque 클래스를 만들고, deque를 이용해서 문제를 풀었습니다.

기본적인 deque의 함수들은 백준의 기본 deque 문제가 제시하는 기준에 맞춰서 구현을 하였고, 제가 추가로 구현한 함수는 find함수로 특성 숫자가 몇번째 index에 있는지 알려주는 함수만 추가로 만들었습니다.


코드

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
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 find(self, num):
        index = 0
        i = self.front_flag
        while(True):
            if self.queue[i] == num:
                return index
 
            index = index + 1
            i = (i + 1) % self.list_size
            if i == self.rear:
                break
 
 
 
n, m = map(int, input().split())
deque = Deque(n)
 
temp = list(map(int, input().split()))
 
for i in range(n):
    deque.push_back(i+1)
 
#이동 회수를 저장하기 위한 변수
count = 0
for i in range(m):
    # 찾아야 되는 숫자의 현재 위치
    index = deque.find(temp[i])
 
    mid = (n - i) / 2
    if index <= mid or (n-i) <= 2:
        #앞쪽임
        while(deque.front() != temp[i]):
            deque.push_back(deque.pop_front())
            count += 1
 
    else:
        #뒤쪽임
        while(deque.front() != temp[i]):
            deque.push_front(deque.pop_back())
            count += 1
    deque.pop_front()
 
print(count)
 
cs


반응형

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

[알고리즘] 백준 - 1003 피보나치 함수 파이썬 구현  (0) 2019.01.18
[알고리즘] 백준 - 5430 AC 파이썬 구현  (0) 2019.01.17
[알고리즘] 백준 - 11866, 1158 조세퍼스 문제 파이썬 구현  (0) 2019.01.13
[알고리즘] 백준 - 1966 프린터큐 파이썬 구현  (0) 2019.01.12
[알고리즘] 백준 - 1260 DFS와 BFS 파이썬 구현  (0) 2019.01.12
반응형

문제

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

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
반응형

문제

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

명령은 총 여섯 가지이다.

  • 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(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
 
#몇개의 숫자를 받을건지
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

 

반응형

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

[알고리즘] 백준 - 1966 프린터큐 파이썬 구현  (0) 2019.01.12
[알고리즘] 백준 - 1260 DFS와 BFS 파이썬 구현  (0) 2019.01.12
[알고리즘] 백준 - 1874 스택 수열 파이썬 구현  (0) 2019.01.09
[알고리즘] 백준 - 1874 스택 수열 파이썬 구현  (0) 2019.01.08
[알고리즘] 백준 - 10828 스택 파이썬 구현  (0) 2019.01.07
반응형

문제

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다. 

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다. 

출력

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다. 

예제 입력 1 

6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(

예제 출력 1 

NO
NO
YES
NO
YES
NO


코드

스택을 이용하여 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
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 True if len(self.list) == 0 else False
 
    def top(self):
        return self.list[-1] if self.size() != 0 else -1
 
def isVaildParan(chars):
    stack = Stack()
    isVPS = True
    if len(chars) == 0:
        isVPS = False
 
    for i in range(len(chars)):
        if chars[-(i+1)] == ")":
            stack.push(chars[-(i+1)])
        else:
            if stack.pop() == -1:
                isVPS = False
 
    if not stack.empty() or not isVPS:
        return False
    else:
        return True
 
#몇개의 숫자를 받을건지
num = int(input())
 
#반복문을 통해 isValid~ 호출
for i in range(num):
    chars = list(input())
    if isVaildParan(chars):
        print("YES")
    else:
        print("NO")
 
cs


반응형

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

[알고리즘] 백준 - 1966 프린터큐 파이썬 구현  (0) 2019.01.12
[알고리즘] 백준 - 1260 DFS와 BFS 파이썬 구현  (0) 2019.01.12
[알고리즘] 백준 - 10845 큐 파이썬 구현  (0) 2019.01.10
[알고리즘] 백준 - 1874 스택 수열 파이썬 구현  (0) 2019.01.08
[알고리즘] 백준 - 10828 스택 파이썬 구현  (0) 2019.01.07
반응형

문제

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 먼저 들어간 자료가 제일 나중에 나오는 (FILO, first in last out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키 도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

입력

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 

정수가 두 번 나오는 일은 없다.

출력

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

예제 입력 1 

8
4
3
6
8
7
5
2
1
예제 출력 1 
+
+
+
+
-
-
+
+
-
+
+
-
-
-
-
-

예제 입력 2 

5
1
2
5
3
4

예제 출력 2 

NO

소스코드

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
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
 
#몇개의 숫자를 받을건지
num = int(input())
#문제를 풀기위해 사용한 stack
stack = Stack()
#입력을 저장하기 위한 list
inputs = []
#출력을 저장하기 위한 list
outputs = []
idx = 0
 
#입력을 받아 inputs 리스트에 저장
for i in range(num):
    inputs.append(int(input()))
 
#for loop를 돌며 각 loop의 시작에서 push를 하며 시작
for i in range(num):
    stack.push(i+1)
    outputs.append("+")
 
    #idx가 전체 숫자의 개수보다 큰 경우가 이 문제를 풀지 못하는경우
    #그러한 경우 발생시 while에서 pop을 하지 않기 떄문에 stack에 숫자가 남게됨
    while idx < num and stack.top() == inputs[idx]:
        stack.pop()
        outputs.append("-")
        idx += 1
 
#숫자가 남은 경우 이 문제를 풀지 못하는 경우 "NO"를 출력
if not stack.empty():
    print("NO")
else:
    for str in outputs:
        print(str)
 
cs


반응형

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

[알고리즘] 백준 - 1966 프린터큐 파이썬 구현  (0) 2019.01.12
[알고리즘] 백준 - 1260 DFS와 BFS 파이썬 구현  (0) 2019.01.12
[알고리즘] 백준 - 10845 큐 파이썬 구현  (0) 2019.01.10
[알고리즘] 백준 - 1874 스택 수열 파이썬 구현  (0) 2019.01.09
[알고리즘] 백준 - 10828 스택 파이썬 구현  (0) 2019.01.07

+ Recent posts

티스토리툴바