/* code block */
반응형

우선순위 큐는 넣는 순서와 상관 없이, 가장 높은 우선순위를 가진 데이터를 꺼내는 큐이다.

 

아래와 같이 사용한다.


1
2
3
4
5
6
7
8
from queue import PriorityQueue
 
q = PriorityQueue()
q.put(3)
q.put(1)
q.put(2)
print(q.get())
 
 

위 코드의 결과는 1이다. 파이썬의 우선순위 큐는 기본적으로 min heap으로 되어있기 때문에

 

숫자가 낮은 수가 높은 우선순위를 가진다.

 

직접 우선순위를 정해줄 수도 있다.

 

1
2
3
4
5
6
7
from queue import PriorityQueue
 
q = PriorityQueue()
q.put((3, '바나나'))
q.put((1, '딸기'))
q.put((2, '토마토')
print(q.get()[1])

위 코드의 결과는 딸기이다.

반응형
저작자표시

'Python > 기초' 카테고리의 다른 글

스택 구현하기  (0) 2019.08.21
소수 구하기 - 에라토스테네스의 체  (0) 2019.08.21
최대공약수, 최소공배수 구하기  (0) 2019.08.21
반응형
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Stack(list):
    push = list.append
 
    def is_empty(self):
        if not self:
            return True
        else:
            return False
 
    def peek(self):
        return self[-1]
 
if __name__ == "__main__":
    s = Stack()
    s.push(1)
    s.push(2)
    s.push(3)
 
    while s:
        data = s.pop()
        print(data, end='')
 
리스트를 상속받아 스택을 구현한 것이다.
스택 클래스를 한 번 구현해놓으면 import해서 사용하기 편리하다.
 
if __name__ == "__main__" 이 부분은
이 소스코드가 있는 파이썬 파일이 다른 파일로부터 호출된것이 아닌 메인으로 실행됐을때 동작하게 하기 위해 쓰는 것으로, 스택이 잘 동작하는지 테스트하기 위해 사용했다.
반응형
저작자표시

'Python > 기초' 카테고리의 다른 글

우선순위 큐  (0) 2019.08.21
소수 구하기 - 에라토스테네스의 체  (0) 2019.08.21
최대공약수, 최소공배수 구하기  (0) 2019.08.21
반응형

소수를 구하는 방법은 여러가지가 있지만, 프로그램으로 구현할 때에는

 

시간복잡도를 고려하게 된다.

 

프로그램의 성능을 좌지우지하는 시간복잡도가 다른방법들에 비해 낮은 편이기 때문에

 

에라토스테네스의 체를 이용해 소수를 구하도록 한다.

 

방법은 아래와 같다.

 

1. 2부터 구하고자 하는 수 n까지의 자연수를 나열한다.

 

2. 소수인 2를 남기고 n까지의 모든 2의 배수를 제거한다. 2의 배수는 2라는 약수가 있기 때문에 소수가 아니기 때문이다.

 

3. 다음 수인 3은 이전 단계에서 제거되지 않았기 때문에 소수이다. 또한 3의 배수는 모두 소수가 아니기 때문에 n까지의 3의 배수들을 모두 제거한다.

 

4. 2번 단계에서 4는 제거되고 없기 때문에 5가 다음 소수이다. 또한 5의 배수는 모두 소수가 아니기 때문에 n까지의 5의 배수들을 모두 제거한다.

 

5. 같은 과정을 n까지 반복하고 나면 소수만 남게 된다.

 

기본 원리는 이렇다. 그런데 2부터 모든 2의 배수를 지우고, 또 3부터 모든 3의 배수를 지우는 것은 불필요한 중복된 작업을 포함한다.

 

정수 i의 배수를 지울 차례가 되었을때, i부터가 아닌 ixi부터 지우면 된다. 

 

왜일까?

 

예로 5의 경우를 들어보자.

 

5x5부터 시작해 모든 5의 배수는 이전 단계에서 다 지워졌을 수도 있고, 아직 지워지지 않은 수가 있을 수도 있다.

 

하지만 5x5 이전 5의 배수들은 5x4 (4의 배수), 5x3 (3의 배수), 5x2 (2의 배수)로 이미 이전 단계에서 다 지워졌다.

 

그렇다면 우리는 각 단계마다 ixi부터 시작함으로써 불필요한 작업을 줄일 수 있다.

 

하지만 프로그램을 이렇게 짤 경우, i가 무지막지하게 큰 숫자일 때 ixi는 프로그램 내에서 처리할 수 있는 범위를 초과해 이상한 결과가 나올 수 있기 때문에 ix2 또는 i+i정도로 해준다.

 

또한, 소수가 아닌 수들을 지울 때 실제로 수를 지우면 시간이 오래걸리니 bool 배열을 만들어 True, False로 지운척 표시만 해준다.

 

아래는 파이썬으로 구현한 코드이다.

 

1
2
3
4
5
6
7
8
MAX = 1000000
check = [False]*(MAX+1)
check[0] = check[1] = True
 
for i in range(2, MAX+1):
    if not check[i]:
        for j in range(i+i, MAX+1, i):
            check[j] = True

37이 소수인지 궁금하다면 check[37]을 확인하면 된다.

 

여기서는 False일 때 소수이다.

 

반응형
저작자표시

'Python > 기초' 카테고리의 다른 글

우선순위 큐  (0) 2019.08.21
스택 구현하기  (0) 2019.08.21
최대공약수, 최소공배수 구하기  (0) 2019.08.21
반응형

A, B의 최대공약수는 B, A%B의 최대공약수와 같다.

 

이 성질을 이용해 A%B의 결과가 0이 될 때까지 나머지를 구해주면

 

최대 공약수를 얻을 수 있다.

 

아래는 최대 공약수를 구하는 함수이다.

1
2
3
4
5
6
7
8
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)
 
a = gcd(n, m)
b = (n*m) // a

 

최소공배수는 최대공약수를 알고 있다면 쉽게 구할 수 있다.

 

'A x B = 최대공약수 x 최소공배수'이기 때문에

 

'최소공배수 = A x B / 최대공약수'로, A와 B를 곱한 값에서 최대공약수를 나눠주면 된다. 

반응형
저작자표시

'Python > 기초' 카테고리의 다른 글

우선순위 큐  (0) 2019.08.21
스택 구현하기  (0) 2019.08.21
소수 구하기 - 에라토스테네스의 체  (0) 2019.08.21

+ Recent posts

티스토리툴바