https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비..

https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다..

이번 포스팅에선 큐의 변형인 원형 큐(Circular Queue)에 대해 알아보겠습니다. 큐에 대한 사전 지식이 없다면 이해가 어려울 수 있으니, 미리 개념을 습득하고 오시길 바랍니다. [큐(Queue) 개념 이해하기] https://mengu.tistory.com/30?category=931463 [자료구조] 큐(Queue) 개념 및 코드 구현 이번 포스팅에선 큐(Queue)의 개념과 코드 구현을 할 것이다. 만약 스택(Stack) 개념을 알지 못한다면 이전 포스팅을 보고 오자. [이전 포스팅 URL: https://mengu.tistory.com/29] [자료구조] 스택(Stack) 개념.. mengu.tistory.com 목차 📃 원형 큐(Circular Queue) 정의 및 원리 📃 원형 큐 구현..

오늘은 자료구조 중 하나인 덱(Deque)에 대해 알아보겠습니다. 덱은 스택, 큐와 아주 유사한 자료구조이며, 스택/큐의 단점을 보완하고 장점을 가져왔기 때문에 유용하게 쓰입니다. 목차 📃 덱(Deque) 개념 📃 덱(Deque) 코드 📃 덱(Deque) 예제 덱(Deque) 개념 📌 정의 덱은 스택/큐와 같은 일차원의 선형 자료구조입니다. 스택과 큐 연산을 모두 지원하기에, 양 끝에서 삽입과 삭제가 가능한 자료구조입니다. 내부가 double-linked list(양방향 연결 리스트)로 구현되어 있습니다. 📌 시간 복잡도 O(1) 양방향 연결 리스트로 구현되어 있어, 양 끝 요소의 추가/삭제가 O(1)를 만족합니다. 그에 반해 List는 고정된 사이즈의 메모리를 갖는 배열로, 첫 번째 요소를 삭제하면 모..

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다. 배열에 정수 x (x ≠ 0)를 넣는다. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1≤N≤100,000)..

이번 포스팅에선 우선순위 큐에 대해 알아보겠습니다. 큐, 스택에 대한 이해가 없으신 분은 밑의 포스팅을 먼저 보고 와주시면 감사하겠습니다. 본 포스팅은 python으로 진행합니다. [스택 개념 및 코드] https://mengu.tistory.com/29?category=931463 [자료구조] 스택(Stack) 개념 및 코드 구현 자료구조 중 하나인 스택(Stack)에 대해 알아보고, 직접 코드로 구현해보자. 배열 구현과 연결 리스트 구현 모두 해볼 것이다. 들어가자. 스택(Stack) 개념 가장 나중에 넣은 데이터를 가장 먼저 빼 mengu.tistory.com [큐 개념 및 코드] https://mengu.tistory.com/30?category=931463 [자료구조] 큐(Queue) 개념 및 ..