자료구조 with Python : Queue(큐)

큐는 스택과 다르게 항목이 들어온 순서대로 접근이 가능하다. 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO) 구조다. 큐도 스택처럼 랜덤 액세스가 제한된다.

큐의 구조

• front : 큐의 가장 앞을 가리키는 포인터
• rear : 큐의 가장 뒤를 가리키는 포인터
• enqueue : rear 뒤에 원소를 삽입하는 함수
• dequeue : front 위치의 원소를 제거하면서 반환하는 함수
• is_empty : 큐가 비어있는지 확인하는 함수
• size : 큐의 크기를 확인하는 함수

큐의 구현

class Queue(object):
    def __init__(self):
        self.items = []
        self.front = 0
        self.rear = -1

    def isEmpty(self):
        return self.front > self.rear

    def enqueue(self, item):
        self.items.append(item)
        self.rear += 1

    def dequeue(self):
        if self.isEmpty():
            print("Queue is empty")
        else:
            self.front += 1
            return self.items[self.front - 1]

    def __repr__(self):
        return repr(self.items[self.front:self.rear+1])

items 리스트에 enqueue()함수로 데이터를 넣으면 가장 뒤를 나타내는 rear가 커진다.

dequeue를 하면 front가 가리키는 데이터를 반환하고 front가 1 증가한다.

큐가 비어있는 지 여부는 front > rear로 알 수 있다.

확인코드

queue = Queue()
for i in range(1, 4):
    queue.enqueue(i)
print(queue)
print("dequeue: {0}".format(queue.dequeue()))
print("dequeue: {0}".format(queue.dequeue()))
queue.enqueue(4)
queue.enqueue(5)
print(queue)
print("dequeue: {0}".format(queue.dequeue()))
print(queue)

이 방법은 큐의 동작이 어떻게 이뤄지는지 확인하기 위함이고 이렇게 계속 사용하게 되면 dequeue()를 하더라도 데이터가 남아있기 때문에 좋은 방법은 아니라고 생각한다.

쉬운 구현은 list자료형을 이용해서 append와 pop(0)를 사용하는 방법이지만 pop(0) 의 경우 시간복잡도가 O(N)이기 때문에 이 또한 비효율적이다.

리스트 함수 정리

이번 포스팅은 파이썬 기본 리스트의 내장 함수들을 정리했습니다. 리스트는 삽입, 삭제, 인덱스 위치 찾기, 원하는 원소 갯수 찾기, 정렬 등이 기본적으로 제공됩니다.

>>> 구문이 있는 명령어는 ide상에서의 실행이 아닌 파이썬 내에서 실행 코드입니다.

삽입

1. append()

A.append(x)는 리스트 A 끝에 원소 x를 추가한다. A[len(A):] = [x] 로 사용도 가능하다. 시간복잡도는 O(1)이다.

>>> A = [1, 2, 3]
>>> A.append(4)
>>> A
[1, 2, 3, 4]
>>> A[len(A):] = [5]
>>> A
[1, 2, 3, 4, 5]

2. extend()

A.extend(iter)는 iterable한 항목 iter를 리스트 A에 추가한다. 여러 개의 리스트를 서로 연결할 때 사용된다. 혹은 A += iter로 사용이 가능하다.

>>>A = [1, 2, 3]
>>>B = [4, 5, 6]
>>>A.extend[B]
A
[1, 2, 3, 4, 5, 6]
>>>A += [7, 8, 9]
A
[1, 2, 3, 4, 5, 6, 7, 8, 9]

3. insert()

A.insert(i, x)는 리스트 A의 i 위치에 x를 삽입하는 함수이다. i 이후의 모든 원소들을 한 칸씩 옮겨야 하기 때문에 시간복잡도는 O(N)이 된다.(N은 리스트의 길이)

>>> A = [1, 2, 3]
>>> A.insert(1, 4)
>>> A
[1, 4, 2, 3]

