[BOJ_step_10] 재귀 01 ~ 04

재귀

재귀함수를 다루어 보자

팩토리얼(10872)

문제풀이

재귀함수를 이용하여 팩토리얼을 구현하는 문제다. 항상 조심해야할 것은 조건! n=0부터 이다.

int process(int n) {
	if (n == 1 || n == 0)return 1;
	return n * process(n - 1);
}
void solution_10872() {
	int n;
	scanf("%d", &n);
	printf("%d\n", process(n));
}

피보나치 수 5(10870)

)

문제풀이

$f(n) = f(n-1) + f(n-2)$
이 점화식을 memoization을 이용하여 풀이

int dp[21];
int process(int n) {
	if (n == 0)return dp[0];
	if (n == 1)return dp[1] = 1;
	if (dp[n])return dp[n];
	else {
		dp[n] = process(n - 1) + process(n - 2);
		return dp[n];
	}
}
void solution_10870() {
	int n;
	scanf("%d", &n);
	printf("%d\n", process(n));
}

별 찍기 - 10(2447)

문제풀이

별 찍기 - 10

백준 단계별로 풀기 문제들이 수정되기 전에 한 번 풀었던 문제이다. 문제에 대한 해석은 위 링크에 있다.
이번에는 좀 다르게 풀어보았는데 각 행과 열을 0 ~ n-1까지 모두 탐색한다. 행과 열의 좌표를 3으로 나눈 나머지가 1일 때에는 공백을 출력하고 그 외에는 n을 최소단위 즉 n=1일때까지 재귀를 타고 들어가 별을 출력한다.

int N;
void process(int n, int x, int y) {
	if ((x / n) % 3 == 1 && (y / n) % 3==1)printf(" ");
	else {
		if (n / 3 == 0)printf("*");
		else process(n / 3, x, y);
	}
}
void solution_2447() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			process(N,i, j);
		}
		printf("\n");
	}
}

하노이탑 이동 순서(11729)

처음에 풀었을 때는 정말 이해하려고 유튜브 찾아보고 구글링하고 난리도 아니었던 것 같다.
아직 포스팅은 하진 않았지만 얼마전에 프로그래머스 문제에서도 한 번 풀고 3번째가 되니 재귀함수를 적용하는 면이 좀 더 이해가 잘 됐다.

문제풀이

process의 매개변수 이름 그대로 n개의 탑을 어디서 어디로 옮길 것이며 과정에 포함되지 않는 기둥은 어떤 기둥인지를 계속해서 체크해보면 한 번 처리하기 위한 과정이 머리속에 그려진다.
process의 코드를 그대로 해석해보면 n개의 탑 중에서 n-1개의 탑을 from에서 to로 옮기고 다음 과정으로 넘어가면 n=1이 될때까지 재귀함수가 호출이 되어 출력하고 재귀함수를 탈출하면서 나머지 과정들이 모두 출력이 될 것이다.
그리고 process(n-1, ex, to, from)에 의하여 마지막 과정이 출력될 것이다.
그리고 이동횟수에 대한 계산은 $2^{n-1}-1$ 임을 알고있어서 따로 계산하지 않고 출력했다.

int N;
void process(int n,int from, int to, int ex) {
	if (n == 1) {
		printf("%d %d\n", from, to);
		return;
	}

	process(n - 1, from, ex, to);
	printf("%d %d\n", from, to);
	process(n - 1, ex, to, from);

}
void solution_11729() {
	scanf("%d", &N);
	printf("%d\n", (2 << N-1) - 1);
	process(N, 1, 3, 2);
}