개요
데이터를 어떻게 조작하느냐에 따라 프로그램의 속도차이가 많이 나게된다.
이러한 데이터 조작 방법을 자료구조라고 합니다.
적합한 알고리즘을 선택하는 것도 중요하다.
재귀
함수가 자기 자신을 호출하는 것
기저 조건과 재귀 조건으로 구성된다.
문제에 따라 전체를 한번에 해결하기보다 같은 유형의 하위 작업으로 분할하여 작은 무제부터 해결하는 방법이 효율적
자료구조
자료구조는 선형 구조 와 비선형 구조로 나뉜다.
선형 구조 : 리스트, 스택, 큐
비선형 구조 : 그래프, 트리
선형구조는 일렬로 조직이 된것이고 비선형은 일렬로 되어 있지 않다.
자료구조에는 네 가지 연산이 있다.
읽기 : 자료구조 내 특정 위치를 찾아보는 것이다.
검색 : 자료구조 내 특정 값을 찾는 것이다.
삽입 : 자료구조에 새로운 값을 추가하는 것이다.
삭제: 자료구조 내 특정 값을 삭제하는 것이다.
자료구조를 구현하는 방법
순자 자료구조 : 배열을 이용 -> 구현할 자료들을 논리적인 순서대로 메모리에 연속하여 저장하는 구현 방식
연결 자료구조 : 포인터를 이용 -> 노드라는 여러 개의 메모리 청크에 데이터를 저장하며, 이를 연결하여 구현하는 방식
프로그래머는 둘의 특징을 명확히 알고 구현할 작업에 따라 둘중 하나를 선택하거나 조합하여 응용프로그램을 개발해야 함
알고리즘의 분석
자원의 사용량을 분석하는 것 이다.
자원을 적게 사용할 수록 효율적인 알고리즘
시간 복잡도
어떤 컴퓨터, 어떤 언어로 구현했는가에 따라 시간은 다 다르다. 그래서 하드웨어와 소프트웨어 환경을 배제한 객관적인 지표가 필요하다.
시간복잡도는 알고리즘을 수행하는데 필요한 연산이 몇 번 실행되는지를 숫자로 표기
이 연산의 개수는 상수가 아니라 입력한 데이터의 개수를 나타내는 n에 따라 변하게 된다.
입력값이 작을 때는 차이가 크지 않지만 점점 커질수록 차이가 벌어진다. 이를 실행시간의 성장률 이라 한다.
Big-O 표기법
다항식의 시간 복잡도 함수에서 입력값이 커져감에 따라 각 항의 결과값에 관여하는 정도가 달라지게 됨
T(n)=2n2+1에서 2n2대비 1의 영향이 매우 작음을 알 수 있다.
점근적 표기법
시간 복잡도와 뒤에 배울 공간 복잡도를 표시할 때는 각 함수의 모든 항을 표시하지 않으며 상수 계수와 중요하지 않은 항목을 제거한것 이다.
Big-θ, Big-O, Big-Ω 등이 있지만 이중 가장 많이 사용되는 것은 Big-O 표기법이다.
Big-O 표기법은 점근적 상한선을 제공한다.
한 알고리즘이 다른 알고리즘보다 실제로 빠르다고 하더라도 같은 방식으로 표현이 될 수도 있다
2n + 3 => O(n)
2n + 1 => O(n) 으로 표기되기에 분석이 필요하다.
공간 복잡도
알고리즘을 수행하는 데 필요한 지원 공간의 양
공간을 더 써서 시간을 줄일 수 있다면 그렇게 하는 편이다.
메모리 < 시간 인 샘이다.
하지만 이때도 남은 메모리량에 따라 다를 수 있다.
STL
표준 템플릿 라이브러리(Standard Template Library) 이다.
이게 다 라이브러리 이다.
이중 우리가 살펴볼 것은
임의 타입의 객체를 보관할 수 있는 컨테이너 라이브러리(Container Library)
컨테이너에 보관된 원소에 접근할 수 있는 반복자 라이브러리(Iterator Library)
반복자를 가지고 일련의 작업을 수행하는 알고리즘 라이브러리(Algorithm Library)
컨테이너는 앞으로 배우게 될 자료구조의 구현체
반복자는 컨테이너의 요소에 접근할 수 있는 포인터
알고리즘은 반복자를 기반으로 수행되는 절차
이렇게 나뉘게 된 이유는 구현 코드의 개수를 줄이기 위함이다.
컨테이너의 개수를 N, 알고리즘의 개수를 M이라 한다면, 컨테이너 각각에 알고리즘을 구현할 때 필요한 구현 코드의 개수는 N * M이다. 이 사이에 반복자를 추가함으로써 반복자를 통해 각 요소에 추상적으로 접근이 가능하게 돼 총 필요한 구현 코드의 개수를 N + M으로 줄일 수 있다
이를 디자인패턴 중 반복자 패턴 이라 한다.
리스트
리스트는 순서를 갖고있는 자료구조다.
순차 자료구조엔 선형 리스트가 있고, 연결 자료구조엔 단일 연결 리스트, 원형 연결 리스트, 이중 연결 리스트가 있다.
선형 리스트
순서 리스트 라고도 불린다.
임의 접근이 가능하다.
STL 상에서는
std::array (정적배열 실행시간 중 변할 수 없다)
std::vector (동적배열 실행시간중 변할 수 있다)
로 구현되어 있다.
읽기
선형 리스트는 임의 접근이 가능하기 때문에 O(1)의 시간이 걸린다. (상수 시간)
검색
특정 원소를 찾는 것
하나하나 원소를 비교해가야 하므로 O(n)의 시간이 걸린다. 정렬되어 있다면 이진 검색을 사용할 수 있으며 이 경우 O(logn)이다.
입력값이 많으면 많을수록 선형적으로 늘어나기에 시간이 늘어날 수 있다.
삽입
자료를 넣는 것
원소를 어디에 삽입하냐에 따라 시간이 달라진다. 맨 끝에 데이터를 추가할 경우 O(1)이지만, 처음이나 중간이라면 모든 데이터를 이동해야 하기에 O(n)이 걸린다.
삭제
삽입과 마찬가지로 원소를 어디에서 삭제하냐에 따라 시간이 달라진다. 맨 끝의 데이터를 삭제할 경우 내부적 데이터를 이동 할 필요가 없어 O(1)이지만, 처음이나 중간이라면 모든 데이터를 이동해야 하기에 O(n)이 걸린다.
연결 리스트
연결 자료구조
선형 리스트와 연결 리스트를 잘 알고있어야 함 : 가장 기본이 되기 때문
연결리스트는 std::forward_list, std::list로 구현되어 있다.
선형 리스트와 다르게 임의 접근이 불가능하다.
임의 접근 : 어떤걸 선택하더라도 바로 접근 할 수 있는거
입의 접근이 가능한 이유 : 주소값을 알고있기 때문
메모리가 연속적으로 할당이 되기에 주소를 계산할 수 있는것이다.
선형 리스트 vs 연결 리스트
선형리스트는 메모리가 연속적으로 저장되어있기에 주소값을 계산할 수 있어 임의접근이 가능하지만 연결 리스트는 메모리에 연속적으로 저장되어있지 않기에 임의접근이 불가능하다.
읽기
O(n)의 시간이 걸린다.
프로그램이 커지면 커질수록 점점 더 걸린다.
하지만 프로그램의 처음과 끝 이라면 O(1) 이 될 수 있다.
검색
O(n)의 시간이 걸린다.
하나하나 원소를 비교해야 한다.
이진검색을 사용할 수 없다.
삽입
원소를 어디에 삽입하냐에 따라 달라진다.
앞이나 뒤에 데이터를 추가한다면 O(1) 이지만
중간이라면 해당위치까지 검색을 해야 하기에 O(n)이 걸린다.
하지만 정확한 위치를 안다면 O(1) 이다.
삭제
원소를 어디에 삭제하냐에 따라 달라진다.
앞이나 뒤에 데이터를 삭제한다면 O(1) 이지만
중간이라면 해당위치까지 검색을 해야 하기에 O(n)이 걸린다.
하지만 정확한 위치를 안다면 O(1) 이다.
std::forward_list
단일 연결 리스트
예제
#include <forward_list> // std::forward_list를 쓰기 위한 헤더
#include <iostream>
int main()
{
std::forward_list<int> flist;
// 삽입
flist.push_front(1); // push_front() : 맨 앞에 삽입한다.
// flist{ 1 }
flist.insert_after(flist.begin(), 2); // insert_after(pos, value) : pos 뒤에 value를 삽입한다.
// pos 이전의 주소를 모르기 때문에 이전에 넣을 수 없다.
// flist{ 1, 2 }
flist.push_front(3); // flist { 3, 1, 2 }
// 반복자
std::forward_list<int>::iterator iter;
// 구현의 편의를 위해 더미노드를 넣음
iter = flist.before_begin();
// [ ]->[3]->[1]->[2]->[ ]
// ↑
iter = flist.begin();
// [ ]->[3]->[1]->[2]->[ ]
// ↑
iter = flist.end();
// [ ]->[3]->[1]->[2]->[ ]
// ↑
// 삭제
flist.pop_front(); // pop_front() : 첫 번째 원소를 삭제한다.
// flist{ 1, 2 };
// flist.erase_after(flist.before_begin()); : 앞의 원소를 삭제한다.
// flist{ 2 };
flist.erase_after(flist.begin()); // erase_after(pos) : pos 다음 원소를 삭제한다.
// flist{ 1 }
flist.clear(); // clear() : 컨테이너를 전부 비운다.
// flist{ }
// 크기
if (flist.empty()) // empty() : 비었는지 확인한다.
{
std::cout << "flist는 비었음.\n";
}
// 주의! 다른 컨테이너와 다르게 size()는 없음
// 아래처럼 초기화 가능
std::forward_list<int> flist2 = { 1, 2, 3, 4, 5 };
// 읽기
// back() : 뒤의 주소값을 모르니까 없음
std::cout << "flist2.front() : " << flist2.front() << "\n"; // front() : 첫 번째 원소를 반환한다.
// 비교 : 다른 컨테이너와 마찬가지로 == / != / > / >= / < / <= 지원
flist = flist2;
if (flist == flist2)
{
std::cout << "flist는 flist2와 같다.\n";
}
// C++17부터는 원소 타입을 적지 않아도 알아서 추론한다. // 17버전부터 가능해졌다.
std::forward_list flist3 = { 1, 2, 3, 4, 5 };
return 0;
}std::list
이전 원소롣 이동할 수 있는 이중 연결 리스트 이다.
예제
#include <list> // std::list를 쓰기 위한 헤더
#include <iostream>
int main()
{
std::list<int> list;
// 삽입
list.push_front(1); // push_front() : 맨 앞에 삽입한다.
// list{ 1 }
list.push_back(2); // push_back() : 맨 뒤에 삽입한다.
// list{ 1, 2 }
list.insert(list.begin(), 9); // insert(pos, value) : pos 전에 value를 삽입한다.
// list{ 9, 1, 2 }
list.push_back(5); // list{ 9, 1, 2, 5 }
// 반복자
std::list<int>::iterator iter;
iter = list.begin();
// [9]<->[1]<->[2]<->[5]<->[ ]
// ↑
iter = list.end();
// [9]<->[1]<->[2]<->[5]<->[ ]
// ↑
std::list<int>::reverse_iterator riter;
riter = list.rbegin();
// [ ]<->[9]<->[1]<->[2]<->[5]
// ↑
riter = list.rend();
// [ ]<->[9]<->[1]<->[2]<->[5]
// ↑
// 삭제
list.pop_front(); // pop_front() : 첫 번째 원소를 삭제한다.
// list{ 1, 2, 5 };
list.pop_back(); // pop_back() : 마지막 원소 삭제한다.
// list{ 1, 2 };
list.erase(list.begin()); // erase(pos) : pos를 삭제한다.
list.clear(); // clear() : 컨테이너를 전부 비운다.
// list{ }
// 크기
if (list.empty()) // empty() : 비었는지 확인한다.
{
std::cout << "list는 비었음.\n";
}
std::cout << "list.size() : " << list.size() << "\n";
// 아래처럼 초기화 가능
std::list<int> list2 = { 1, 2, 3, 4, 5 };
// 읽기
std::cout << "list2.front() : " << list2.front() << "\n"; // front() : 첫 번째 원소를 반환한다.
std::cout << "list2.back() : " << list2.back() << "\n"; // back() : 마지막 원소를 반환한다.
// 비교 : 다른 컨테이너와 마찬가지로 == / != / > / >= / < / <= 지원
list = list2;
if (list == list2)
{
std::cout << "flist는 flist2와 같다.\n";
}
// C++17부터는 원소 타입을 적지 않아도 알아서 추론한다.
std::list list3 = { 1, 2, 3, 4, 5 };
return 0;
}std::forward_list
한쪽 방향만으로 가야하고 갯수도 필요 없을 때 forward_list를 사용하는것이 좋다.
Node : 단순히 가리키는 것
iterator : 기능
#pragma once
#include <stddef.h>
class ForwardList
{
// 연결 리스트에서 데이터를 저장하기 위한 타입
// 즉, 연결 리스트는 데이터를 직접적으로 다루는 것이 아니라
// Node라는 것으로 다룹니다.
// private 으로 Node는 외부에 공개가 되있지 않다.
struct Node
{
Node(int data = 0, Node* next = nullptr);
Node(const Node&) = delete;
Node& operator=(const Node&) = delete;
~Node();
int Data = 0; // 실제 데이터
Node* Next = nullptr; // 다음 원소
};
public:
// 데이터를 수정할 수 없는 반복자.
// const int* 같은 것 이다.
class const_iterator
{
public:
const_iterator(Node* p = nullptr);
~const_iterator();
const int& operator*() const; // 역참조
const int* operator->() const; // 멤버 접근
const_iterator& operator++(); // 전위 증가 연산자
const_iterator operator++(int); // 후위 증가 연산자
bool operator==(const const_iterator& rhs) const;
bool operator!=(const const_iterator& rhs) const;
bool operator==(nullptr_t p) const;
bool operator!=(nullptr_t p) const;
public:
Node* _p = nullptr;
};
// 데이터 수정이 가능한 반복자
// int*
class iterator : public const_iterator
{
public:
iterator(Node* p = nullptr);
int& operator*() const;
int* operator->() const;
iterator& operator++();
iterator operator++(int);
};
// 기본 생성자
ForwardList();
// count만큼의 요소를 갖고 있는 컨테이너를 만드는 생성자
explicit ForwardList(size_t count);
// 복사 생성자.
ForwardList(const ForwardList& other);
// 할당 연산자
ForwardList& operator=(const ForwardList& rhs);
// 소멸자
~ForwardList();
// 첫 번째 요소를 반환한다.
int& front();
const int& front() const;
// 시작 전 요소를 가리키는 반복자를 반환한다.
iterator before_begin();
const_iterator before_begin() const;
// 시작 요소를 가리키는 반복자를 반환한다.
iterator begin();
const_iterator begin() const;
// 끝 다음 요소를 가리키는 반복자를 반환한다.
iterator end();
const_iterator end() const;
// pos 다음에 value를 삽입한다.
// 삽입된 요소를 가리키는 반복자를 반환한다.
iterator insert_after(const_iterator pos, int value);
// pos 다음 요소를 삭제한다.
// 삭제된 요소의 다음 요소를 가리키는 반복자를 반환한다.
// 아무 요소도 없으면 end()를 반환한다.
iterator erase_after(const_iterator pos);
// 시작 요소에 value를 삽입한다.
void push_front(int value);
// 시작 요소를 제거한다.
void pop_front();
// 컨테이너가 비었는지 판단한다.
bool empty() const;
// 컨테이너를 비워버린다.
void clear();
// value가 있는지 검사한다. // 이 값이 현재 stl에 있는가
bool contains(int value) const;
private:
// 더미노드 : 실제 데이터를 담지 않음. 오로지 구현의 편의성만을 위해서 존재
Node* _head = new Node(); // before_begin();
// 더미노드 :
Node* _end = new Node(); // end();
};#include "헤더.h"
#include <algorithm>
ForwardList::ForwardList()
{
// _head -> []
// _end -> []
// [] -> []
_head->Next = _end;
}
ForwardList::ForwardList(size_t count) // count만큼의 요소를 갖고 있는 컨테이너를 만드는 생성자
:ForwardList()
{
for (size_t i = 0; i < count; ++i)
{
push_front(0);
}
}
ForwardList::ForwardList(const ForwardList& other) // 복사 생성자
: ForwardList()
{
iterator inserted = before_begin();
for (const_iterator iter = other.begin(); iter != other.end(); ++iter)
{
inserted = insert_after(inserted, *iter);
}
}
ForwardList& ForwardList::operator=(const ForwardList& rhs) // 할당 연산자
{
if (&rhs != this)
{
ForwardList temp(rhs);
std::swap(_head, temp._head);
std::swap(_end, temp._end);
}
return *this;
}
ForwardList::~ForwardList() // 소멸자
{
clear();
delete _head;
_head = nullptr;
delete _end;
_end = nullptr;
}
int& ForwardList::front()
{
return *begin();
}
const int& ForwardList::front() const
{
return *begin();
}
ForwardList::iterator ForwardList::before_begin()
{
return _head;
}
ForwardList::const_iterator ForwardList::before_begin() const
{
return _head;
}
ForwardList::iterator ForwardList::begin()
{
return _head->Next;
}
ForwardList::const_iterator ForwardList::begin() const
{
return _head->Next;
}
ForwardList::iterator ForwardList::end()
{
return _end;
}
ForwardList::const_iterator ForwardList::end() const
{
return _end;
}
ForwardList::iterator ForwardList::insert_after(const_iterator pos, int value)
{
// [] -> [] -> [] -> []
// pos
// value
Node* newNode = new Node(value);
Node* where = pos._p;
newNode->Next = where->Next;
where->Next = newNode;
return newNode;
}
ForwardList::iterator ForwardList::erase_after(const_iterator pos)
{
// [] -> [] -> [] -> []
// pos
if (empty())
{
return end();
}
Node* where = pos._p;
Node* removed = pos._p->Next;
where->Next = removed->Next;
removed->Next = nullptr;
return removed;
}
void ForwardList::push_front(int value)
{
insert_after(before_begin(), value);
}
void ForwardList::pop_front()
{
erase_after(before_begin());
}
bool ForwardList::empty() const
{
if (_head->Next == _end) // if (begin() == end())
{
return true;
}
else
{
return false;
}
}
void ForwardList::clear()
{
while (false == empty())
{
pop_front();
}
}
bool ForwardList::contains(int value) const
{
for (const_iterator iter = begin(); iter != end(); ++iter)
{
if (*iter == value)
{
return true;
}
}
return false;
}
