승쨩개발공부

백트레킹은 모든 경우의 수를 재귀적으로 탐색할떄 사용한다.for문으로도 가능하지만 n개의 숫자가 늘어날수록 중첩for문을 해야하니 효율적이지 못할 수 있다. 1. 아이디어 - 백트레킹 재귀함수 안에서, for문 돌면서 숫자 선택(이떄 방문여부 확인) - 재귀 함수에서 m개를 선택할경우 출력 - n은 사용할 숫자 갯수 m은 열 2. 시간복잡도 백트레킹은 중복이 가능할시 O(N^N), N = 8까지 중복이 불가시 O(N!) N = 10까지 중복 불가 조건 8까지 3. 자료구조 방문 여부 확인 bool[] 선택값 입력 배열 int[] N = 4 M = 3일떄 구조 예제입력2

이전 문제들과 분할법은 똑같지만입력이 붙어있으니 string으로 받아야하고전체영역이 0 이면 0 출력 1이면 1출력섞여있으면 계속 4등분씩 쪼개가면서 체크해야한다. 재귀 슬슬 감 오니 백트레킹,DP 들어가자.

전 문제 BJ 1780 종이의 개수와 풀이 방법은 같다 그러므로 설명 생략

문제풀이분할 정복 알고리즘과 재귀를 이용하여 해결하는 문제이다.분할 정복 알고리즘이란 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 해결하는 방법이다.이 문제에 따르면종이(배열) 안의 숫자들이 모두 같다면, 그 종이는 분할하지 않고 넘어간다.종이 내에 다른 숫자가 하나라도 포함된다면, 그 종이를 9분할 한다.9분할한 종이 하나하나마다 숫자가 같은지 확인한다.(다시 1번으로 반복)9*9 크기의 종이를 예로 들면,9*9 크기에 채워진 숫자들, 즉 81칸의 숫자가 모두 같다면 -> n으로만 적혀있는 종이의 개수 ++하나라도 다르다면 3*3 크기의 종이 9개로 분할 (즉 3^n승이니 한변의 길이는 n/3이다)3*3 크기의 종이 하나하나 다시 체크 -> 모두 같다면 -> n으로만 적혀있는 종이의 개수 ++ ..

유명한 재귀 문제이다.1번예제에 첫번쨰 줄을보자 어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다. 재귀 함수는 자기 자신을 호출하는 함수라네 그러고 2 -> 1 -> 0 순으로 종료되며 라고 답변하였지. 를 출력한다. 그림으로 한번 보자____ 가 0일떄,1일떄,2일떄 순서이다.즉 ____의 갯수가 n일떄 "재귀함수는 자기 자신을 호출하는 함수이네" 라는 basecondition을 출력후라고 답변하였지. 를 출력후 함수가 종료된다. 아직은 쉽지만 Z문제같은 부분탐색같은경우도 정확히 식을 세우고 쪼개서 풀 줄 알아야추후에 풀을 DP,백트레킹이 수월하다.