원소 제거

1. remove()

A.remove(x)는 리스트의 원소 x를 제거한다. x는 원소의 인덱스가 아닌 원소의 값이다. x가 존재하지 않으면 ValueError가 발생한다. 시간복잡도는 O(N)이다.

>>> A = [1, 2, 3]
>>> A.remove(2)
>>> A
[1, 3]

2. pop()

A.pop(i)는 리스트의 i번째 원소를 제거하면서 해당 원소를 반환한다. remove와는 다르게 위치에 있는 값을 제거하는 함수이고 i를 지정하지 않으면 리스트의 마지막 원소를 제거하면서 반환한다. i를 지정하지 않은 경우 시간복잡도는 O(1)이고 i를 지정한 경우 시간복잡도가 O(N)이 된다.

>>> A = [1, 2, 3]
>>> A.pop(1)
2
>>> A
[1, 3]
>>> A.pop()
3
>>> A
[1]

3. del문

del문은 pop처럼 인덱스를 지정해서 항목을 삭제한다. pop과 다른 점은 삭제한 원소를 반환하지 않는 것이다. 리스트 슬라이싱을 통해서 여러개의 원소를 한 번에 삭제도 가능하다. 시간복잡도는 O(N)이다.

>>> A = [1, 2, 3, 4, 5, 6]
>>> del A[2]
>>> A
[1, 2, 4, 5, 6]
>>> del A[1:3]
>>> A
[1, 5, 6]

이외 함수들

index()

A.index(x)는 리스트 A에서 원소 x의 위치를 반환한다. 이 때 주의할 점은 리스트 A에 x가 여러 개가 있다면 가장 앞에 있는 인덱스를 반환하다. 시간 복잡도는 리스트를 순차적으로 모두 확인하므로 O(N)이 된다.

>>> A = [1, 2, 3, 4, 5]
>>> A.index(3)
2

count()

A.count(x)는 리스트 A에 x인 값을 갖는 원소의 개수를 반환한다. 시간복잡도는 O(N)이다.

>>> A = [1, 2, 2, 3, 3, 3]
>>> A.count(3)
3

sort()

A.sort(key, reverse)는 리스트 A를 값을 기준으로 오름차순으로 정렬해준다. 시간복잡도는 O(NlogN)이고 내림차순으로 정리하려면 reverse=True를 인자로 주어야 한다. 원하는 기준으로 정렬을 해주고 싶다면 key와 lambda를 사용하여 규칙을 정해주어야 한다.

>>> A = [4, 1, 3, 2]
>>> A.sort()
>>> A
[1, 2, 3, 4]
>>> A.sort(reverse=True)
>>> A
[4, 3, 2, 1]

reverse()

A.reverse()는 리스트 A의 원소들을 반전시켜서 다시 리스트 A에 저장한다. list[::-1]을 하는 것과 같다.

>>> A = [1, 2, 3, 4, 5]
>>> A.reverse()
>>> A
[5, 4, 3, 2, 1]

[백준][파이썬] 17406번 - 배열 돌리기 4

문제 번호 : 17406번 - 배열 돌리기 4
문제 출처 : https://www.acmicpc.net/problem/17406

Code

from itertools import permutations

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
val = []


def matrix_value(ans):
    for i in range(n):
        ans = min(ans, sum(matrix[i]))
    return ans


def rotate(rcs):
    r, c, s = rcs
    for i in range(1, s+1):
        tmp = matrix[r - 1 - i][c - 1 - i]
        x = r - i - 1
        y = c - i - 1
        for j in range(4):
            for k in range(2*i):
                nx = x + dx[j]
                ny = y + dy[j]
                matrix[x][y] = matrix[nx][ny]
                x, y = nx, ny
        matrix[r-1-i][c-i] = tmp


n, m, k = map(int, input().split())
a = [[] for _ in range(n)]
for h in range(n):
    a[h] = list(map(int, input().split()))
