EVI$ION 겨울방학 코테스터디 2주차 과제

1158, 요세푸스 문제, C++

이 문제를 그대로 이해하면 될 것 같다.

그니까, 문제의 예를 보면 입력을 7 3 로 받는다면 이 7의 의미는 앉아있는 사람의 수라고 생각할 수 있고,

1, 2, 3, 4, 5, 7을 나타낼 수 있다. 3은 제거되는 사람의 번호를 의미를 하게 되는데

나는 반복문을 구현할 때 1~3까지 큐에 삽입 후 그 인덱스 번호가 3인 경우, remove 동적배열에 삽입하고,

인덱스 번호가 3이 아닌 경우 큐 맨 뒤에 삽입

 

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

vector<int> calcJosephus(queue<int> Q,int N,int K)
{
	vector<int> remove;
	int q_front, j=0;
	
	while(N!=remove.size())
	{
		for(int i=1;i<=K;i++)
		{
			if(i==K)
			{
				remove.insert(remove.begin()+j, Q.front());
				Q.pop();
				j++;
			}
			else{
				q_front = Q.front();
				Q.pop();
				Q.push(q_front);
			}
			
		}
	}
	
	return remove;
}

int main()
{
	int n, k;
	
	queue<int> q;
	cin >> n >> k;
	
	int arr_Josephus[n];
	if(k<=n)
	{
		for(int i=1;i<=n;i++)
		{
			q.push(i); //큐 삽입
		}
		vector<int> result = calcJosephus(q,n,k);
		cout <<"<";
		for(int i=0;i<result.size();i++)
		{
			if(i==n-1){
				cout <<result[i];
			}
			else{
				cout <<result[i]<<", ";
			}
		}
		cout<<">"<<'\n';
	}
	return 0;
}

 

💡 관련 알고리즘 - 큐

선형 자료구조로써, 데이터를 저장하고 검색하는데 사용되는 알고리즘임.

큐는 데이터를 저장할 때 선입선출(FIFO) 원칙을 따른다. 

[구성요소]

Elements : 큐에 저장되는 실제 데이터 항목

Front & rear : 큐의 시작과 끝 지점을 나타내는 포인터들

[종류]

1. 선형큐

 

2. 원형큐

 

3. 우선순위 큐

각 데이터 요소에 우선순위를 할당하고 해당 우선순위에 따라 데이터를 처리하는 큐

 

3. 덱

양쪽에서 삽입, 삭제가 가능한 구조

---

2747, 피보나치 수, C++

문제는 다음과 같고

나는 이렇게 이해하였다.

처음에는 memoization을 위해 저장 목적으로 vector 라이브러리를 사용했는데 메모리 초과가 나왔다. 

다음은 vector 라이브러리로 구현한 코드이다.

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

int solution(int n)
{
	vector<int> v(46);
	for (int i = 0; i < n+1; i++)
	{
		if (i == 0)
		{
			v[i] = 0;
			//cout << v[i];
		}
		else if (i == 1)
		{
			v[i] = 1;
			//cout << v[i];
		}
		else if (i > 45)
		{
			return 0;
		}
		else
		{
			v[i] = v[i-1] + v[i-2];
			//cout << v[i];
		}
	}

	cout << v[n];
}
int main()
{
	int n;
	//입력
	cin >> n;
	solution(n);

	return 0;

}

vector<int> v(46)은 최대 46개의 정수 메모리 공간을 할당하게 되는데

int는 64비트 기준으로 4바이트 이므로 => 46 x 4byte = 184byte이다.

또한, 함수 호출이 많거나 스택 메모리가 과도하게 사용되면 메모리 초과 발생가능한 것 같다.

184는 128보다 훨씬 큰 숫자였다.

그래서 또 다른 알고리즘을 생각한것이 재귀호출이다. 

다음은 재귀호출 알고리즘 코드이다.

