ITwork

www.cplusplus.com/reference/deque/deque/

dequeue에 대해서  알아 보겠습니다.

보통 덱(deck)이라고 불리기도 합니다. double-ended queue이어서 양쪽에서 push/pop을 할 수 있습니다.

아래 파일에 api들이 정의되어 있어서 사용하려면 꼭 추가해 줘야합니다.

#include <deque>

push_front : insert element at the beginnig

push_back : Add element at the end 

pop_front :  delete first element

pop_back : delete last element

push_front(1);

push_front(2);

push_front(3);

push_front(4);

push_front(5);

pop_front()

pop_front()

pop_front()

pop_front()

pop_front()

result:

5 4 3 2 1

www.acmicpc.net/problem/10866

문제

정수를 저장하는 덱(Deque)를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여덟 가지이다.

• push_front X: 정수 X를 덱의 앞에 넣는다.
• push_back X: 정수 X를 덱의 뒤에 넣는다.
• pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 덱에 들어있는 정수의 개수를 출력한다.
• empty: 덱이 비어있으면 1을, 아니면 0을 출력한다.
• front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

dequeue를 기본 api 확인하는 문제이다. 

/*baekjoon 10866 dequeue*/
#include <iostream>
#include <deque>
#include <cstring>

using namespace std;
#define MAX_N 100

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);


    int n,i,dt;
    char str[20];
    cin >> n;

    deque<int> dq;


    for(i =0; i < n; i++ ){

        cin >> str;

        if( !strcmp(str, "push_front") ){
            cin >> dt;
            dq.push_front(dt);
        }else if( !strcmp(str, "push_back") ){
            cin >> dt;
            dq.push_back(dt);
        }else if( !strcmp(str, "pop_front") ){
            if(!dq.empty() ){
                cout << dq.front() << '\n';
                dq.pop_front();
            }else{
                cout << "-1" << '\n';
            }
        }else if( !strcmp(str, "pop_back") ){
            if(!dq.empty() ){
                cout << dq.back() << '\n';
                dq.pop_back();
            }else{
                cout << "-1" << '\n';
            }
        }else if( !strcmp(str, "size") ){
            cout << dq.size() << '\n';
        }else if( !strcmp(str, "empty") ){
            cout << dq.empty() << '\n';
        }else if( !strcmp(str, "front") ){
            if(!dq.empty() ){
                cout << dq.front() << '\n';
            } else {
                cout << "-1" << '\n';
            }
        }else if( !strcmp(str, "back") ){
            if(!dq.empty() ){
                cout << dq.back() << '\n';
            } else {
                cout << "-1" << '\n';
            }
        }
    }

    return 0;
}

www.acmicpc.net/problem/1021

문제

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

[풀이]

loop( dt 값 만큼){

    if( dt == front){

       pop

    }else{

        |dt - front| 비교 |dt - back| 작은 쪽 선택 

       dt와 같아 질때까지 이동  

    }

}

예제1

10 3

1 2 3

예제2

10 3

2 9 5

처음 queue값 

1 2 3 4 5 6 7 8 9 10

dt=2 일 경우 

2 3 4 5 6 7 8 9 10 1 (count =1)

dt-front =1

dt-back = 8

pop_front로 거리 측정 후 원복 하고

if (distance > q.size()/2)  pop_back

if (distance <= q.size()/2)  pop_front

9  일 경우 

3 4 5 6 7 8 9 10 1 (origin)

1 3 4 5 6 7 8 9 10 (count = 2)

10 1 3 4 5 6 7 8 9  (count = 3)

9 10 1 3 4 5 6 7 8   (count = 4) pop(dt == q.front)

5  일 경우 

10 1 3 4 5 6 7 8   (origin) 

8 10 1 3 4 5 6 7    (count = 5) 

7 8 10 1 3 4 5 6    (count = 6) 

6 7 8 10 1 3 4 5      (count = 7) 