rotation = [[] for _ in range(k)]
for i in range(k):
    rotation[i] = list(map(int, input().split()))
answer = 1e9
orders = permutations(rotation)

for order in orders:
    matrix = [a[row][:] for row in range(n)]
    for rcs in order:
        rotate(rcs)
    answer = matrix_value(answer)

print(answer)

Idea

1. 회전하는 경우의 수를 순열을 통해서 구한다. K의 최대값이 6이기 때문에 6! = 720개의 경우가 만들어진다.
2. 각 경우의 수마다 배열을 복사하고 회전을 시킨 후 각 행마다 최솟값인지 확인한다.

[백준][파이썬] 17089 - 세 친구

문제 번호 : 17089번 세 친구
문제 출처 : https://www.acmicpc.net/problem/17089

Code

import sys

n, m = map(int, input().split())
relations = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]

friends = [set() for _ in range(n)]
for relation in relations:
    friends[relation[0]-1].add(relation[1])
    friends[relation[1]-1].add(relation[0])

num_friends = m
for a in range(n):
    for b in friends[a]:
        for c in friends[b-1]:
            if c in friends[a]:
                num_friends = min(num_friends, len(friends[a]) + len(friends[b-1]) + len(friends[c-1]) - 6)
if num_friends < m:                
    print(num_friends)
else:
    print(-1)

Idea

1. 입력된 친구가 모두 A, B, C의 친구인 경우 세 친구의 친구 수 합의 최대는 m - 6이다.
2. A를 정하고 B는 A의 친구 중 한명이고 C는 B의 친구이면서 A의 친구인 경우에서 친구 수의 최소값을 찾아낸다.
3. b > a, c > b 조건을 넣은 이유는 먼저 순회한 조합을 순회하지 않기 위함이다. 이 두 조건이 없다면 순열처럼 동작할 것이지만 이 조건으로 인해서 조합이 되어서 시간 복잡도가 줄어든다. 이 조건 두 줄만으로 1880ms에서 92ms로 시간이 확 줄었다.

[백준][파이썬] 2422번 - 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

문제 번호 : 2422
문제 출처 : https://www.acmicpc.net/problem/2422

Code

import sys

n, m = map(int, input().split())
answer = n * (n - 1) * (n - 2) // 6
nomat = [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    answer -= (n-2) - len(nomat[a-1] | nomat[b-1])
    nomat[a-1].add(b)
    nomat[b-1].add(a)

print(answer)

Idea

1. 초기 answer 값은 \( {}_n \mathrm {C}_3 \) 을 수로 나타낸 것이다.
2. nomat 리스트에는 각 맛 별로 조합이 좋지 않은 맛을 넣는다.
3. 2 가지가 정해진 상황에서 나머지 한 가지 맛을 고르는 경우의 수는 n - 2 이다.
4. 그 전에 경우의 수에서 없앤 경우의 수는 합집합의 길이가 된다.

예제 입력을 넣었을 때를 예시로 들면 다음과 같다.

    1. 모든 경우의 수는 5가지 맛 중 3가지를 뽑는 경우로 총 10이다.  
    2. 처음 (1, 2, X) 를 뽑는 경우의 수는 3가지이므로 전체 경우의 수에서 3을 빼준다.  
    3. (3, 4, X) 를 뽑는 경우의 수 중 전에 뽑은 경우가 없으므로 `nomat\[2\]`와 `nomat\[3\]`의 합집합의 길이는 0이다.  
    4. (1, 3, X) 를 뽑는 경우에는 (1, 2, 3) 인 경우와 (1, 3, 4) 인 경우를 그 전의 입력에서 뺐으므로 전체 경우의 수에서 1만 빼준다.

처음에 코드 제출했을 때는 파이썬 언어에서 시간 순위 1등이었는데 글 적을 때 되니까 밀려났다.