×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 2,102,003명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
반응형

1. 연결리스트


문제

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


입력

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

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


출력

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#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 >>
Crocus





2. 원형 큐


문제

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


입력

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

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


출력:

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#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 >>
Crocus



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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#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 >>
Crocus





3. 트리


문제

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


입력

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

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


출력:

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
#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 * + 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 >>
Crocus


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

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





4. 스택


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


입력

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

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


출력:

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#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 >>
Crocus






5. 이중연결리스트


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


입력

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

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


출력:

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




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#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 >>
Crocus



반응형

'Tutoring > Data Structure' 카테고리의 다른 글

연결리스트 및 응용 예시 문제  (0) 2018.05.24
튜터링 템플릿, 체인  (0) 2018.05.03
튜터링 단일 연결 리스트  (0) 2018.04.18
튜터링 atoi, 후위 표기식  (0) 2018.04.11
튜터링 연습문제 1주차  (0) 2018.03.21
hash  (0) 2018.03.04