코딩무식자 전공생

문제출처:https://www.acmicpc.net/problem/10992

별찍기의 난이도가 어려워질 때 마다 느끼는건데 행과 열의 변수값만으로도  풀 수 있는데

자꾸 제가 풀 때 마다 새로운 변수를 두고 풀려고한다는 것입니다.

반복문,조건문을 이루는 변수들을 사용하는 아이디어를 떠올리는게 중요한 것 같습니다.

주석 친 코드는 맨 마지막줄(별이 찍히는 행)을 제외하여 연산을하고 맨마지막 행만 따로 연산하는 풀이이고

두번 째 코드는 통째로 푼 방식입니다.

#include<iostream>
using namespace std;
int main()
{
	int i, j, n;
	cin >> n;
	for (int i = 0; i < n - 1; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			cout << " ";
		}
		cout << "*";
		for (int j = 0; j < i * 2 - 1; j++)
			cout << " ";
		if (i != 0)cout << "*";
		cout << endl;
	}
	for (int i = 0; i < n * 2 - 1; i++)
		cout << "*";
}

#include<iostream>
using namespace std;
int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n - i; j++)
		{
			cout << " ";
		}
		if (i == 1 || i == n)//이때는 n갯수만큼*출력
			for (int j = 1; j <= (i - 1) * 2 + 1; j++)
				cout << "*";
		else//1행or n행아닐 때
		{
			cout << "*";
			for (int j = 1; j <= (i - 1) * 2 - 1; j++)
			{
				cout << " ";
			}
			cout << "*";
		}
		cout << endl;
	}
}

문제출처: https://www.acmicpc.net/problem/2935

알고리즘은 다음과 같습니다.

1. 일단 입력값이 연산자를 제외하고 10의거듭제곱꼴 뿐이라 나올 수있는 출력값의 숫자는 0,1,2뿐입니다.

2. 입력값의 자릿수가 100을 넘기므로 int,long long 형으로 풀 수 없고 문자열로 접근합니다.

3. 입력값의 자릿수를 비교하며 연산합니다.

1) a와 b의 자릿수가 같을때

⑴: +연산: 2를 출력하고 a_size-1또는 b_size-1만큼 0을 출력합니다.

⑵ *연산: 1을출력하고 a_size+b_size -2만큼 0을 출력합니다.

2)a와 b의 자릿수가 다를때

⑴ +연산: a_size>b_size일때 : a[a_size-b_size]=1로바꾸고 a출력, 반대로 a_size<b_size일때는 b[b_size-a_size]=1로바꾸고 b출력

⑵ *연산: 1출력 후 a_size+b_size - 2만큼 0 출력

#include<iostream>
#include<string>
using namespace std;
int main()
{
	string a, b;
	char op;
	cin >> a >> op >> b;
	int a_size = a.size();
	int b_size = b.size();

	if (a_size == b_size)///사이즈같을때 
	{
		if (op == '+')
		{
			cout << 2;
			for (int i = 0; i < a_size - 1; i++)
				cout << 0;
		}
		else//'*'
		{
			cout << 1;
			for (int i = 0; i < a_size + b_size - 2; i++)
				cout << 0;
		}
	}
	else//사이즈다를때
	{
		if (op == '*')
		{
			cout << 1;
			for (int i = 0; i < a_size + b_size - 2; i++)
				cout << 0;
		}
		else//'+'
		{
			if (a_size < b_size) {
				b[b_size - a_size] = '1';
				cout << b;
			}
			else
			{
				a[a_size - b_size] = '1';
				cout << a;
			}

		}
	}
}

저번에 공부한 코드실행시간분석 코드를 이용해 피보나치수열을

반복, dp(동적프로그래밍)으로 성능차이를 분석해보겠습니다.

재귀함수로 구현한 피보나치는 O(2^N)이고

dp로 구현한 피보나치는O(N)으로, 재귀로구현한것보다 훨씬!!빠른 효율적인 알고리즘입니다.

반복문으로구현한 피보나치또한 O(N)입니다.

따라서 범위가 작을때는 어느방법을 사용해도상관없으나 범위가 커질수록  효율적인 방법을 써야합니다.

dp와 반복문으로로구한 피보나치수열의 시간차이가 상당함을 알 수 있습니다.

(상당한 차이입니다.)

빅오표기법으로 표기한 4가지 시간복잡도의 빠른순서(왼쪽부터)

O(N) <O(NlogN) <O(N^2) < O(2^N)

#include<iostream>
#include<algorithm>
#include<ctime>
using namespace std;
int fibo_recursive(int x);
int fibo_dp(int x);
int  fibo_repeat(int x);
int  dp[100];
int main()
{
	clock_t start, finish;
	double duration;
	int sum = 0;
	start = clock();
	int x = fibo_recursive(40);
	finish = clock();
	duration = (double)(finish - start) / CLOCKS_PER_SEC;
	cout << "재귀구현피보나치값:" << x << "시간: " << duration << "초\n";

	start = clock();
	int y = fibo_dp(40);
	finish = clock();
	duration = (double)(finish - start) / CLOCKS_PER_SEC;
	cout << "dp구현피보나치값:" << y << "시간: " << duration << "초\n";

	start = clock();
	int z = fibo_repeat(40);
	finish = clock();
	cout << "반복문피보나치값:" << z << "시간: " << duration << "초\n";
}
int fibo_recursive(int x)
{

	if (x == 1)return 1;
	if (x == 2)return 1;
	return fibo_recursive(x - 1) + fibo_recursive(x - 2);
}
int fibo_dp(int x)
{
	if (x == 1)return 1;
	if (x == 2)return 1;
	if (dp[x] != 0)return dp[x];
	return dp[x] = fibo_dp(x - 1) + fibo_dp(x - 2);
}
int  fibo_repeat(int x)
{
	if (x == 1)return 1;
	if (x == 2)return 1;
	int temp, current = 1, last = 0;
	for (int i = 2; i <= x; i++)
	{
		temp = current;
		current += last;
		last = temp;
	}
	return current;
}

프로그램의  코드실행시간을 측정하기위한 방법이다.

주로 시간복잡도의 큰요인으로 작용되는 함수,반복문등의 연산식 전후로 다음과같이 선언하여

실제 코드의 실행시간을 알 수 있다.

clock_t자료형을 사용하기위해 헤더파일 time을 include한다.(여기선c++이기떄문에 ctime으로선언)

CLOCKS_PER_SEC-> 수행시간을 초단위로 계산한다고 생각하면된다.

clock_t 자료형: 실제로는 typedef long clock_t 로 설정되어있어서 clock_t를 long으로써도된다.

duration:함수가 끝날때시간과 시작할때 시간을 빼준값을 실수형으로바꿔서 소수점단위까지의 값을 구한다.

결과값은 컴퓨터의성능에 따라 다르다.(노트북 성능이 쓰레기라 다른 컴퓨터에서 돌렸을때 값보다 많이느리다..)

#include<iostream>
#include<ctime>
using namespace std;

{
	clock_t start, finish;
	double duration;
	int sum = 0;

	start = clock();
	for (int i = 0; i < 100000000; i++)

		sum += i;

	finish = clock();

	//duration=실제 코드수행시간
	duration = (double)(finish - start) / CLOCKS_PER_SEC;
	cout << duration << endl;


}

**여기서구하는건 실제 함수 동작시간이지 시간복잡도o(n)을 계산한게아니다.

시간복잡도: O(N)==O(100000000)==약1초