5 6 7 8 10 1 3 4      (count = 8) 

  1 /*baekjoon 1021 queue*/                                                                     
  2 #include <iostream>
  3 #include <deque>
  4 
  5 using namespace std;
  6 deque<int> q;
  7 #define MAX 100 
  8 
  9 int main()
 10 {
 11     ios_base::sync_with_stdio(0);
 12     cin.tie(0);
 13     cout.tie(0);
 14 
 15 
 16     int i=0,j=0;
 17     int N; // N명 
 18     int K; //K번째 제거 
 19     int dt[MAX];
 20     int count = 0; //최종 거리 
 21     int dist = 0; //distance 
 22     int temp =0; // temporary distance
 23     cin >> N;
 24     cin >> K;
 25 
 26     for(i =1; i <= N; i++ ){
 27         q.push_back(i);
 28     }
 29 
 30     for(i =0; i < K; i++ ){
 31         cin >> dt[i];
 32     }
 33 
 34     for ( i=0; i < K; i++ ){
 35 
 36         dist = 0;
 37         if(dt[i] == q.front() ){
 38             if(!q.empty()){  q.pop_front(); }
 39         }else{
 40             //pop front로 거리 측정 
 41             while( dt[i] != q.front() ) {
 42                 q.push_back(q.front());
 43                 q.pop_front();
 44                 dist++;
 45             }
 46             temp = dist;
 47             // 원복  
 48             while( dist !=0 ) {
 49                 q.push_front(q.back());
 50                 q.pop_back();
 51                 dist--;
 52             }
 53 
 54             if ( temp > q.size()/2 )  {
 55                 while( dt[i] != q.back() ) {
 56                     q.push_front(q.back());
 57                     q.pop_back();
 58                     count++;
 59                 }
 60                 q.pop_back();
 61                 count++;
 62             }else if (temp <= q.size()/2){
 63                 while( dt[i] != q.front() ) {
 64                     q.push_back(q.front());
 65                     q.pop_front();
 66                     count++;
 67                 }
 68                 q.pop_front();
 69 
 70             }
 71 
 72         }
 73     }
 74 
 75     cout << count << endl;
 76 
 77     return 0;
 78 }   

www.acmicpc.net/problem/11866

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

예 

(7, 3)

1 2 3 4 5 6 7

3번째  제거  3

4 5 6 7 1 2

3번째 제거  6

4 5 6 7 1 2

3번째 제거 2

7 1 2 4 5

3번째 제거 7

4 5 7 1

3번째 제거 5

 1 4 5

3번째 제거 1

1 4

나머지 남은 건

4

[키 포인트]

큐는 FIFO인 특성을 잘 이해하고 풀면 될 것 같습니다. 

front를 빼서 다시 push하면 loop를 돌면서 저장되는 특성이 있는 걸 이해하면 쉽게 풀 수있을 것 같습니다. 

[풀이 ]

loop( queue가 빌때까지 ){

  K-1 만큰 front를 다시  queue에 저장 

  K번째는 front해서 print하고 나서 pop해서 제거 

}

/*baekjoon 11866 queue*/
#include <iostream>
#include <queue>

using namespace std;
queue<int> q;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);


	int i=0,j=0;
	int N; // N명 
	int K; //K번째 제거 
	cin >> N;
	cin >> K;



    for(i =1; i <= N; i++ ){
        q.push(i);
    }

    cout << "<";
    while( !q.empty() ){
        for(i=0; i<K-1; i++){
            q.push( q.front() );
            if(!q.empty()){  q.pop(); }
            j++;
        }

        j++;
        if( !(j%K) ) {

            if(q.size() != 1)
                cout << q.front() << ", ";
            else if(q.size() == 1)
                cout << q.front();

            if(!q.empty()){
                q.pop(); }
        }
    }

    cout << ">" << endl;


	return 0;
}

www.acmicpc.net/problem/2164

N=4일 경우 

1 2 3 4

규칙 : 아래 반복 

맨 위 카드 버림 --> 맨 위 카드를 맨 아래로 이동 --> 맨 위카드 버림 --> 맨 위카드를 맨 아래로 이동 

1 2 3 4

맨 위 카드 버림

2 3 4

맨 위 카드 맨 아래 

3 4 2

맨 위 카드 버림

4 2

맨 위 카드 맨 아래로

2 4

맨 위 카드 버림

4

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;
#define MAX_N 100
queue<int> q;


