1. 문제 https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 num[i]; lottery(0, 0); cout

1. 구간합이란? 어떤 배열이 주어졌을 때 원하는 구간의 합을 말한다. 2. 구간합 알고리즘 구간합 개념 고등학교때 배운 수열의 합을 이용하여 원하는 구간의 합을 구하는 법을 배웠다. 자연수 n에 대하여 수열 A(n)의 1 ~ n까지의 합을 S(n)이라고 할 때 두 자연수 a ~ b까지의 합은 S(b) - S(a-1)이다. [증명] a > a >> b; for (int i = 1; i > A[i]; //S(b), S(a) 구하기 for(int i=1; i Ai; S[i] = S[i-1] + Ai; } cin >> a >> b; cout

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, ..

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/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net #define F first #define S second #include #include using namespace std; stack sta; int main(void) { cin.tie(0); ios_base::sync_with_stdio(NULL); long long int max, s, h; int n; while (1) { ci..

1. 문제 https://www.acmicpc.net/problem/14601 14601번: 샤워실 바닥 깔기 (Large) 첫 번째 줄에는 바닥의 한 변의 길이를 표현하는 자연수 K(1 ≤ K ≤ 7) 가 주어진다. 이때 바닥의 크기는 2K 가 됨에 유의하라. 두 번째 줄에는 배수구의 위치를 나타내는 자연수 x, y (1 ≤ x, y ≤ 2K) www.acmicpc.net #include using namespace std; int num; int map[128][128]; bool check(int x1, int y1, int x2, int y2) { for (int i = x1; i < x2; i++) { for (int j = y1; j < y2; j++) { if (map[i - 1][j - 1..

1. 문제 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 2. 풀이 단순히 모든 칸을 한칸씩 다 탐색했더니 시간초과가 나왔다. N의 최대값을 살펴보니 15이다. 최대 size는 2의 15승이므로 32,768이 된다. 즉, 최대넓이는 32,768 x 32,768 = 1,073,741.824로 10억이 넘어간다. 결국 10억이 넘는 칸을 모두 탐색할 경우 대충 10초가 나온다.(1억번 탐색하면 약 1초가 나오므로) 따라서 구역을 확인 후..

1. 재귀 함수란? 한자로 풀어서 해석하면 다시 "재(再)" 돌아올 "귀(歸)", 말 그대로 다시 돌아오다 라는 뜻이다. 프로그래밍의 관점에서 재귀란 "함수 자신을 다시 호출하다"라는 의미이다. 2. 재귀함수의 쓰임 재귀함수는 기본적으로 현재의 condition을 유지한 상태로 전의 작업과 비슷한 행동을 할 때 매우 유용한 알고리즘이다. 이러한 재귀함수의 특성때문에 stack, 분할정복 등의 많은 문제에서 활용되곤 한다. 다음은 재귀함수로 간단하게 구현할 수 있는 문제이다. https://wondrous-developer.tistory.com/1 [백준 17609] 회문 (C++) 처음 고민했던 사고과정과 이후 정답풀이를 같이 정리해 놓았다. 1. 문제 https://www.acmicpc.net/prob..