해나의 컴공생존기

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과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다 풀이 백트래킹에 대한 감이 아직 없는건지 N과M(1)과 비슷한 문제인데 꽤 헤맸다. 하지만 그저 간단하게 for문을 이전 n 값부터 돌리면 되는 거였다. num[n-1]을 위해 num은 index 1부터 사용했다. 몇개 더 풀어봐야할..

문제 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개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다 위 그림에서..

https://www.acmicpc.net/problem/1780 문제 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다. 출..

모든 경우의 수를 하나하나 확인해봐야하는 문제다! 엥 간단하다! 하고 덤볐는데 for문 8개 돌리기밖에 생각이 안났다. 어쩌지어쩌지하다가 재귀를 풀면 될 것 같다..! 라고생각했고 배열을 만들어 맨 앞에서 부터 차례대로 채워 나가면 되겠다는 생각을 했다. 인자 n번째 칸을 결정하는 함수를 만든뒤 차례차례 뒤에를 채울 수 있게 재귀를 돌렸다. n번째칸이 문제에서 제시된 M과 같다면 모아놓은 배열을 출력하고 다시 새로운수를 만들면된다. #include using namespace std; int N, M; int num[10]; int check[10]; void NM(int n) { if (n == M) { for (int i = 0; i < M; i++) { cout M; NM(0); return 0; }

별로 어려운 문제는 아니다! 답변을 "재귀함수는 자기 자신을 호출하는 함수라네" 하는 문구를 기준으로 생각해야한다. 답변 앞에를 출력하고 재귀함수를 부르고 답변뒤에는 출력하면 재귀가 알아서 잘 실행이된다! #include using namespace std; int n; void chat(int x) { if (x == n) { for (int i = 0; i < x; i++) cout

찾으려는 값이 들어간 2*2 박스의 첫 칸만 안다면 찾으려는 값도 쉽게 찾을 수 있다 순서가 필요하기 때문에 고민이 되는 문제이다 먼저 제일먼저 생각나는건! 재귀로 배열을 채우고 주어진 배열의 값을 출력하는것이다! 하지만 이런 방법은 너무 비효율적일 것 같다. 2의 15승까지 될 수 있는데..이는너무 오래걸린다. 그래서 생각해본건 4개로 나누고 찾으려는 숫자가 있는 범위를 4칸 중에 한 칸를 선택하고, 또 그 한 칸을 4개로 나누고 범위를 찾고 하면서 구체화 시키면 될 것 같다. 정리하자면 전체 칸을 4칸으로 나누고 각 칸은 그 칸의 제일 앞에있는 수로 관리하는 것이다. 각 칸의 맨 앞에 있는 수의 좌표와 값을 알아야하는데, 규칙을 찾아보면 다음과 같이 된다는 것을 알 수 있다. Z함수는 a,b점이 대표..

하노이탑은 재귀로 아주 유명한 문제이다! 이 문제는 아주 복잡하기 때문에 절차지향적으로 하나하나 생각하면 답이 전혀 안나온다... n개일떄 어떻게 해야하나? 를 생각해야 답이 나온다. hanoi(int a,int b, int n) 이라는 함수는 a에서 b까지 n개의 칸을 옮긴다고 해보자 n칸의 탑을 a에서 b까지로 옮긴다면 6-a-b칸을 이용해야한다. 6-a-b칸에 n-1개의 칸을 옮겨놓고 → hanoi(a,6-a-b,n-1) 맨 밑에 있던 n칸을 b로 옮기고 6-a-b칸에 있는 n-1개의 탑을 b칸으로 옮기면 된다! → hanoi(6-a-b,b,n-1) 이동한 횟수를 매번 세는 것은 어렵다. 점화식을 이용하여 식을 구해보자! n번째 옮기는 식이 k번이라면 n+1번째는 2*k +1 이 된다. n개를 옮기..

처음에는 그냥 문제 그대로 a를 b번 곱해준 뒤 c로 나눠서 출력해줬다. 이렇게 쉬울리가 없는데 하면서 실행시켜보니 음수값이 나왔다... 코드를 보면 음수값이 나올 이유가 전혀 없었는데...곰곰히 생각해보니 overflow가 일어났다는 것을 알 수 있었다. 그래서 곱해주는 것과 동시에 C로 계속 나눠주었다. 하지만 이렇게 하니 A,B,C가 커질수로 시간이 너무 오래 걸렸다. 이 문제의 핵심은 재귀이다 결국 a의 b승을 c로 나눴을 때 나머지를 구하는 것이다. b가 짝수이면 : a^b = a^(b/2) x a^(b/2) b가 홀수이면 : a^b = a^(b/2) x a^(b/2 + 1) 위 식을 이용하여 분할정복 해야한다. 분명 맞는데...왜 자꾸 틀리지 했더니 곱셈과정에서 int의 범위를 넘어가는 것 같..