[Deque 선언] #include #include using namespace std; deque DQ; [덱의 주요 기능] 멤버 함수 설명 push_front deque의 앞에 원소 추가 push_back deque의 뒤에 원소 추가 pop_front 앞의 원소를 제거 pop_back 마지막 원소를 제거 front deque의 앞의 원소를 반환 back duque의 마지막 원소를 반환 size deque의 크기를 반환 empty 비어있는지 확인해주는 기능, 저장한 원소가 있으면 false, 없으면 true 반환 https://math-coding.tistory.com/219 [Data Structure] Deque 사용법 c++ STL 중 하나인 Deque에 대한 설명입니다. Deque Deque는 ..

[목차] Deque이란? Deque 기능 주요 기능 소개 구현해보기 주요 기능들의 성능 분석 예제 코드 Deque의 특징 예제 문제 1. Deque이란? 선형 자료구조에는 Stack, Queue, Deque, Linked List가 있다. Duque는 선형 자료구조의 한 종류이다. Double Ended Queue의 줄임말로 양쪽에서 삽입과 삭제가 가능한 Queue를 말한다. 주로 배열을 뒤집어서 원소를 추가/삭제하는 경우에 Deque를 쓰면 효율적으로 구현할 수 있다. C++과 java 모두 Deque을 지원한다. 따라서 그냥 가져다 쓰면 된다. 여기서는 C++에서 Deque의 주요 기능들을 간단히 소개하고 구현해본다. 예제는 [백준 5430번]을 이용한다. 2. Deque의 기능 1) 주요 기능 문제..

https://cplusplus.com/reference/deque/deque/ https://cplusplus.com/reference/deque/deque/ difference_typea signed integral type, identical to: iterator_traits ::difference_type usually the same as ptrdiff_t cplusplus.com

1. 문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 2. 풀이 아이디어 알고리즘 코드 #include #include #include #define F first #define S second #define IN(Y, X) Y >= 0 && Y = 0 && X < N using namespace std; queue q; int dy[4] = {0, 1, 0, -1}; int dx[4] = {1, 0, -1, 0}..

#include #include #include #include #define F first #define S second #define IN(Y, X) Y >=0 && Y =0 && X < M using namespace std; int N, M, cheese, board[100][100]; bool visit[100][100]; queue q; vector melt; int dy[4] = { 0, 1, 0, -1 }; int dx[4] = { 1, 0, -1, 0 }; void BFS(int y, int x) { visit[y][x] = true; q.push({ y, x }); while (!q.empty()) { pair front = { q.front().F, q.front()..

[목차] 완전 탐색과 DP로 푼 LIS LIS 알고리즘 아이디어 알고리즘 알고리즘 분석 예제 정리 1. 완전 탐색과 DP로 구현한 LIS 이 전의 글에서는 LIS를 구하는 알고리즘을 완전 탐색과 동적 계획법으로 구현했었다. 동적 계획법 풀이는 O(N²)의 시간 복잡도를 가졌었다. 하지만 이분 탐색을 이용하면 O(N logN)의 시간 복잡도로 더 빠르게 해결할 수 있다. 이번 글에서는 이분 탐색을 이용하여 O(N log N)의 시간 복잡도로 구현해보려고 한다. 이분 탐색의 LIS를 이해하려면 이분 탐색의 lower_bound() 함수와 upper_bound()함수에 대해 알고 있어야 한다. 또한 DP로 푼 LIS알고리즘도 이해하고 오면 도움이 된다. 따라서 앞의 부분에 대한 이해가 안되어있다면 최소한 이분..

최적화 문제를 결정 문제로 바꾸어 해결하면 매우 단순한 생각으로 바꿀 수 있다. 예를 들면 Parametric Search를 결정 문제로 바꾸면 단순한 이분 탐색으로해결할 수 있고 부분수열의 합이 S이상것들 중 최대 최소를 구할 때에도 합이 S인가?라는 결정 문제로 바꾸면 단순한 부분수열의 합 문제로 바꾸어 해결할 수 있다.