연결리스트 및 응용 예시 문제

1. 연결리스트

문제

n개의 값을 받고 단일 연결리스트를 구성해보자.

입력

첫 줄에 테스트 케이스 T가 주어진다. 

테스트 케이스 각 첫 줄에 정수 n이 주어지고, 두 번째 줄부터 정수 n개의 입력 데이터가 공백을 기준으로 주어진다. 

출력

각 테스트 케이스의 정답을 첫 줄에 case t를 출력하고 다음 줄에 입력한 정수 n개의 데이터를 거꾸로 출력한다.

#include <iostream>
#include <cstdio>
 
using namespace std;
 
class node {
private:
   friend class list;
   int data;
   node *next;
};
class list {
private:
   node *first;
   node *last;
 
public:
   list() {
      first = last = NULL;
   }
   ~list() {} // 소멸자 구현은 따로 안했습니다.
   void insert(int val) {
      // 처음 리스트에 삽입될 때
      if (first == NULL) {
         node *newNode = new node;
         newNode->data = val;
 
         first = last = newNode;
         newNode->next = NULL;
      }
      else {
         node *newNode = new node;
         newNode->data = val;
 
         newNode->next = first;
         first = newNode;
      }
   }
 
   void print() {
      node *pos = first;
      while (pos != NULL)
      {
         cout << pos->data << " ";
         pos = pos->next;
      }
   }
 
};
int main()
{
   int tCase;
   cin >> tCase;
 
   for (int tc = 1; tc <= tCase; tc++) {
      list LIST;
      int n;
      cin >> n;
 
      for (int i = 0; i < n; i++)
      {
         int val;
         cin >> val;
         LIST.insert(val);
      }
 
      cout << "case " << tc << endl;
      LIST.print();
      cout << endl;
   }
   return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

2. 원형 큐

문제

n개의 값을 받아 원형 큐를 구성해보자.

입력

첫 줄에 테스트 케이스 T가 주어진다. 데이터 입력 세트

테스트 케이스 각 첫 줄에 정수 n이 주어지고, 두 번째 줄부터 정수 n개의 입력 데이터가 공백을 기준으로 주어진다. 

출력:

각 테스트 케이스의 정답을 첫 줄에 case t를 출력하고 다음 줄에 입력한 정수 n개의 데이터를 순서대로 출력한다.

#include <iostream>
#include <cstdio>
 
using namespace std;
 
class node {
private:
   friend class circularQueue;
   int data;
   node *next;
};
class circularQueue {
private:
   node *first;
   node *last;
   
public:
   circularQueue() {
      first = last = NULL;
   }
            ~circularQueue() {} // 소멸자 구현은 따로 안했습니다.
   void insert(int val) {
      // 처음 리스트에 삽입될 때
      if (first == NULL) {
         node *newNode = new node;
         newNode->data = val;
 
         first = last = newNode;
         newNode->next = first;
      }
      else {
         node *newNode = new node;
         newNode->data = val;
 
         last->next = newNode;
         last = newNode;
         newNode->next = first;
      }
   }
 
   void print() {
      node *pos = first;
      bool start = true;
      while (start || pos != first)
      {
         start = false;
         cout << pos->data << " ";
         pos = pos->next;
      }
   }
 
};
int main()
{
   int tCase;
   cin >> tCase;
 
   for (int tc = 1; tc <= tCase; tc++) {
      circularQueue CQ;
      int n;
      cin >> n;
 
      for (int i = 0; i < n; i++)
      {
         int val;
         cin >> val;
         CQ.insert(val);
      }
 
      cout << "case " << tc << endl;
      CQ.print();
      cout << endl;
   }
   return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

배열을 이용한 원형 큐는 아래와 같다.

#include <iostream>
#include <cstdio>
 
using namespace std;
 
int main() {
 
   int n;
   cout << "크기는 원하는 크기 + 2로 잡으세요." << endl;
   cout << "원형 큐 크기 입력 : "; cin >> n;
 
   int *queue = new int[n];
   int first = 0, last = 1;
   int sz = 0;
 
   while (1) {
      cout << "1. push\n2. pop\n3. front\n4. size\n5. empty" << endl;
 
      int num;
      cin >> num;
 
      if (num == 1)
      {
         int val;
         cout << "값 :: "; cin >> val;
         if ((last + 1) % n != first)
         {
            queue[last] = val;
            last = (last + 1) % n;
            sz++;
         }
         else
            cout << "큐가 가득 찼습니다." << endl;
      }
 
      else if (num == 2)
      {
         if ((first + 1) % n == last)
            cout << "큐가 비었습니다." << endl;
         else
         {
            first = (first + 1) % n;
            queue[first] = 0; // pop
            sz--;
         }
      }
 
      else if (num == 3)
      {
         if ((first + 1) % n == last)
            cout << "큐가 비었습니다." << endl;
         else
            cout << "first :: " << first << " last :: " << last << " top :: " << queue[(first + 1) % n] << endl; // pop
      }
 
      else if (num == 4)
         cout << "크기 :: " << sz << endl;
 
      else if (num == 5)
         cout << "비어있으면 0 안비었으면 0이외 값 :: " << sz << endl;
 
   }
 
   return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

3. 트리

문제

n개의 데이터 값을 받아 트리를 구성하고 전위순회로 출력해보자.

입력

첫 줄에 테스트 케이스 T가 주어진다. 

테스트 케이스 각 첫 줄에 정수 n이 주어지고, 두 번째 줄부터 정수 n개의 입력 데이터가 공백을 기준으로 주어진다. 

출력:

각 테스트 케이스의 정답을 첫 줄에 case t를 출력하고 다음 줄에 입력한 정수 n개의 데이터를 순서대로 출력한다.

 
#include <iostream>
#include <cstdio>
 
using namespace std;
 
void prevTravel(int *tree, int node) {
   if (tree[node] == 0)
      return;
 
   cout << tree[node] << " ";
   prevTravel(tree, node * 2);
   prevTravel(tree, node * 2 + 1);
}
int main()
{
   int tCase;
   cin >> tCase;
 
   for (int tc = 1; tc <= tCase; tc++) {
      int node = 1;
      int arr[10002] = { 0, };
      int tree[10002] = { 0, };
 
      int n;
      cin >> n;
 
      for (int i = 0; i < n; i++)
         cin >> arr[i];
 
      for (int i = 0; i < n; i++){
         tree[node] = arr[i];
         node++;
      }
      cout << "case " << tc << endl;
      prevTravel(tree, 1);
      cout << endl;
   }
   return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

포인터를 이용한 트리는 아래 링크를 참고해보자.

http://www.crocus.co.kr/1183?category=278488

4. 스택

문제1. n개의 데이터 값을 받아 스택을 구성해보자.

입력

첫 줄에 테스트 케이스 T가 주어진다. 데이터 입력 세트

테스트 케이스 각 첫 줄에 정수 n이 주어지고, 두 번째 줄부터 정수 n개의 입력 데이터가 공백을 기준으로 주어진다. 

출력:

각 테스트 케이스의 정답을 첫 줄에 case t를 출력하고 다음 줄에 입력한 정수 n개의 데이터를 거꾸로 출력한다.

#include <iostream>
#include <cstdio>
 
using namespace std;
 
class node {
private:
   friend class list;
   int data;
   node *next;
};
class list {
private:
   node *first;
   node *last;
 
public:
   list() {
      first = last = NULL;
   }
   ~list() {} // 소멸자 구현은 따로 안했습니다.
   void insert(int val) {
      // 처음 리스트에 삽입될 때
      if (first == NULL) {
         node *newNode = new node;
         newNode->data = val;
 
         first = last = newNode;
         newNode->next = NULL;
      }
      else {
         node *newNode = new node;
         newNode->data = val;
 
         newNode->next = first;
         first = newNode;
      }
   }
 
   void print() {
      node *pos = first;
      while (pos != NULL)
      {
         cout << pos->data << " ";
         pos = pos->next;
      }
   }
 
};
int main()
{
   int tCase;
   cin >> tCase;
 
   for (int tc = 1; tc <= tCase; tc++) {
      list LIST;
      int n;
      cin >> n;
 
      for (int i = 0; i < n; i++)
      {
         int val;
         cin >> val;
         LIST.insert(val);
      }
 
      cout << "case " << tc << endl;
      LIST.print();
      cout << endl;
   }
   return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

5. 이중연결리스트

문제1. n개의 데이터 값을 받아 이중연결리스트를 구성해보자.

입력

첫 줄에 테스트 케이스 T가 주어진다. 데이터 입력 세트

테스트 케이스 각 첫 줄에 정수 n이 주어지고, 두 번째 줄부터 정수 n개의 입력 데이터가 공백을 기준으로 주어진다. 

출력:

각 테스트 케이스의 정답을 첫 줄에 case t를 출력하고 다음 줄에 입력한 정수 n개의 데이터를 거꾸로 출력한다.

#include <iostream>
#include <cstdio>
 
using namespace std;
 
class node {
private:
   friend class list;
   int data;
   node *next;
   node *prev;
};
class list {
private:
   node *first;
   node *last;
 
public:
   list() {
      first = last = NULL;
   }
   ~list() {} // 소멸자 구현은 따로 안했습니다.
   void insert(int val) {
      // 처음 리스트에 삽입될 때
      if (first == NULL) {
         node *newNode = new node;
         newNode->data = val;
 
         first = last = newNode;
         newNode->next = NULL;
         newNode->prev = NULL;
      }
      else {
         node *newNode = new node;
         newNode->data = val;
 
         newNode->prev = last;
         last->next = newNode;
         last = newNode;
      }
   }
 
   void print() {
      node *pos = last;
      while (pos != NULL)
      {
         cout << pos->data << " ";
         pos = pos->prev;
      }
   }
 
};
int main()
{
   int tCase;
   cin >> tCase;
 
   for (int tc = 1; tc <= tCase; tc++) {
      list LIST;
      int n;
      cin >> n;
 
      for (int i = 0; i < n; i++)
      {
         int val;
         cin >> val;
         LIST.insert(val);
      }
 
      cout << "case " << tc << endl;
      LIST.print();
      cout << endl;
   }
   return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>