노는 게 제일 좋아

앞서 선형 자료구조만을 공부했는데 비선형 자료구조는 왜 필요할까??? 모든 것이 선형구조가 효율적이지 않음을 알기 때문이다. 알아보자 선형 자료구조로 표현할 수 없는 문제가 생긴다. 계층적 문제와 순환 종속성 문제다. 계층적 문제란 가계도, 어느 단체의 조직도, 고등학교 교육과정 등 다양한 예가 있다. 그냥 이런 것과 비슷하다. 과연 이것의 의미를 선형 자료구조가 담을 수 있을까? 라고 생각해보면 된다. 순환 종속성 문제란 아래와 같다. ABC 순서대로 그냥 저장하면 위의 정보가 전달이 될까? 아무튼 위와 같은 문제들은 비선형 자료구조의 필요를 가져왔고 우리는 트리, 그래프라는 자료구조를 배우게 되었다. 차차 알아보자

[프로그래밍언어(Programming Language)/C || C++] - Deque, 덱 , 자료구조 [CPP] 물론 덱에 대한 글은 썼지만 그냥 사용법만 적어놨다. 아무래도 모든 자료구조는 trade-off 관계일 수 밖에 없다. 하지만 이익을 최대한보고 손해를 최소한으로 하는 인간의 끊임 없는 노력은 vector의 단점마저 극복하고자 하였다. vector에서 push_front() 는 insert로 대신한다고 하였다. erase도 마찬가지다. 즉, 맨 앞에서 일어나는 삽입과 삭제는 cost가 높다. 즉, 시간이 오래걸린다. 그래서 사람들은 덱을 만들어냈다. 덱은 아래 3가지의 조건을 만족해야 한다. push_front(), pop_front(), push_back(), pop_back()에 있어서..

우선 forward_list가 기름기를 뺀 리스트라면 이건 건강한 음식인 list이다. 이 list는 이중 연결 리스트, doubly-linked list 구조로 되어 있다. 때문에 prev를 가리키는 포인터가 있기에 더 메모리를 먹는다는 점부터 알고 시작하자. 다시 말해서 데이터, 다음 노드를 가리키는 포인터, 이전 노드를 가리키는 포인터 3가지를 가지고 있다는 것이다. forward_list와 list의 차이점은 list에서 _after로 끝나는 함수들이 이제는 after가 없어진다. insert_after -> insert emplace_after -> emplace 왜냐하면 원소 이동을 역방향으로도 가능하니까 원소 삽입이나 삭제를 위해 특정 원소의 이전 원소 반복자를 제공하지 않아도 되니까..? ..

연결된 구조, 연속된 구조에서 둘 다 반복자, iterator를 쓰지만 서로 다르게 구현되어 있다. 그도 그럴 것인게.. 메모리 주소 접근 방식을 생각해보면 쉽다. 단일 메모리 블럭에 들어있는 주소에 접근과 여러 메모리 블럭에 퍼져있는 주소에 접근하는 것은 다를게 분명하기 때문이다. 배열이나 벡터에서 우리가 쓰는 iterator는 random access iterator라고 한다. 임의의 위치에 바로 접근이 가능하다. forward_list 에서 쓰는 iterator는 forward iterator라고 한다. **하지만 양방향 연결리스트를 들어봤다면 bidirectional iterator도 있겠네라고 생각할 수 있다. 정확하게 맞다. 아무튼 위 연결된 구조 연속된 구조와 다르게 임의의 위치에 바로 접근..

배열과 벡터같은 얀속된 자료 구조에서는... 임의의 위치에서 삽입 삭제가 비효율적이고 말할 수 있다. 즉, 연결된 자료구조를 C++이 제공하느냐?? **list도 있지만 list에서 뺄 것을 빼서 기름기가 쫙빠진 것이 forward_list라고 할 수 있다. 그렇다. 제공한다. 그것이 바로 forawrd_list이다. 연결리스트의 성능은 유지하면서 추가적인 기능을 제공한다. 하지만 성능 유지를 위해 임의의 위치에 대한 직접 접근을 허용하지 않으며 전체 리스트의 크기를 바로 알 수는 없다. 즉, 맨 처음 원소에 접근하는 front()는 제공하지만 맨 뒤의 원소에 접근하는 back()같은 것은 지원하지 않는다. 그리고 연결된 구조와 연속된 구조의 iterator, 반복자는 종류가 다름을 생각하자 forwar..