int fibo(int n)
{
	if (n == 0 || n == 1)
		return n;
	else if (n > 45)
		return 0;
	else
		return fibo(n - 1) + fibo(n - 2);
}
int main()
{
	int n;
	//입력
	cin >> n;
	//출력
	cout<<fibo(n);
	return 0;

}

하지만, 이것도 시간초과가 나왔다. 왜냐하면 재귀호출로 인해 중복계산이 이루어지기 때문이다. 

n = 5일 때, 재귀 호출의 구조는 다음과 같다.

fibo(5)
├── fibo(4)
│   ├── fibo(3)
│   │   ├── fibo(2)
│   │   │   ├── fibo(1)
│   │   │   └── fibo(0)
│   │   └── fibo(1)
│   └── fibo(2)
│       ├── fibo(1)
│       └── fibo(0)
└── fibo(3)
    ├── fibo(2)
    │   ├── fibo(1)
    │   └── fibo(0)
    └── fibo(1)

 

fibo(2)는 총 3번 호출, fibo(1)은 총 5번 호출되는 시간이 많이 소요되는 그런 구조였다.

시간복잡도는 빅오 2^n이다. n이 커지면 호출 횟수가 급격히 증가해서 그렇다. 

입력이 n = 45일 경우, 재귀호출 횟수는 약 22억번......(?) 충격🤔😯😯😢 내가 잘못해써.... 그래서 1초의 시간제한 내에 처리불가!!!!

그래서 첫번째 때 생각한 메모이제이션을 vector말고 배열로 구현하였다.

#include <iostream>

using namespace std;

int solution(int n)
{
	int v[46] = { 0,1, };

	//v[0] = 0;
	//v[1] = 1;
	//cout << v[i];

	for (int i = 2; i <= n; i++)
	{

		if (i > 45)
		{
			return 0;
		}
		else
		{
			v[i] = v[i - 1] + v[i - 2];
			//cout << v[i];
		}
	}

	return v[n];
}
int main()
{
	int n;
	//입력
	cin >> n;
	cout<< solution(n);

	return 0;

}

 

💡관련 알고리즘 - Dynamic Algorithm

• 메모하기
  변수 값에 따른 결과를 저장할 배열 등을 미리 만들고 그 결과를 나올 떄마다 배열 내에 저장하고 그 값을 재사용하는 방식.
• 변수 간 관계식 만들기
  피보나치 수열 : f(n) = f(n-1) + f(n-2)

   [문제 해결 방식]

• Bottom-up : 반복문 사용
  작은 부분 문제부터 차례대로 해결하여 전체 문제를 해결
  최적 부분 구조 보장
• Top- Down : 재귀 사용 
  큰 문제를 작은 부분 문제로 나누어 해결하는 방식
  문제를 작은 부분 문제들로 쪼개고, 중복계산을 피하기 위해 이전에 계산한 값을 저장하는 Memoization을 활용 

---

25206, 너의 평점은, C++

전공평점 계산 - 전공과목별(= 학점 x 과목평점)총합을 학점의 총합으로 나눈 값.

제한:

• 1 ≤ 과목명의 길이 ≤ 50
• 과목명은 알파벳 대소문자 또는 숫자로만 이루어져 있으며, 띄어쓰기 없이 주어진다. 입력으로 주어지는 모든 과목명은 서로 다르다.
• 학점은 1.0,2.0,3.0,4.0중 하나이다.
• 등급은 A+,A0,B+,B0,C+,C0,D+,D0,F,P중 하나이다.
• 적어도 한 과목은 등급이 P가 아님이 보장된다.

0	1	2
ObjectOrientedProgramming1	3.0	A+ (4.5)
IntroductiontoComputerEngineering	3.0	A+ (4.5)
ObjectOrientedProgramming2	3.0	A
CreativeComputerEngineeringDesign	3.0	A+
AssemblyLanguage	3.0	A+
InternetProgramming	3.0	B
ApplicationProgramminginJava	3.0	A
SystemProgramming	3.0	B
OperatingSystem	3.0	B
WirelessCommunicationsandNetworking	3.0	C+
LogicCircuits	3.0	B
DataStructure	4.0	A+
MicroprocessorApplication	3.0	B+
EmbeddedSoftware	3.0	C
ComputerSecurity	3.0	D+
Database	3.0	C+
Algorithm	3.0	B
CapstoneDesigninCSE	3.0	B+
CompilerDesign	3.0	D
ProblemSolving	4.0	P

