Roble

#include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); int n, a, b; cin >> n; while(n--){ cin >> a >> b; cout

#include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout

#include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int a, b; cin >> a >> b; cout

0x00 알고리즘 설명 정점과 간선으로 이루어진 자료구조인 그래프라는 자료구조에서 모든 노드를 방문하기 위한 알고리즘이다. 0x01 예시 원리를 이해해보자 우선 BFS 알고리즘에서는 좌표를 담을 큐가 필요하다. BFS 알고리즘이 시작되면 우선 (0, 0)에 방문했다는 표시를 남기고 해당 칸을 큐에 넣는다. 이 초기 세팅이 끝난 후에는 큐가 빌 때까지 계속 큐의 front를 빼고 해당 좌표의 상하좌우를 살펴보면서 큐에 넣어주는 작업을 반복하게 된다. 첫 시작(큐의 front)을 기록해놨으면 pop을 하고 그 점으로부터의 상하좌우 칸을 보는데, 이 중에서 파란색 칸이면서 아직 방문하지 않은 칸을 찾을것이다. 위 상황을 보면 (0,0)과 상하좌우로 인접한 (0,1)과 (1,)은 모두 파란칸이면서 방문하지 않았..

0x00 수식의 괄호 쌍이란? 괄호를 빼놓고 봐도 위에껀 올바른 수식의 괄호 쌍이고 밑에껀 그렇지 않다는게 딱 눈에 들어올 것이다. 이와 같이 수식의 괄호 쌍이란, 주어진 괄호 문자열이 올바른지 판단하는 문제이다. 0x01 문제 해결을 위한 관찰 올바르게 문자열을 읽을때 문자열을 앞에서부터 읽어나갈 때, 닫는 괄호는 남아있는 괄호 중에서 가장 최근에 들어온 여는 괄호와 짝을 지어 없애버리는 명령이라고 생각해도 된다. 문자열을 다 읽었고 남아있는 괄호가 없는 것으로 보아 모든게 다 짝이 잘 맞았다는걸 알 수 있다. 이처럼 올바른 괄호 쌍일 경우 여는 괄호를 읽을 때 마다 저장하다가 닫는 괄호를 읽을 때 가장 최근에 들어온, 즉 가장 끝에 있는 여는 괄호와 짝을 이루게 해주고 pop을 하면 올바른 괄호 쌍인..

https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net #include using namespace std; int main(void){ ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; //1)n,m 입력받기 deque DQ; for(int i=1; i > val; int idx = find(DQ.begin(), DQ.end(), val) - DQ.begin(); while(DQ.fro..

0x00 정의와 성질\ 정의 양쪽 끝에서 삽입과 삭제가 전부 가능하다. 덱은 deque고 Double Ended Queue라는 뜻이다. 성질 덱에서도 삽입, 삭제, 제일 앞/뒤 원소의 확인이 다 O(1). 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능한데 독특하게도 STL deque에서는 인덱스로 원소에 접근할 수 있다. STL stack, queue에서 불가능했던걸 생각하면 꽤 독특한 일이다. 0x01구현 덱도 스택이나 큐처럼 배열 혹은 연결 리스트 둘 다를 가지고 구현할 수 있지만 배열을 이용하는게 구현이 더 쉽기 때문에 배열을 이용해 구현해 볼것이다. 일단 필요한 변수는 큐랑 똑같이 원소를 담을 큰 배열 한 개와 앞쪽, 뒤쪽을 가리킬 변수 두 개이다. 이 때 head와 tail을..

0x00 정의와 성질 정의 큐는 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조이다. 스택에서는 먼저 들어간 원소가 나중에 나왔는데 큐에서는 먼저 들어간 원소가 먼저 나오게 된다. 스택을 FILO(First In Last Out)이라고 한 것과 비슷하게 큐를 FIFO(First in First Out)이라고 하기도 한다. 성질 큐에서는 추가되는 곳을 rear(뒤쪽)라고 하고, 제거되는 쪽을 front(앞쪽)이라고 한다. 0x01 기능과 구현 선형 배열로 만든 큐 head는 가장 앞에있는 원소의 인덱스이고 tail은 가장 뒤에 있는 원소의 인덱스 +1 이다. 꼭 이렇게 안두고 tail을 가장 뒤에있는 원소의 인덱스로 두어도 괜찮다. 값을 추가하면 head는 변함이 없고 tail은 한 칸..