해나의 컴공생존기

https://www.acmicpc.net/problem/15651 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 풀이 #include using namespace std; int N, M; int check[10]; int num[10]; void NM(int n){ if(n==M){ ..

문제 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. 출력 첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다 풀이 백트래킹 문제 너무 어렵다…. 처음에는 연속되는 수열을의 합만 되는줄 알고 풀었다가 틀렸다. 이는 숫자 하나하나 보며 해당 숫자를 더했을때와 더하지 않았을때를 고려한다. 코드 자체는 N과 M 문제보다 쉬운 것 같은데.. 백트래킹 자체가 나한테 잘 안 와..

https://www.acmicpc.net/problem/1992 문제 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다. 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다 위 그림에서..

이번에는 몇모둠이 있나?에 대한 문제이다. 1을 찾아서 BFS를 진행하고 또 1을 찾아서 BFS를 하고 이런식으로 반복하면 금방 개수를 알 수 있지 않을까? 하는 생각이 들었다. 코딩해보자~! 우왕!! 한번에 맞았다. 디테일이 부족해서 계속 while문을 돌아 여러번에 디버깅이 필요햇지만 그래도 크게 어려움을 겪지 않고 성공했다! #include #include #include using namespace std; int farm[50][50]; int dx[4] = { 1,0,-1,0 }; int dy[4] = { 0,1,0,-1 }; int main() { int a, num = 0,N, M ,K, x, y, flag = 0,sx,sy; cin >> a; for (int i = 0; i < a; i+..