c++문제풀이

문제

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

입력

첫째 줄에 N이 주어진다. N은 항상 3의 제곱꼴인 수이다. (3, 9, 27, …) (N=3^k, 1 ≤ k < 8)

출력

첫째 줄부터 N번째 줄까지 별을 출력한다.

예제 입력

27

예제 출력

***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
*********         *********
* ** ** *         * ** ** *
*********         *********
***   ***         ***   ***
* *   * *         * *   * *
***   ***         ***   ***
*********         *********
* ** ** *         * ** ** *
*********         *********
***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************

별찍기 문제 패턴

1. printf(“*”); 문장만 사용해서 별을 출력한다.
2. 중첩반복문을 이용하여 i행 j열에 별을 찍는다.

#include<stdio.h>

void star(int n, int x, int y);
char arr[6561][6561];

int main()
{
	for(int i = 0; i < 6561; ++i)
	{
		for(int j = 0; j < 6561; ++j)
		{
		    arr[i][j] = ' ';
		}
	}
	int n; 
	scanf("%d", &n);
	
	star(n, 0, 0);
		
	for(int i = 0; i < n; ++i)
	{
		for(int j = 0; j < n; ++j)
		{
			printf("%c", arr[i][j]);
		}
		if(i == n-1)
		break;
		printf("\n");
	}
	
	return 0;
}

void star(int n, int x, int y)
{
	if(n == 3)
	{
		arr[x][y] = '*';
		arr[x][y+1] = '*';
		arr[x][y+2] = '*';
		arr[x+1][y] = '*';
		arr[x+1][y+1] = ' ';
		arr[x+1][y+2] = '*';
		arr[x+2][y] = '*';
		arr[x+2][y+1] = '*';
		arr[x+2][y+2] = '*';
		return;
	}
	n = n/3;
	
	star(n, x , y);
	star(n, x , y+ n);
	star(n, x , y+ n + n);
	
	star(n, x+n, y);
//	star(n, x+n, y+n);
	star(n, x+n, y+ n+n);
	
	star(n, x+n+n, y);
	star(n, x+n+n, y+ n);
	star(n, x+n+n, y+ n+n);
	
}

c++문제풀이

문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

예제 입력

3

예제 출력

7
1 3
1 2
3 2
1 3
2 1
2 3
1 3

재귀함수를 사용하는 하노이의 타워 원리

#include <stdio.h>
int move_min = 0;
int hanoi_min(int from, int by, int to, int circle);
void hanoi_print(int from, int by, int to, int circle);

int main()
{
	int n;
	scanf("%d", &n);
	
	move_min = hanoi_min(1, 2, 3, n);
	printf("%d\n", move_min);
	hanoi_print(1, 2, 3,n);
	return 0;
}

int hanoi_min(int from, int by, int to, int circle)
{
	if(circle == 1)
	{        
	    ++move_min;
		return move_min;
	}
	hanoi_min(from, to, by, circle -1);	
	hanoi_min(from, by, to, 1);	
	hanoi_min(by, from, to, circle -1);
	
}

void hanoi_print(int from, int by, int to, int circle)
{
	if(circle == 1)
	{
		printf("%d %d\n",from, to);
	}
	else
	{
		hanoi_print(from, to, by, circle -1);
		printf("%d %d\n",from, to);	
	    hanoi_print(by, from, to, circle -1);	
	}
}

1. 재귀( 순환 )

Recursion 이란 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법

2. 재귀 함수의 원리

주어진 문제를 더 작은 동일한 문제들로 분해하여 해결하는 방법 분할 정복(divide and conqure)

3. 반복 vs. 재귀 (순환)

팩토리얼 코드를 통해서 반복알고리즘과 순환 알고리즘 성능 비교

• 반복 알고리즘

int factorial_iter(int n)
{
	int k, v = 1;
	for(k = n; k >= 0; k--)
	{
		v *= k;
	}
	return v;
}

for 반복문을 사용하여 n번 반복하므로 시간 복잡도는 O(n) 이다.

• 순환 알고리즘

int factorial(int n)
{
	if(n == 0 || n ==1)
	    return 1;
	return n * factorial(n-1);
}

한번 순환 호출 할 때마다 1번의 곱셈이 수행되고 순환호출이 n번 일어나므로 역시 시간복잡도는 O(n)이다.

반복 알고리즘과 순환알고리즘의 시간 복잡도는 같지만 순환 호출의 경우 여분의 기억공간이 더 필요하다. (함수를 호출하기 위해서 함수의 파라미터들을 스택에 저장)
따라서 실행 시간도 더 걸린다. 결론적으로 순환 알고리즘은 수행 시간과 기억공간의 사용에 있어서는 비효율적인 경우가 많다.
순환 호출 시에는 호출이 일어날때마다 호출하는 함수의 상태가 기억되어야하므로 여분의 기억장소가 필요하게 된다.

4. Recursion 알고리즘이 반복 알고리즘보다 실행시간이 빠른 경우

숫자 x의 n-거듭제곱 값을 구하는 함수

• 반복 알고리즘

double power_iter(double x, int n)
{
    int i;
	double r = 1.0;
	for(i = 0; i <n; i++)
	    r *= x;
    return r;
}

for 반복문을 사용하여 n번 반복하므로 시간 복잡도는 O(n) 이다.

• 순환 알고리즘

double power(double x, int n)
{
    if(n == 0) return 1;
	else if((n%2) == 0) 
	    return power(x*x, n/2);
    else 
	    return x*power(x*x, (n-1)/2);
}

Recursion 알고리즘 사용하면 한번의 순환이호출될 때마다 약 1번의 곱셈과 1번의 나눗셈이 일어나므로 시간 복잡도는 O(logN) 이다.

• x의 거듭제곱 - 순환 알고리즘 시간복잡도
  T(n)
  = T(n/2) + c1 if n is even
  = T(n-1) + c2 if n is odd
  = T(0) = 1 if n is 0

  T(n)
  = T(3n-2/2) + c1 + c2
  = T(n/2) + k
  = T(n/4) + 2k
  = T(n/8) + 3k
  = T(n/2^k) + ck

  T(1)
  = T(0) + c2
  = 1 + k

  1/2^k + ck = 1+ k
  1/2^k = c
  2^k = n
  k = log2n

O(log n)

• 결론적으로, Recursion 알고리즘은 문제의 정의가 순환적으로 되어있는 경우에 유리한방법
  즉, 문제의 크기가 순환이 진행될 수록 작아지는 경우에 순환 알고리즘을 쓰는 것이 자연스럽다.