int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);


	int i,n,tmp;
	cin >> n;



	for(i =1; i <= n; i++ ){
		q.push(i);
	}

	while( 1 ){
		if( q.size() ==1)
			break;

		q.pop();
		tmp = q.front();	
		q.pop();
		q.push(tmp);
	}

	cout << q.front();
		
	return 0;
}

www.acmicpc.net/problem/18258

queue사용 기본 동작 확인하는 문제이다. 

아래와 같이 풀면 되는데, c++인데 printf,scanf는 c용 함수를 쓰는게 좀 아닌 것 같아서 다시 수정을 해 봤습니다.

/*baekjoon 18258 queue*/
#include <iostream>
#include <queue>
#include <cstring>

using namespace std;
#define MAX_N 100

int main()
{

	int n,i,dt;
	char str[10];

	cin >> n;

	queue<int> q;


	for(i =0; i < n; i++ ){


			scanf("%s", str);

		if( !strcmp(str, "push") ){
			scanf("%d", &dt);
			q.push(dt);
		}else if( !strcmp(str, "front") ){
			if(!q.empty()){
				printf( "%d\n", q.front() );
			} else{
				printf("-1\n");
			}
		}else if(  !strcmp(str, "back") ){
			if(!q.empty()){
				printf( "%d\n", q.back() );
			} else{
				printf("-1\n");
			}
		}else if( !strcmp(str, "size") ){
			printf( "%ld\n", q.size() );
		}else if( !strcmp(str, "empty") ){
			printf( "%d\n", q.empty() );
		}else if( !strcmp(str, "pop") ){
			if(!q.empty()){
				printf( "%d\n", q.front() );
				q.pop();
			} else{
				printf("-1\n");
			}
		}
	}

	return 0;
}

printf--> cout, scanf-->cin으로 변경해서 다시 제출해 봤습니다.  시간 초과 발생해서 googling 해 보니 아래를 추가해야 한다고 합니다.

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

<시간 초과 발생>

/*baekjoon 18258 queue*/
#include <iostream>
#include <queue>
#include <cstring>

using namespace std;
#define MAX_N 100

int main()
{
	int n,i,dt;
	char str[10];
	cin >> n;

	queue<int> q;


	for(i =0; i < n; i++ ){

		cin >> str;

		if( !strcmp(str, "push") ){
			cin >> dt;
			q.push(dt);
		}else if( !strcmp(str, "front") ){
			if(!q.empty() ){
				cout << q.front() << '\n' ;
			}else{
				cout << "-1" << '\n';
			}
		}else if( !strcmp(str, "back") ){
			if(!q.empty() ){
				cout << q.back() <<  '\n';
			}else{
				cout << "-1" << '\n';
			}
		}else if( !strcmp(str, "size") ){
			cout << q.size() << '\n';
		}else if( !strcmp(str, "empty") ){
			cout << q.empty() << '\n';
		}else if( !strcmp(str, "pop") ){
			if(!q.empty() ){
				cout << q.front() << '\n';
				q.pop();
			} else {
				cout << "-1" << '\n';
			}
		}
	}

	return 0;
}

추가하고 다시 시도 했을 때 정답이라고 뜨네요. 왜 그러지는 좀 더 확인 해 봐야겠습니다.

/*baekjoon 18258 queue*/
#include <iostream>
#include <queue>
#include <cstring>

using namespace std;
#define MAX_N 100

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);


	int n,i,dt;
	char str[10];
	cin >> n;

	queue<int> q;


	for(i =0; i < n; i++ ){

		cin >> str;

		if( !strcmp(str, "push") ){
			cin >> dt;
			q.push(dt);
		}else if( !strcmp(str, "front") ){
			if(!q.empty() ){
				cout << q.front() << '\n' ;
			}else{
				cout << "-1" << '\n';
			}
		}else if( !strcmp(str, "back") ){
			if(!q.empty() ){
				cout << q.back() <<  '\n';
			}else{
				cout << "-1" << '\n';
			}
		}else if( !strcmp(str, "size") ){
			cout << q.size() << '\n';
		}else if( !strcmp(str, "empty") ){
			cout << q.empty() << '\n';
		}else if( !strcmp(str, "pop") ){
			if(!q.empty() ){
				cout << q.front() << '\n';
				q.pop();
			} else {
				cout << "-1" << '\n';
			}
		}
	}

	return 0;
}

