이코딩

힙 힙(Heap)은 완전 이진 트리*에 있는 노드 중에서 값이 가장 큰 노드나 값이 가장 작은 노드를 찾기 위해 만든 자료구조다. 값이 가장 큰 노드를 찾기 위한 힙을 최대 힙(Max Heap), 가장 작은 노드를 찾기 위한 힙을 최소 힙(Min Heap)이라고 한다. 힙은 우선순위 큐(Priority Queue)라고도 한다. STL에서는 std::priority_queue로 구현이 되어 있다. 힙의 불변성 힙이 되기 위한 조건 최대 & 최소 원소에 즉각적으로 접근이 가능해야 한다. //그래서 최대 & 최소 원소는 항상 루트 노드에 존재한다. 부모 노드가 자식 노드보다 항상 크거나(Max Heap), 작아야 한다(Min Heap).//부모와 자식간의 족보가 제대로 갖춰져야 한다. 연산 - 검색 및 읽기 ..

set #include // set을 쓰기 위한 헤더 #include int main() { std::set s; // 삽입 s.insert(1); // s{ 1 } s.insert(2); // s{ 1, 2 } s.insert(3); // s{ 1, 2, 3 } // 중복된 데이터는 삽입할 수 없다. // insert()의 반환은 pair 타입이며 // 두 번째 데이터에 삽입 여부가 담긴다. if (false == s.insert(1).second) { std::cout

이진 트리의 형태 왼쪽 자식 노드값

그래프는 관계에 특화된 자료 구조로 정점(Vertex)과 간선(Edge)으로 구선된다. 정점 : 고유하게 식별되는 객체 간선 : 정점간의 관계 종류 그래프는 간선이 방향성을 가지는 방향 그래프와 무방향 그래프로 구분할 수 있고 간선이 단순 연결 이상의 정보를 가지는 가중치 그래프등 여러가지 종류가 있다. 용어 정리 인접(Adjacent) : 간선으로 연결된 정점끼리를 부르는 말 부속(Incident) : 정점에 연결된 간선 차수(Degree) : 정점에 부속된 간선의 수 진입 차수(In - Degree) : 정점으로 들어오는 방향 진출 차수(Out - Degree) : 정점으로 나가는 방향 경로(Path) : 한 정점에서 다른 정점까지 간선으로 연결된 정점을 순서대로 나열한 리스트 경로 길이(Path l..

큐는 리스트의 일종으로 스택의 LIFO (Last - In First -Out) 구조가 아닌 FIFO (First - In First -Out) 구조를 가지고 있다. FIFO는 (First - In First -Out) 이름과 같이 가장 처음에 들어간 데이터가 가장 먼저 나오는 구조이다. 삽입이 일어나는 쪽을 뒤(Rear) 삭제가 일어나는 쪽을 (Front)라고 한다. 프린트 큐, CPU스케줄링, 데이터 버퍼, BFS 등에 사용된다. queue 만들기 #include //큐를 사용하기 위해 필요한 헤더 queue Q; //변수명 Q로 큐를 만듬 queue 변수 명 먼저 queue를 만들기 위해선 먼저 라는 헤더를 가져올 필요가 있다. 그리고 큐를 만들기 위해 queue 변수 명 을 사용한다. push f..

스택은 리스트의 일종으로 연산이 한 쪽 끝에서 이루어지는 자료구조다. LIFO (Last - In First -Out)구조 (가장 나중에 들어간게 가장 빨리 나오는 구조) 스택의 끝을 Top 시작을 Bottom 이라고 한다. stack 만들기 #include //스택을 사용하기 위해 필요한 헤더 stack st; // 스택 st를 만듬 stack 변수 명 먼저 스택을 사용하기 위해선 #include 가 필요하다. 그리고 스택을 만드는데 stack 변수 명 을 사용 할 필요가 있다. push for (int i = 0; i { 4, 3, 2, 1, 0} push는 스택에 ( )에 들어간 값을 넣을 수 있으며 값이 앞에서 ..

STL상에서 std::forward_list, std::list로 구현되어 있다. 선형리스트와 다르게 임의접근이 불가능하다. 읽기 연결리스트는 임의 접근이 불가능해 요소 하나하나를 탐색해야 되므로 읽는 시간이 오래걸린다. 검색 읽기와 마찬가지로 원소를 하나하나 비교하기에 시간이 걸린다. 선형 리스트와 다르게 이진 검색도 불가능 삽입 원소의 삽입 위치에 따라 시간이 달라진다. 앞이나 뒤에서 가까우면 짫고 중간이면 해당 위치까지 검색해야한다. 삭제 삽입과 마찬가지로 삭제 위치에 따라 시간이 달라진다. 이유역시 삽입과 똑같이 앞이나 뒤에서 가까우면 짫고 둥간이면 해당 위치까지 검색해서 길어진다. std::forward_list std::forward_list는 다음 원소로 만 이동할 수 있는 단일 연결 리스트..

시간 복잡도 실행 시간은 하드웨어와 소프트웨어의 환경에 따라 천차 만별이다. 그렇기에 소프트웨어와 하드웨어 환경을 배제한 객관적인 지표가 필요한데 이것이 시간 복잡도 이다. 시간 복잡도는 알고리즘 수행에 연산이 몇 번 수행되는지 숫자료 표기한다. 하나 연산하는데 t 만큼 시간이 들때 계산식 case 1 = 2t case 2 = (2n + 1) t case 3 = (2n² + 1) t 각각의 시간 복잡도를 계산 할 수 있다. 여기서 모든 계산에 걸리는 시간을 1ms 라고 정의했을때 표를 만들 수 있다. 입력 값(n) case 1(단위 : ms) case2(단위 : ms) case3(단위 : ms) 1 2 3 3 10 2 21 201 100 2 201 20,001 1000 2 2,001 2,000,001 1..

대부분 언어는 프로그래머의 편의를 위한 자료구조와 알고리즘을 제공한다. C++은 탬플릿을 이용해 지원하는데 이를 표준 템플릿 라이브러리(Standard Template Library)라고 한다. 임의 타입의 객체를 보관할 수 있는 컨테이너 라이브러리(Container Library) 컨테이너에 보관된 원소에 접근할 수 있는 반복자 라이브러리(Iterator Library) 반복자를 가지고 일련의 작업을 수행하는 알고리즘 라이브러리(Algorithm Library) 컨테이너는 자료구조의 구현체 반복자는 컨테이너의 요소에 접근할 수 있는 포인터 둘로 나뉘게 된 이유는 구현 코드의 개수를 줄이기 위함이다. 컨테이너의 개수를 N, 알고리즘의 개수를 M이라 한다면, 컨테이너 각각에 알고리즘을 구현할 때 필요한 구..

자료구조의 정의로는 데이터를 조직하는 방법이라고 할 수 있다. 자료구조는 여러 알고리즘대해 배우고 데이터에 적합한 알고리즘을 선택 할 수 있는 것을 목표로 한다. 자료구조는 기본 4가지 방법을 쓴다. - 읽기 : 자료구조 내 특정 위치를 찾아보는 것이다. - 검색 : 자료구조 내 특정 값을 찾는 것이다. - 삽입 : 자료구조에 새로운 값을 추가하는 것이다. - 삭제 : 자료구조 내 특정 값을 삭제하는 것이다.