1. 문제 https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 구간 K만큼의 합을 구하고 그 중에서 최댓값을 구하는 문제이다. 2. 풀이 구간합 https://wondrous-developer.tistory.com/47 동적 계획법을 이용하여 구간합 구하기 1. 구간합의 의미와 시간복잡도 어떤 배열이 주어졌을 때 원하는 구간의 합을 말한다. 2. 구간합 알고리즘 구간합 고등학교때 배운 수열의 합을 이용하여 원하는 구간의 합을 구하는 법..

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net #include using namespace std; int seq[20]; int N, S, ans; void func(int cur, int cnt, int sum) { if (cur == N) { if (sum == S && cnt != 0) ans++; return; } //다음 원소를 포함한 경우와 포함하지 않은 경우로 나누기 func(cur + 1, ..

필수 선행 개념: 분할 정복, 이분 탐색 배열 arr = {1, 3, 5, 10, 2}이 있다고 해보자. 특정 구간의 최댓값, 최솟값, 구간합, 구간곱을 구한다고 할 때 질문이 하나라면 O(N)에 해결할 수 있다. 만약 질문이 10만개라면 어떨까? O(N²) = 약 11자리 이므로 1초안에 해결이 불가능하다. 이때 세그먼트 트리를 이용하면 O(log N)에 해결이 가능하다. 배열의 크기는 자료의 개수(N)에 대해 N보다 크거나 같은 2의 제곱수에 두배한 크기만큼 미리 할당해두어야 한다. 시뮬레이션 1. 세그먼트 트리 초기화하기 int init(int st, int en, int node){ if(st == en) return tree[node] = arr[st]; int mid = (st + en) / ..

트리란? 트리란 싸이클이 없는 무방향 그래프를 말한다. 싸이클이 존재하지 않아서 모든 노드가 루트가 될 수 있다. 마치 실로 연결된 구슬이 있는데 한 구슬을 잡아서 들어올릴 때마다 그 구슬이 루트가 되고 트리 구조가 형성되는 것과 비슷하다. 트리 순회하기 그래프의 구조를 가지므로 BFS와 DFS를 이용할 수 있다. 이 과정에서 부모의 정보 or 깊이의 정보가 필요한 경우 중간중간에 기록해주면 된다. 1. BFS void bfs(int root){ queue q; q.push(root); while(!q.empty()){ int cur = q.front(); cout

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net int N, M; int check[100]; int seq[100]; void backtracking(int cur){ //base condition if(cur == M) { for(int i=0; i

https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 재귀가 3번 반복되므로 시간복잡도가 O(n의 log2 3승)이다. 잘못하면 시간초과가 날 수 있으므로 연산량을 최대한 줄이는 것이 좋다. #include using namespace std; int map[6143][3702]; void fractal(int size, int x, int y) { if (size == 1) return; if (size == 3) { for (int i = 0; i < 3; i++) { for (int j = 0; ..

#define SIZE 2187 #include using namespace std; int map[SIZE][SIZE]; void fractal(int size, int x, int y) { if (size == 1) return; if (size == 3) { for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (i != 1 || j != 1) map[x + j][y + i] = 1; } } } size /= 3; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (i == 1 && j == 1) continue; else fractal(size, x + size * j, y +..