광그로

deque : double ended queue 멤버원형설명atreference at( size_type _Pos ); const_reference at( size_type _Pos ) const;특정 위치의 원소의 참조를 반환backreference back( ); const_reference back( ) const;마지막 원소의 참조를 반환beginconst_iterator begin() const; iterator begin();첫 번째 원소의 랜던 접근 반복자를 반환clearvoid clear();모든 원소를 삭제emptybool empty() const;아무것도 없으면 true 반환enditerator end( ); const_iterator end( ) const;마지막 원소 다음의(미 사용..

https://www.acmicpc.net/problem/1406 linkedlist로 풀 수도 있고, stack으로도 풀 수 있는 문제입니다.저는 stack으로 풀 수 있다는 걸 인지하는 데에 약간의 시간이 필요했습니다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include #include #include using namespace std; stack left_stack;stack right_stack; int main(){ char str[100001]; cin >> str; for (int i = 0; i > test; char a, b; char tm..

https://www.acmicpc.net/problem/10799 stack의 size를 통하여 계산을 통하게 되면 시간초과가 발생하여 수정하였습니다. 123456789101112131415161718192021222324252627282930313233343536#include #include #include using namespace std; stack st; int main(){ char s[100001]; cin >> s; int result = 0; int cnt = 0; for (int i = 0; i

문제 : https://www.acmicpc.net/problem/2667 DFS를 이용하여 풀이하였다.동서남북 방향 중, map[y][x] = 1 && visited[y][x] = 0 인 조건일 때, 움직일 수 있다.방문한 지점들을 카운트 해주며, 시작지점으로부터의 'DFS 사이클'이 끝나면 res에 카운트되어진 값을 넣어준다. #include #include #include #include using namespace std; int map_size; int map[26][26] = { 0 }; char row[26] = { 0 }; int visited[26][26] = { 0 }; vector res; int cnt=0; void DFS(int y, int x) { cnt++; visited[y]..

문제 : https://www.acmicpc.net/problem/9466 #include #include #include #include using namespace std; int test_case; int student_num; int graph[100001]; bool visited[100001]; bool finished[100001]; int cnt=0; void DFS(int now_pos) { visited[now_pos] = true; int next = graph[now_pos]; if (visited[next] == true) { // != if(vistied && finished) else 처리에서 달라진다. if (finished[next] == false) { int first_..

문제 : https://www.acmicpc.net/problem/2331 문제의 INPUT을 배열해보면 위의 그림과 같은 형식으로 나오게 된다. 다음 숫자(next number)를 구하는 방법은 while (A != 0) { calcul_res += (int)pow(A % 10, P); A /= 10; } 을 이용하면 되고, 백터의 처음 부터 끝까지를 탐색하며, 다음 숫자와 동일한 경우 함수를 끝마친다.그렇지 않을 경우, 백터에 지속적으로 다음 숫자를 추가해준다. #include #include #include using namespace std; int A, P; int calcul_res = 0; int res = 0, position = 0; vector arr; int function() { a..

문제 : https://www.acmicpc.net/problem/10451 #include #include #include #include #include #include using namespace std; vector graph[1001]; bool visited[1001] = { false }; int edge_num, vertex_index;//edge_num = vertex_num int cnt = 0; void DFS(int position, int start_pos) { visited[position] = true; for (int i = 0; i < graph[position].size(); i++) { int next_position = graph[position][i]; if (nex..

문제 : https://www.acmicpc.net/problem/1707 모든 edge의 양 끝에 vetex가 존재할 때, 각 vertex의 색깔이 다를 경우, 이분 그래프의 조건을 충족시킨다. #include #include #include #include #include #include //edge의 양 끝 vertex는 서로 다른 색깔을 가져야한다. using namespace std; int vertex_num, edge_num; vector graph[20001]; int colored[20001];//0:none 1:blue 2:red void DFS(int position, int color) { colored[position] = color; for (int i = 0; i < graph..

문제 : https://www.acmicpc.net/problem/11724 graph를 행렬화 시켜서 bfs를 돌려보았더니, 시간이 오래걸리는 것이 느껴졌다.이전, 1260 문제 풀이(http://rhkdrmfh.tistory.com/30) 중 두번째의 방법과 유사하게 풀이하였다. 연결 요소가 N개 존재할 때, BFS 혹은 DFS는 N번 시행되어야한다.for (int i = 1; i > vertex_num >> edge_num; for (int i = 0; i > vertex_left >> vertex_right; graph[vertex_left].push_back(vertex_right); graph[vertex_right].push_back(vertex_l..

문제 : https://www.acmicpc.net/problem/1260 DFS BFS 1. GRAPH를 행렬화#include #include #include #include #include #include using namespace std; int arr[1020][1020]; bool visited[1020]; int vertex_num, edge_num; stack DFS_NUM; queue BFS_NUM; void DFS(int start) { visited[start] = true; cout start_vertex; for(int i=0; i> vertex1 >> vertex2; arr[vertex1][vertex2] = arr[vertex2][vertex1] = 1; } DFS(start_..