Twinparadox Factory

시간 제한 : 0.3초메모리 제한 : 512MB 입력첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 N(1≤N≤500,000)이 주어진다. 셋째 줄부터 N개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다. 명령어는 위의 네 가지 중 하나의 형태로만 주어진다. 출력첫째 줄에 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 출력한다. 소스코드#include #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cout.tie(NULL); st..

C++로 알고리즘 문제를 풀다 보면 STL을 자주 사용한다. 다양한 방식으로 자료를 다루는 스택, 큐, 링크드 리스트 등을 직접 구현하지 않아도 최적화된 환경에서 잘 이용해먹을 수 있게 해주는 도구로, 이번 포스트에서는 STL에서 list에 대해 간단하게 다뤄볼까 한다. 사실, 다룬다는 개념보다는 정리한다는 측면이 더 강할 것이다. list는 순차적인 컨테이너로, 메모리 할당은 연속적으로 이루어지지 않는다. vector와 비교했을 때, 랜덤 접근이나 탐색 측면에서는 vector가 더 좋은 성능을 보이지만, 특정 위치를 정해둔 상태에서 삽입이나 삭제가 이루어질 경우에는 vector에 비해 빠르다는 장점을 가지고 있다. 종합적으로 볼 때, list는 중간 데이터 삭제와 삽입이 자주 발생하면서, 순차적으로 저..

C언어로만 작성했던 것들을 C++로 작성하면서 C++과 자료구조 공부를 동시에 하려고 한다. 지난번에는 C++로 간단한 삽입, 삭제, 출력 기능만 넣은 단일 연결 리스트를 구현했다. 이번에 올리는 글은 이중 연결 리스트(Double Linked List)로, 다음 노드에 대한 포인터만 가지고 있는 단일 연결 리스트와는 달리 이전 노드에 대한 포인터도 가지고 있어, 노드 간의 이동을 양방향으로 할 수 있게 구현하는 자료구조를 뜻한다. #include using namespace std; class Node { friend class List; private: Node* next; Node* prev; int value; Node(Node* n, Node* p, int v) { next = n; prev =..

C언어로 쉽게 풀어쓴 자료구조 4장 Exercise 문제들이다. 필자가 학교 다니면서 자료구조론 수업을 들었는데, 과제로 제출했던 것들이고, 난항을 겪고 있는 사람들에게 참고가 되었으면 하는 마음으로 올린다. 자고로, 버그가 존재할 수 있으니 디버깅 작업은 필수다. 23번. 두 개의 다항식이 다음과 같이 주어졌다. 이들을 연결 리스트를 이용하여 나타내고 본문의 프로그램을 이용해 두 다항식의 합을 구해보라. 24번. 다항식을 연결 리스트로 표현할 수 있음을 보였다. 다항식이 연결 리스트로 표현되어 있고, p를 다항식을 가리키는 포인터라고 할 때, 어떤 실수 x에 대해 이 다항식의 값을 계산하는 함수 poly_eval을 작성하라. 25번. 다항식이 연결 리스트로 표현되어 있는 경우, 두 개의 다항식을 받아 ..