레벨테스트 답변

피보나치 수열

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

int Fi(int num)
{
	if (num == 1)
		return 1;
	else if (num == 2)
		return 1;
	else
		return Fi(num - 1) + Fi(num - 2);
}
void main()
{
	int num;
	cin >> num; 
	cout << Fi(num) << endl;
}

 

하노이의 탑

#include <iostream>
using namespace std;


//하노이 탑
void hanoi(int n, int from, int by, int to)
{	//n : 원판 개수 : from : 출발지, by : 경유지, to : 목적지
	if (n == 1)
		cout << from << "->" << to << endl;
	else
	{
		hanoi(n - 1, from, to, by);	//기둥1의 n-1개의 원판을 기둥 2로 옮기기
		cout << from << "->" << to << endl;	//기둥 1의 1개의 원판을 기둥3으로 옮기기
		hanoi(n - 1, by, from, to);	//기둥2의 n-1 원반을 기둥 3으로 옮기기
	}
}
void main()
{
	
	int n;
	cin >> n;
	int k = pow(2, n) - 1;
	cout << "최소 이동 횟수 : "<<k << endl;
	hanoi(n, 1, 2, 3);
	

	
}

링크드리스트

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

//링크드리스트
//각 요소인 노드를 연결해서 만드는 리스트


class Node
{
public:
	int value;
	Node* next = nullptr;
	Node* prev = nullptr;
};

class SingleLinkedList
{
private:
	Node* head = nullptr;
	Node* tail = nullptr;
	int size = 0;
public:
	void AddNode(int value);
	void AddNode(int value, int position);
	void RemoveNode(int value);
	int SearchPosition(int value);
	void Show();
	int GetSize();
	bool IsEmpty();


};

void SingleLinkedList::AddNode(int value)
{
	Node* newNode = new Node;
	newNode->value = value;
	size++;
	if (head == nullptr) //리스트가 비어있다면
	{
		head = newNode;
		tail = newNode;

	}
	else
	{
		tail->next = newNode;
		tail = newNode;

	}


}
void SingleLinkedList::AddNode(int value, int position)
{
	Node* newNode = new Node;
	newNode->value = value;
	size++;
	//1번 해당위치까지 접근
	Node* currentNode = head;
	for (int i = 1; i < position - 1; i++)
	{
		currentNode = currentNode->next;
	}
	newNode->next = currentNode->next;
	currentNode->next = newNode;
}
void SingleLinkedList::RemoveNode(int value)    //해당 값 찾아서 지우기
{
	Node* currentNode = head;
	if (currentNode->value == value)
	{
		head = currentNode->next;
		delete currentNode;
	}
	else if (tail->value == value)
	{
		while (currentNode->next != tail)
		{
			currentNode = currentNode->next;
		}
		delete(tail);
		tail = currentNode;
	}
	else
	{
		for (int i = 0; i < SearchPosition(value) - 2; i++)
		{
			currentNode = currentNode->next;
		}
		Node* removeNode = currentNode->next;
		currentNode->next = currentNode->next->next;
		delete removeNode;
	}
}
bool SingleLinkedList::IsEmpty()
{
	return head == nullptr;
}
int SingleLinkedList::GetSize()
{
	return size;
}
void SingleLinkedList::Show()
{
	Node* currentNode = head;
	while (currentNode != nullptr)
	{
		cout << currentNode->value << endl;
		currentNode = currentNode->next;
	}
}
int SingleLinkedList::SearchPosition(int value)
{
	Node* currentNode = head;
	int currentNodeNum = 1;
	while (currentNode->value != value)
	{
		currentNode = currentNode->next;
		currentNodeNum++;
	}
	return currentNodeNum;
}
void main()
{
	SingleLinkedList linkedlist;
	linkedlist.AddNode(10);
	linkedlist.AddNode(20);
	linkedlist.AddNode(40);
	linkedlist.AddNode(50);
	linkedlist.AddNode(100, 3);
	linkedlist.RemoveNode(20);


	

	linkedlist.Show();
}

 스택 - 배열

#include <iostream>
using namespace std;

const int MAX = 1e5;

class Stack {
private:
    int data[MAX];
    int index;
public:
    Stack();
    bool empty();
    void push(int x);
    void pop();
    int top();
    int size();
};

Stack::Stack() {
    index = -1;
}

bool Stack::empty() {
    return index == -1;
}

void Stack::push(int x) {
    index += 1;
    data[index] = x;
}

void Stack::pop() {
    index -= 1;
}

int Stack::top() {
    return data[index];
}

int Stack::size() {
    return index+1;
}

int main() {
    Stack s;
    for (int i=1; i<=10; i++) s.push(i); // Push 1~10
    for (int i=1; i<=4; i++) s.pop(); // Pop 10~7
    for (int i=1; i<=4; i++) s.push(i); // Push 1~4
    cout << "* Size: " << s.size() << '\n';
    while (!s.empty()) {
        cout << "Pop: " << s.top() << '\n';
        s.pop();    // Pop all
    }
    return 0;
}