본문 바로가기

알고리즘&자료구조/재귀7

재귀(recursion) *** 재귀란?하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘 재귀를 이용해 문제를 풀때는 수학적 귀납법을 이용하면 간결하게 풀 수 있다.제일 앞의 도미노를 쓰러트리면 모든 도미도는 쓰러질 것이다.그런데 왜? 모든 도미노가 쓰러지는가를 설명해보자 첫번째 설명 방법은 제일 앞에 있는 1번 도미노가 쓰러지면 2번도미노, 3번도미노... 순차적으로 쓰러진다는 설명방법이고 두번째 설명 방법은 1번 도미노가 쓰러진다. K번 도미노가 쓰러지면 K+1번 도미노도 쓰러진다 결국에는 모든 도미노가 쓰러진다는 귀납적 방식을 이용한다.  절차지향적 사고방식)// N~1까지 차례대로 출력void func1(int val) { if (val == 0) return; cout  func1(10000...) .. 2024. 5. 2.
백준 1992 문제 분석 언제 괄호를 열고 닫아야 하는지? 1. 똑같은 영상으로 이루어지지 않은 경우 4등분을 하기 전에 괄호를 한 번 열어주고 4등분한 재귀함수가 모두 끝난 이후 괄호를 닫아줌 주어진 영상이 모두 똑같은 수로만 되어있으면 괄호로 묶을 필요가 없음 --> 이 말을 이해하지 못해서 똑같은 수로 되어 있는 경우도 괄호로 묶어버림 코드 #include using namespace std; int board[65][65]; bool valSameCk(int n, int x, int y) { for (int i = x; i < x + n; i++) { for (int j = y; j < y + n; j++) { if (board[x][y] != board[i][j]) return false; } } return.. 2024. 3. 1.
백준 2630 #include using namespace std; // 종이의 각 칸 int board[130][130]; // 0[0], 1[1] 채워진 종이 개수 int cnt[2]; bool valSameCk(int n, int x, int y) { for (int i = x; i < x + n; i++) { for (int j = y; j < y + n; j++) { if (board[x][y] != board[i][j]) return false; } } return true; } void func(int n, int x, int y) { // 모두 같은 값으로 이루어진 종이인지 체크 if (valSameCk(n, x, y)) { cnt[board[x][y]] += 1; } else { int half = n.. 2024. 2. 29.
백준 1780 문제분석 종이 크기는 1(3의 0승), 3(3의 1승), 9(3의 2승)... 형태로 주어짐 각각 1*1, 3*3, 9*9 크기로 이루어짐 k=1 일 때 종이를 자를 수 없음 (1을 3으로 나누면 몫이 0) k=3 일때 종이를 한 번 자를 수 있음 (3을 3으로 나누면 몫이 1, 즉 1*1 9개로 나눠짐) k=3의 n승일때 n번 종이를 자를 수 있음 1. 함수식 func(n, x, y) n : 종이 크기 x : 모든 종이가 똑같은 값인지 검사할 행 y : 모든 종이가 똑같은 값인지 검사할 열 func(3, 0, 0)으로 예시를 들어보면 (0,0) 값을 기준으로 삼고 3*3 모든 종이의 칸과 비교 종이의 각 칸이 모두 같은 수로 되어있다면 해당 수의 개수 1 증가 후 재귀함수 종료 종이의 각 칸이 모두 같.. 2024. 2. 27.

티스토리툴바