https://www.acmicpc.net/problem/11658 11658번: 구간 합 구하기 3 첫째 줄에 표의 크기 N과 수행해야 하는 연산의 수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 www.acmicpc.net 2차원 세그먼트 트리를 이용해서 문제를 해결했다. 코드 #include #include #include using namespace std; //2차원 세그먼트를 이용해서 문제를 해결 int n, m; vector board(1024, vector(1024, 0)); vector sgmtt(1024 * 2, vector(1024 * 2, 0)); void M..

https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 공간(3X3), 행, 열에 어떤 숫자가 있는지 체크하여 백트래킹을 이용해 문제를 해결했다 코드 #include #include #include #include using namespace std; int area[10][10]; //[공간][숫자] = (해당 공간에 해당 숫자가 있을때 : 1, 없을때 : 0) int row[10][10]; //[행][숫자] = (해당 행에 해당 숫자가 있을때..

https://www.acmicpc.net/problem/15669 15669번: 나무 위의 입자 트리란, 사이클이 없는 연결 그래프를 의미한다. 위 그림은 트리 모양의 입자가속기와 그 위의 어떤 정점에 놓인 특별한 입자 하나를 표시하고 있다. RB 입자라고 불리는 이 특이한 입자는 안정 www.acmicpc.net 1번 정점이 루트인 트리를 만들고, cache[100001][2]에 해당 정점이 루트인 서브트리에서 깊이가 홀수인 노드의 개수와 깊이가 짝수인 노드의 개수를 저장해 놓고, 도착점이 빨간색일 때 이동하는 간선의 총개수가 짝수개이므로 (짝수 깊이 노드, 짝수 깊이 노드) 또는 (홀수 깊이 노드, 홀수 깊이 노드)의 조합이어야 하고, 도착점이 검은색일 때는 이동하는 간선의 총개수가 홀수개이므로 (..

https://www.acmicpc.net/problem/20002

https://www.acmicpc.net/problem/2450 2450번: 모양 정돈 첫째 줄에는 모양의 전체 개수 N이 주어진다. N은 3이상 100,000이하이다. 둘째 줄에는 나열된 모양들을 나타내는 N개의 정수가 빈 칸을 사이에 두고 주어지는데, 정수 1은 세모를, 정수 2는 네모를, www.acmicpc.net 세모, 네모, 동그라미가 어떤 순서로 배치되는지에 따라 각각 경우를 next_permutation를 통해 고려하고, 해당 경우로 구역을 나눴을 때 [도형a][도형b] = 개수 (도형a의 구역에 속해있는 도형b의 개수)를 세고, 이를 통해 도형1을 먼저 맞추고, 도형2,3을 맞추는 방식으로 문제를 해결했다. 코드 #include #include #include using namespac..

https://www.acmicpc.net/problem/2671 2671번: 잠수함식별 입력에 들어있는 스트링을 읽고, 이것이 잠수함의 엔진소리를 나타내는 스트링인지 아니면 그냥 물속의 잡음인지를 판정한 후, 잠수함의 엔진 소리에 해당하는 스트링이면 "SUBMARINE"을 출력하고 www.acmicpc.net regex 라이브러리 이용한 정규표현식을 통해 문제를 해결했다 코드 #include #include #include #include #include using namespace std; //정규표헌식 //regex 라이브러리 이용 int main() { cin.tie(NULL); ios_base::sync_with_stdio(false); regex reg("(100+1+|01)+"); strin..