반응형 queue5 baekjoon - python - 18258 www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net # @Author YoungMinKim # baekjoon from collections import deque import sys N = int(sys.stdin.readline()) class queue: def __init__(self): self.ls = deque([]) def push(self,num): self.ls.append(num) def pop(self): if se.. 2020. 9. 20. baekjoon - python - 11866 www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net # @Author YoungMinKim # baekjoon from collections import deque import sys a,b = map(int,sys.stdin.readline().split()) q = deque([i for i in range(1,a+1)]) result = [] while len(q) != 0: q.rotate(-b+1) result.append(q.popleft()) x= ', '.join(map(str,result)) print('') 2020. 9. 14. baekjoon - python - 2164 www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net from collections import deque import sys N = int(sys.stdin.readline()) q = deque([]) for i in range(1,N+1): q.append(i) while len(q) != 1: q.popleft() x = q[0] q.popleft() q.append(x) print(q[0]) 2020. 9. 13. Queue - C와 Python 비교 - 2 지난 원형큐 설명에 이어 deque(덱 큐)에 대해 설명하겠다. 덱 큐는 원형큐에 비해 매우 파워풀하다. 원형큐는 front가 삭제 rear가 삽입으로 정해져 있었다면 그에 비해 덱큐는 front와 rear가 모두 삭제와 삽입이 자유롭다는 것이다. 사실 이는 덱이라고 불리지만 원형큐로 구현하면 시간복잡도가 O(1) 이기 때문에 효율적이다. 그래서 덱큐라고 명칭한다. 덱큐와 원형큐가 다른 점은 앞서 말했듯이 front와 rear가 모두 삭제가 가능하다는 것이다. 이를 구현하기 위해선 원형큐에선 시계방향의 회전만 했다면 덱큐는 반시계방향 회전을 한다. 이로 인해 delete_rear와 add_front가 구현될 수 있다. 덱큐는 원형큐를 상속하여 구현해보겠다. 일단 python코드이다. # 덱큐 -> 원형큐.. 2020. 7. 13. Queue - C와 Python 비교 Queue는 대표적인 FIFO(First In First Out) 알고리즘이다. 즉 선입선출으로 먼저 들어온 값이 먼저 나가는 구조이다. LIFO구조인 stack과 비교된다. 구조상으로 스택과 다른 점은 삽입과 삭제 연산의 위치가 다르다는 것이다. 스택은 맨 위에부터 꺼내 쓰고 꺼내서 빼는 구조로 삽입과 삭제 연산의 위치가 같지만 Queue는 앞뒤에 문이 있다고 생각하면 된다. 따라서 앞의 문은 front, 뒤에 문은 rear 이다. 삽입이 일어나는 곳은 rear, 삭제가 일어나는 곳은 front 이다. 기본적으로 큐의 종류는 선형큐,원형큐,덱큐,우선순위 큐가 있다. 이 중 가장 기본적으로 선형큐의 구현을 보여줘야하지만 선형큐는 다른 큐에 비해 비효율적인 면이 있다. 왜냐하면 삭제연산에서 리스트의 모든 .. 2020. 7. 13. 이전 1 다음 반응형