전공평점 = (3.0 x 4.5 + 3.0 x 4.5 + ... + 3.0 x 1.0) / (3.0 + 3.0 + ... + 3.0)

위 표와 같이 20행 3열로 matrix를 구성하면 될 것 같다. -> 근데 이거 없어도 될듯?

그냥 그자리에서 입력받는대로 함수호출해서 연산해도 될듯!

#include <iostream>
#include <string>

using namespace std;
float upSum = 0.0, downSum = 0.0;  // upSum : 분자 계산, downSum : 분모 계산
float solution(float myPoint, const string subPoint)
{	
	if (subPoint == "A+")
	{
		upSum += (myPoint * 4.5);
		downSum += myPoint;
	}
	else if (subPoint == "A0")
	{
		upSum += (myPoint * 4.0);
		downSum += myPoint;
	}
	else if (subPoint == "B+")
	{
		upSum += (myPoint * 3.5);
		downSum += myPoint;
	}	
	else if (subPoint == "B0")
	{
		upSum += (myPoint * 3.0);
		downSum += myPoint;
	}
	else if (subPoint == "C+")
	{
		upSum += (myPoint * 2.5);
		downSum += myPoint;
	}
	else if (subPoint == "C0")
	{
		upSum += (myPoint * 2.0);
		downSum += myPoint;
	}
	else if (subPoint == "D+")
	{
		upSum += (myPoint * 1.5);
		downSum += myPoint;
	}
	else if (subPoint == "D0")
	{
		upSum += (myPoint * 1.0);
		downSum += myPoint;
	}
	else if (subPoint == "F")
	{
		upSum += (myPoint * 0.0);
		downSum += myPoint;
	}
	else
		upSum += 0;
	float result = upSum / downSum;
	return result;
}

int main()
{
	string subject;	float myPoint; int n = 20; string subPoint; float result;
	
	while (n--)
	{
		//입력
		cin >> subject >> myPoint >> subPoint;
		//연산
		if (1 <= subject.size() && subject.size() <= 50)  //문자열 길이 제한
		{
			result = solution(myPoint, subPoint);
		}
			
		else // 제한 조건
		{
			n++;
			continue;
		}
			
	}
	cout << fixed;
	cout.precision(6); // 소숫점 아래 6자리로 고정시키기 
	cout << result;
	return 0;
}

 

 

 

💡관련 라이브러리 - 문자열 

 string 클래스는 #include <string>

문자의 끝에 null문자가 포함되지 않는다.

배열처럼 한 문자씩 다룰 수 있다 -> 인덱스 or .at(index)

string 클래스끼리는 문자열을 합치는 것이 "+" 연산자 하나만으로 가능하다.

문자열을 사전순으로 정렬할 때도 string 변수를 사용하면 편리하다.

숫자를 문자열로, 문자열을 숫자로 바꾸기 가능

//숫자 -> 문자열
str1 = to_string(a); // 7이 string "7"로 변환되어 str1에 저장된다.

//문자열 -> 숫자
int after_a = stoi(str_a); // "7"을 int형 7로 바꿔줌
double after_b = stod(str_b); // "7.02"를 double형 7.02로 바꿔줌
float after_c = stof(str_c); // "3.14"를 float형 3.14로 바꿔줌
long int after_d = stof(str_d); // "2300000000"을 long int형으로 바꿔줌

 

---

참고:

https://velog.io/@boyeon_jeong/%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming

https://velog.io/@mic050r/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Tree-Graph%EC%9D%B4%EB%9E%80

https://chanhuiseok.github.io/posts/algo-37/