C++에서는array도 제공하지만 vector도 제공한다. 왜 우리는 vector를 쓰는가? 우선 array는 컴파일할 때 크기가 결정된다. 즉, 미리 알고 선언해야한다는 말이다. 크기가 고정되어있으므로 원소의 데이터는 바꿀 수 있어도 원소를 추가하거나 삭제하는 일은 불가능하다. 또한 컴파일할 때 크기가 결정되므로 무조건 스택 메모리를 사용한다. 솔직히 거의 모든 응용프로그램에서는 데이터가 동적이며 크기도 고정되어 있지 않은 게 현실이다. 때문에 데이터의 크기를 미리 알고 있는 것은 어렵다 **다만 메모리가 많다면 미리 선언하는 것도 나쁘지는 않다고 본다. 하지만 효율적인 활용을 위해선, 위 상황을 제외하면 가변 크기의 데이터 컨테이너가 있었으면 좋겠다고 생각한다. 바로 그것이 vector이다. //1...

기본 중에 기본부터 알아보자 응용프로그램을 설계할 때 가장 중요하게 고려해야 할 점 중 하나인 데이터 관리는 매우 중요하다. 즉, 우리는 응용 프로그램에 적합한 자료 구조를 사용하는 것이 정말 중요하다. 해결하고자 하는 문제에 적합한 자료구조를 이용하는 것이 응용프로그램 개발에 도움이 된다. 기본 내장 자료구조가 한계가 있다면 우리는 사용자 정의 자료 구조를 구현해야 한다. -> 결국 자료구조를 배우면서 어떤 문제를 해결하는 데에 어떤 자료구조가 필요할 것인가? 임을 배우는 것이 자료구조를 배우는 목적이라고 하겠다. C++에는 자료구조 중 대표적으로 선형 자료구조(Linear Data Structure)가 있다. 선형 자료구조는 또 다시 2가지로 나뉘는데 연속된 구조와 연결된 구조로 나눌 수 있다. (C..

메모리 heap에 생성되며 동적할당이 가능하여 동적 배열을 대체할 수 있는 std:: 를 알아보자 C++ STL 에서 컨테이너는 크게 두 가지 종류가 있다. 배열 처럼 객체들을 순차적으로 보관하는 시퀀스 컨테이너 (sequence container) 키를 바탕으로 대응되는 값을 찾아주는 연관 컨테이너 (associative container) 가 있다. 우리가 알아볼 벡터는 시퀀스 컨테이너다. 벡터에는 원소들이 메모리 상에서 실제로 순차적으로 저장되어 있고 따라서 임의의 위치에 있는 원소를 접근하는 것을 매우 빠르게 수행할 수 있다. 하지만 벡터가 만능인줄 알고 있는 사람들도 있지만 그렇지 않다. 맨 뒤에 원소를 추가하거나 제거하는 것은 빠르지만 임의의 위치에 원소를 추가하거나 제거하는 것은 O(n) 으..

이번엔 스택을 알아보자 스택은 First In Last Out으로 삽입과 삭제 연산이 동일한 장소에서 일어나는 자료구조다. 역시 삽입, 삭제 연산에 있어서 상수 시간복잡도를 가진다. FILO구조는 다시 말하면 LIFO구조다. 마지막에 들어온 것이 먼저 나온다는 이야기다. 데이터를 역으로 추적할 때와 같은 상황에 사용한다. 연결리스트와 유사한 자료구조라고도 한다. (연결리스트로 스택 구현가능) 스택 같은 경우에는 중위-후위 변환 재귀함수와 같은 함수 호출 구현 **웹브라우저의 뒤로가기 (페이지기록) 문서 어플리케이션,에디터의 Ctrl + z , undo 기능등과 같은 곳에 쓰인다. 스택은 배열, 동적배열(Vector), 연결리스트로 구현이 가능하다. push(), pop()이 같은 장소에서 일어나고 que..

자료구조의 큐에 대해서 알아보자 First In First Out의 구조를 가지고 있으며 방향성이 있는 자료구조이다. 삽입과 삭제 연산이 일어나는 곳이 다르다는 이야기다. -> 이 개념이 가장 중요하다. 이러한 일을 처리할 때 쓰는 것이다. 또한 삽입,삭제 연산에 있어서는 상수의 시간복잡도를 가진다. ** 주로 순차적으로 진행되어야 하는 일을 스케줄링할 때 사용된다. 주로 우리의 일상적으로 쓰는 곳에 있다. 줄을 서서 기다리는 모든 것들이 큐와 같다. ** 큐를 CPP에서 사용하기 위해서는 헤더를 사용해서 포함시켜야 한다. 큐를 선언할 때 원소가 될 자료형을 선언하며 크기는 선언하지 않았다. 하지만 enqueue와 dequeue를 사용하는 대신 push() 와 pop()를 사용하며 -> push는 bac..