곧죽어도 콛잉

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 새로운 주제인 백트래킹이다. 재귀를 응용해서 경우의 수를 찾을 수 있다. 문제를 읽어보면 부분집합들의 합을 찾아내야한다. 주어진 1) 수열의 부분집합을 찾고 2)그 부분집합의 합을 구해내는 것이 핵심이다. 그러나 대게 막연할 것이다. 따라서 다음과 같이 그림으로 도식화해보자. 그림을 보며 생각해보자. 위의 그림은 제시된 수열이 {1,2,3}일때를 가정했다. 우선..

https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 이것 역시 앞의 문제들과 유사하게 풀면된다. 반복되는 모양을 캐치해서 이를 어떻게 구현할지가 키포인트 같다! 나는 단순하게 2차원 배열을 통해 모양이 시작되는 각 좌표를 재귀함수가 호출될때마다 넘겨주었다. 위의 패턴들의 느낌을 봐보자. 사각형을 9개의 사각형으로 나눠야할 거 같지 않은가? 근데 또 각각의 사각형은 또 9개의 사각형을 나눠지고 ... 이게 계속해서 반복된다..

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 앞서한 종이의 개수와 논리와 완전히 똑같다! 이건 BOJ 1760 종이의 개수보다 훨씬 쉬운문제다! 1) 하나의 숫자로(0, 1) 채워져있는지 확인하고, 1-1) 만약 채워졌다면, 그 숫자를 확인한 후 개수를 세준다. 1-2) 만약 안채워졌다면, 사각형을 4등분한 후 각 사각형마다 다시 1) 과정을 반복한다. 토씨하나 틀리지 않다... 실제로 코드도 논리도 거의 똑같다...

https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 재귀의 기본형인 문제. 앞으로 갖고올 문제들도 다 이거의 응용 아니면 동일한 문제다. 큰 개념은 1) 하나의 숫자로(0, -1, 1) 채워져있는지 확인하고, 1-1) 만약 채워졌다면, 그 숫자를 확인한 후 개수를 세준다. 1-2) 만약 안채워졌다면, 사각형을 9등분한 후 각 사각형마다 다시 1) 과정을 반복한다. 이런 논리로 재귀를 통해 해결할 수 있다. 말은 쉬우나 .. 구현이 처음할..