Brute force Study

std::forward_liststd::array, std::vector와 같은 연속된 자료구조는 데이터 중간에 자료를 추가, 삭제하는 작업이 매우 비효율적임따라서 연결 리스트 기반 컨테이너가 등장함연결 리스트를 구성하는 중에 포인터와 관련된 버그 양산을 막기 위해 연결 리스트 wrapper class인 std::forward_list 클래스를 제공함std::forward_list의 기본적인 기능연결 리스트의 성능을 유지하면서 기본적인 기능을 제공함성능 유지를 위해 전체 리스트 크기를 반환하거나, 첫 번째 원소를 제외한 나머지 원소에 직접 접근하는 기능을 제공하지 않음front() 함수는 제공하지만, 거꾸로 움직이는 back() 함수는 제공하지 않음원소의 삽입, 삭제, 순서 뒤집기, 분할을 위한 기능은 ..

std::vectorstd::array의 단점std::array의 크기는 컴파일 시간에 결정되는 상수이어야 한다.런타임 중에 변경할 수 없다.크기가 고정되어 있어서 원소를 추가/삭제할 수 없다.항상 스택 메모리를 사용한다. 메모리 할당 방법을 바꿀 수 없다따라서 가변 크기의 데이터를 처리할 수 있는 컨테이너가 필요하다 --> std::vectorstd::vector - 가변 크기 배열배열 기반으로 구현되어 있다초기화 과정에서 데이터의 크기를 제공하지 않아도 된다std:array의 '고정 크기' 문제를 해결한다벡터를 초기화 하는 몇 가지 방법// 크기가 0인 벡터 선언std::vector vec;// 지정한 초깃값으로 이루어진 크기가 5인 벡터 선언std::vector vec = { 1, 2, 3, 4, ..

보호되어 있는 글입니다.

보호되어 있는 글입니다.

덱(Dequeue) 덱이란? Dequeue : Double-ended Queue 여기선 큐의 출력을 의미하는 Dequeue와 다른 의미로 사용됨 a.k.a 데크 전단, 후단 양쪽에서 push, pop이 가능함 스택과 큐의 장점을 모아둔 자료구조 덱의 종류 스크롤 : 입력이 한쪽 끝으로만 가능하도록 제한, 입력 제한 덱이라고도 함 셀프(Shelf) : 출력이 한쪽 끝으로만 가능하도록 제한, 출력 제한 덱이라고도 함 보통 양쪽에서 입력/출력을 모두 하는 경우는 거의 없어 스크롤이나 셀프를 사용한다 덱의 용도 스케줄링 우선순위 조절 덱의 동작 입력과 출력이 양방향에서 가능하고, 입력과 출력의 순서를 맘대로 정할 수 있음 추가 및 삭제의 실행속도는 O(1) 이중 연결 리스트로 덱 구현 #include #incl..

링크드 큐(Linked Queue) 링크드 리스트를 이용하여 큐를 구현 노드 멤버의 포인터를 이용하여 삽입 / 제거 연산이 이루어짐 삽입을 할 때는 삽입하려는 노드에 후단을 연결 제거를 할 때는 전단 바로 다음 노드에 전단에 대한 포인터를 거두기만 하면 됨 원형 큐(순환 큐)와 다른 점은 용량 제한이 없다는 것이다.(가득 찼는지 확인할 필요 X) 링크드 큐의 기본 연산 보다 직관적으로 설계 및 구현이 가능함 링크드 큐와 노드의 선언 노드의 경우 데이터 필드와 다음 노드에 대한 포인터를 담는다 링크드 큐 구조체의 경우 전단, 후단, 노드 개수를 담는다 // 노드 구조체 typedef struct _Node { char* data; // 노드에 담을 데이터 struct _Node* nextNode; // 다..

큐(Queue)큐의 ADT큐의 개념입력과 출력 창구가 따로 존재하고, 제일 먼저 들어간 데이터가 제일 먼저 나옴(FIFO)큐의 핵심 기능 : 삽입과 제거전단 : 큐의 가장 앞 요소, 제거 연산이 일어나는 곳후단 : 큐의 가장 마지막 요소, 삽입 연산이 일어나는 곳순환 큐(원형 큐)큐를 배열로 구현하는 경우 전단을 제거한 후 요소를 이동하는데 비용이 매우 큼큐의 전단과 후단을 가리키는 변수를 도입삽입과 제거를 거치다 보면 큐의 용량이 줄어듬순환 큐 : 배열의 끝과 시작을 연결함배열의 마지막 요소가 후단인 경우 삽입 연산을 진행하면 배열의 첫 번째 요소가 후단이 된다전단의 경우도 마찬가지삽입이 이루어질 때 후단이 전단을 만나면 큐는 가득 찬 상태가 된다전단과 후단이 만나있는 경우, 공백 상태화 포화 상태를 ..

연결(링크드) 리스트 기반 스택노드의 경우 Data의 주소를 가리키는 참조형과, 자기 위에 쌓여 있는 노드의 주소를 가리키는 NextNode로 구성스택의 용량이나 최상위 노드의 인덱스가 스택의 멤버로 존재하지 않음링크드 리스트의 헤드와 테일에 대한 포인터는 필요함  typedef struct tagNode {char* Data;struct tagNode* NextNode;} Node;typedef struct tagLinkedListStack { Node* List; // 자유 저장소에 존재하는 헤드 노드의 주소를 가리킴 Node* Top; // 자유 저장소에 존재하는 테일 노드의 주소를 가리킴} LinkedListStack;* Top 포인터는 스택의 입출력이 이루어지는 최상위 노드에 대한 포..

배열 기반 스택배열 기반 스택데이터만 담는 구조체로 노드를 표현스택 구조체의 경우 용량, 최상위 노드의 위치, 노드 배열 총 3가지 필드를 가지고 있어야 함typedef struct tagArrayStack { int Capacity; int Top; Node* Nodes; // 자유 저장소에 할당된 배열을 가리키는 용도로 사용(첫 번째 요소)} ArrayStack;배열 기반 스택의 함수생성void AS_CreateStack(ArrayStack** Stack, int Capacity){ // 스택을 자유저장소에 생성 (*Stack) = (ArrayStack*)malloc(sizeof(ArrayStack)); // 입력된 Capacity만큼의 노드를 ..

환형 링크드 리스트(Circular Linked List)a.k.a 원형 연결 리스트싱글 링크드 리스트나 더블 링크드 리스트와 노드 구성은 동일하지만, 헤드와 테일이 연결되어 있음테일의 nextNode는 헤드를 가리키고, 헤드의 prevNode는 테일을 가리킴리스트의 시작과 끝을 미리 알 수 있다 (시작을 알면 끝을 알 수 있고, 끝을 알면 시작을 알 수 있다)DLL의 삽입 함수와 같은 부분의 성능을 많이 개선할 수 있다. (테일에 접근하는 비용이 거의 없으므로)노드를 뒤에서 역순으로 찾아나갈 수 있는 탐색도 구현할 수 있다.환형 더블 링크드 리스트의 주요 연산추가 / 삭제 연산 이외 함수들은 링크드 리스트와 더블 링크드 리스트 함수와 동일함노드 추가 연산비어있는 리스트에 새 노드를 추가하면 이 노드는 ..