728x90 반응형 알고리즘&자료구조/덱2 백준 1021 난이도 : 중상 해결 방법 : 풀이 참고(https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x07/solutions/1021.cpp) #include #include #include using namespace std; int N, M; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N >> M; deque DQ; // 원소의 위치 for (int i = 1; i > position; while (DQ.front() != position) { // front에 뽑아내려고 하는 원소의 위치가 없는 경우 // 2번과 3번에서 어떤 연산을 수행하는게 더 최솟값을 구할수 있는.. 2024. 4. 11. 덱(Double Ended Queue) 덱의 정의 양쪽 끝에서 삽입과 삭제가 가능한 자료구조 삽입, 삭제, 제일 앞/뒤의 원소 확인이 모두 O(1) 시간복잡도를 가지고 있다. 제일 앞/뒤가 아닌 원소들의 확인/변경이 불가능하지만 STL Deque에서는 인덱스로 원소에 접근할 수 있다. 구현 방법 스택이나 큐처럼 배열 또는 연결 리스트로 구현할 수 있지만 배열을 이용하는 게 쉽기 때문에 배열로 구현을 했다. 원소를 담을 배열 앞쪽과 뒤쪽을 가리킬 변수 2개 초기값이 0이 아니라 설정한 배열 크기의 중간값으로 잡는다. 왜냐하면 큐에서는 배열의 앞쪽에서는 제거만 발생하고 뒤쪽에서 삽입되는 형태이기 때문에 원소들이 차지하는 공간이 오른쪽으로 이동하면서 확장되지만, 덱에서는 양쪽으로 이동하면서 확장되기 때문에 초기값을 0으로 잡거나 배열의 최대 크기로.. 2024. 2. 4. 이전 1 다음 728x90 반응형