www.acmicpc.net/problem/1874

이 문제는 여러 우여곡절 끝에 답을 찾은 문제 입니다.

for loop에 39,43 라인에 원래 cout을 사용했더니 시간초과로 정답이 안되는 문제가 있어서 여기저기 찾아보니

endl이 시간을 많이 소모해서 문제가 된다고 하여 printf로 수정했습니다. 

endl을 '\n'으로 바꾸셔도 되고 아예 printf문으로 다 바꿔도 됩니다. 

cout이 편리해서 잘 사용하고 있었는데, 이런 문제가 있네요. 참고로 하시기 바랍니다.  

아래 코드도 아직 틀렸다고 하는데 왜 틀렸는지 잘 모르겠네요. 혹시 아시는 분은 아래 답변 좀 부탁드립니다. 

cout << dtout[i] << endl;

cout << "NO" << endl;

  1 /*baekjoon 1874*/                                                                         
  2 #define _CRT_SECURE_NO_WARNINGS
  3 #include <iostream>
  4 #include <stack>
  5 #include <string.h>
  6 
  7 using namespace std;
  8 #define MAX 100001
  9 int dt[MAX];
 10 char dtout[MAX];
 11 stack<int> s;
 12 
 13 
 14 int main()
 15 {
 16     int i,j=0,k=0, n;
 17     int size;
 18 
 19     /* input size*/
 20     cin >> n;
 21 
 22     /* input data*/
 23     for(i= 0; i<n; i++ ){
 24         cin >> dt[i];
 25     }
 26 
 27     for( i=1; i <= n; i++){
 28         s.push(i);
 29         dtout[k++] = '+';
 30         while( !s.empty() && s.top() == dt[j] ){
 31             s.pop();
 32             dtout[k++] = '-';
 33             j++;
 34         }
 35     }
 36 
 37     size = strlen( dtout );
 38     if( !s.empty() ) {
 39         printf("NO");
 40         return 0;
 41     }else{
 42         for( i = 0; i< size; i++) {
 43             printf("%c\n", dtout[i]);
 44         }
 45     }
 46 
 47     return 0;
 48 }

프로그램 실행 시 아래 메시지 찍고 동작 안할 때 디버깅 방법 
세그멘테이션 오류 (코어 덤프됨)


l  코어파일 분석하기

 
코어파일은 충돌할 당시 프로세스의 메모리 이미지를 덤프한 것이다. 코어파일을 gdb와 함께 사용하여 프로그램의 상태를 조사하고 실패 원인을 규명할 수 있다. 어떤 예기치 않은 일이 발생하여 비정상적인 종료가 발생할 때 운영체계는 디스크에 코어 파일을 남긴다.메모리에 관한 문제는 Checker 패키지를 사용하여 예방할 수 있다. 하지만 메모리 fault를 일으키는 경우에는 충돌하면서 파일을 덤프한다. 코어파일은 일반적으로 프로세스를 실행시킨 현재 작업 디렉토리에 생성되지만 프로그램 내에서 작업 디렉토리를 바꾸는 경우도 있다.

보통 리눅스는 부팅시에 코어 파일을 만들지 않도록 세팅되어 있다. 코어 파일 생성을 가능케 하려고 한다면 그것을 다시 가능케 하는 셀의 내장 명령을 사용한다.

만약C쉘 호환 쉘(tcsh)을 쓰고 있다면 다음과 같이 명령을 내린다.

%  limit core unlimited

만약 본쉘류( sh , bash , zsh , pdksh )를 사용하고 있다면,

$  ulimit –c unlimited

와 같은 명령을 내린다.

코어파일을 함께 사용하기 위해선 다음과 같이 한다.

% gdb program core

 
참고로 ulimte -a 를 하면 현재 설정값을 볼 수 있다. core file size가 설정전 default값은 '0'이다.

core dump로 저장을 하려면 이 값을 unlimited로 변경해야 저장이 된다.

변경 방법은 아래와 같이 하면되고 변경 후의 값은 ulimit -a로 확인 가능하다. 

ulimit -c unlimited