www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 미세먼지를 확산하는 함수를 만들고, 공기청정기를 작동하는 함수를 만들어 미세먼지가 확산하고 공기청정기가 작동하는 것을 t번 반복한다. 공기 청정기를 작동은 공기청정기에 먼저 들어오는 미세먼지 순으로 deque에 저장하고, pop_front(); push_back(0);을 해서 공기청정기가 정화하는 것과, 공기청정기에서 바람이 나오는 것을 적용한다. 그렇게 움직여진 미세먼지를 board에 적용한다. 코드 #in..

www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 상어의 정보를 따로 저장해 놓는다. Search()를 통해 가장 가까운 물고기를 먹는데, 먹을 수 있는 거리가 가장 가까운 물고기가 많을 때를 위해 우선, 거리가 가장 가까운 물고기 들을 모두 저장해 놓은 뒤 가장 위에, 가장 왼쪽 우선순위로 정렬을 한 뒤 가장 앞의 물고기를 먹는다 그리고 Search()는 물고기를 먹는데 걸린 시간을 반환한다 이때 먹을 수 있는 물고기가 없을때 -1을 반환하며 이때부터..

www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 구간의 곱을 나타내는 세그먼트 트리를 만들고 세그먼트 트리의 쿼리와 업데이트를 이용해 문제를 해결했다. 세그먼트 트리를 나타내는 배열의 크기를 넉넉하게 n*4로 설정했다. 코드 #include #include #include using namespace std; int n, m, k; vector input_data; vector sgmtt; //세..

www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net 스택을 이용하여 문제를 해결했다. 코드 #include #include #include #include using namespace std; int main() { cin.tie(NULL); ios_base::sync_with_stdio(false); while (1) { string input; stack s; bool check = true; getline(cin, input); if (inp..

www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 최소 공통 조상(LCA) 문제 해결방법을 이용하여 방문 구간의 최소 값을 저장하는 세그먼트 트리를 이용해 문제를 해결했다. 트리를 만들고 트리를 순환하면서 해당 노드의 travel_num를 저장하고, travel_num가 나타내는 노드를 저장한다. 그리고 vector visited로 방문하는 순서를 저장한다. 또한 vector node_first_find(100001, 0)에 here노드를 몇번째에 처..

www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 세그먼트 트리의 쿼리와 업데이트를 이용해서 문제를 해결했다. 세그먼트 트리에 사용하는 각 구간의 합을 저장하는 배열을 넉넉하게 4*n으로 했다. 코드 #include #include #include using namespace std; int n, m, k; vector range_sum; //세그먼트 트리 vector input_data; //세그먼트..