c++33 레드-블랙 트리(Red_Black_Tree) 레드-블랙 트리 레드 블랙 트리는 자가 균형 이진 탐색 트리입니다. 탐색(Search) 연산의 시간 복잡도 O(logN) 레드 블랙 트리는 아래의 조건을 항상 만족해야 합니다. 1. 루트 노드는 블랙이다. 2. 모든 리프 노드는 블랙이다. 3. 노드가 레드이면 그 노드의 자식은 반드시 블랙이다. (No Double Red) 4. 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다 노드 삽입 과정 노드의 삽입은 항상 빨간색 단 루트노드 제외 첫 번째 노드 삽입 (루트 노드는 항상 블랙 노드) 2, 8 노드 삽입 노드 삽입은 항상 빨간색 3 노드 삽입 3번 조건 위배되는 상황 발생 (Double Red) 이중 레드 (Double Red) 문제 해결 Restructuring .. c++/자료구조 간단 이론 2023. 5. 31. 이분 탐색 이분 탐색이란? - 정렬된 배열에서 원하는 값의 존재 여부를 찾는 알고리즘. - 반드시 배열을 정렬해서 사용해야 한다는 단점이 있다. - 탐색할 때마다 검사 범위가 절반으로 줄어든다. 시간복잡도 : O(log N) 탐색 방식 - 전체 배열의 중간 요소를 찾고자 하는 키로 시작합니다. - 찾고자 하는 키의 값이 항목과 같으면 찾고자 하는 키의 인덱스를 반환합니다. - 또는 찾고자 하는키의 값이 Mid보다 작으면 End = Mid - 1으로 좁힙니다. - 그렇지 않으면 Start = Mid + 1으로 좁힙니다. - 두 번째 지점부터 값을 찾거나 간격이 비어 있을 때까지 반복적으로 확인합니다. 출처 : https://www.geeksforgeeks.org/binary-search/ Binary Search -.. c++/자료구조 간단 이론 2022. 11. 3. deque 정의 및 시간복잡도 deque 정의 앞, 뒤 전부 삽입 삭제가 가능함 Restricted Structure 시퀀스 컨테이너이자, 배열 기반 컨테이너입니다 시간복잡도 1. 원소의 추가O(1) 2. 원소의 제거O(1) 3. 제일 앞/뒤의 원소 확인O(1) 4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 (단, stl deque에는 인덱스로 접근이 가능함) c++/자료구조 간단 이론 2022. 8. 23. Stack 간단 정의, 시간복잡도 Stack 정의 스택은 대표적인 후입선출(LIFO) 방식의 자료 구조입니다. 가장 나중에 저장된 데이터가 가장 먼저 제거되는 구조입니다. 기본 함수로는 push, pop, empty, top, size이 있습니다 후입선출(LIFO) : Last In First Out 컨테이너 Stack는 컨테이너 어뎁터이다. 어뎁터 컨테이너는 다른 컨테이너 클래스들을 상속 받아서 다른 컨테이터 클래스의 객체에 특정한 인터페이스를 제공해주는 개념이다. 단, 반복자를 지원하지 않으므로 STL 알고리즘에서는 사용할 수 없다. 시간복잡도 1. 원소의 추가O(1) 2. 원소의 제거O(1) 3. 제일 상단의 원소 확인O(1) 4. 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 c++/자료구조 간단 이론 2022. 8. 23. List 간단 정의 성질 및 종류 list : 노드형 시퀀스 컨테이너 연결 리스트의 성질 1. K번째 원소를 확인/변경하기 위해 O(k)가 필요함 2. 임의의 위치에 원소를 추가/임의 위치의 원소 제거는 O(1) 3. 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움 연결 리스트 종류 1. 단일 연결 리스트(Singly Linked List) 2. 이중 연결 리스트(Doubly Linked List) 3. 원형 연결 리스트(Circular Linked List) 배열 vs 리스트 배열 리스트 k번째 원소의 접근 O(1) O(k) 임의 위치에 원소 추가 / 제거 O(N) O(1) 메모리 상의 배치 연속 불연속 추가적으로 필요한 공간 (Overhead) - O(N) c++/자료구조 간단 이론 2022. 8. 23. queue간단 정의, 성질 queue정의 큐는 대표적인 선입선출(FIFO) 방식의 자료 구조입니다. 가장 처음에 저장된 데이터가 가장 먼저 제거되는 구조입니다. 기본 함수로는 push, pop, front, back, empty, size이 있습니다 선입 선출구조 FIFO(First In First Out) 컨테이너 queue는 컨테이너 어뎁터이다. 어뎁터 컨테이너는 다른 컨테이너 클래스들을 상속 받아서 다른 컨테이터 클래스의 객체에 특정한 인터페이스를 제공해주는 개념이다. 단, 반복자를 지원하지 않으므로 STL 알고리즘에서는 사용할 수 없다. 시간 복잡도 1. 원소의 추가 O(1) 2. 원소의 제거O(1) 3. 제일 앞/뒤의 원소 확인O(1) 4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 c++/자료구조 간단 이론 2022. 8. 23. 20210813 파일 입출력 안녕하세요 틴구입니다 "오늘은 파일 입출력을 설명 해보도록 할게요" 파일 입출력 하드디스크에 파일을 만들거나 있는 파일의 데이터를 얻어올때 사용합니다 언어마다의 방식 c언어 방식 : fopen 함수를 사용하여 처리한다. c++ 방식 : ifstream, ofstream을 사용하여 처리한다. 오늘은 c언어 방식인 fopen을 사용할 것입니다. ex) text파일 입,출력 fopen_s의 인자 종류 1번인자 : 파일 스트림 2번인자 : 파일 명이 들어가고 3번 인자에는 Mode가 들어간다. Mode 종류 r : 파일을 읽어온다. w : 파일을 만든다. a : 파일에 접근하여 이어쓰기를 한다. r+ : 파일이 존재하면 해당 파일을 읽고 쓰기 가능하게 연다. 파일이 없으면 에러를 반환한다. w+ : 파일이 존재.. c++ 2021. 8. 14. 20210812 class 상속 안녕하세요 틴구입니다. "오늘 올릴 내용은 뭐냐 class 상속에 대한 기초 개념과 이론입니다." 1.클래스 상속 클래스 상속이란 기존에 있는 클래스의 멤버 변수와 멤버 함수를 물려받아 새로운 클래스를 작성하는 것을 의미합니다.클래스는 부모의 or 자식의 관계를 형성할 수 있습니다. 상속관계에서의 생성자와 소멸자 호출 순서 생성자 : 부모 -> 자식 소멸자 : 자식 -> 부모 ex) 위의 코드처럼 구성을 하였을 경우 호출 순서에 의해 아래처럼 출력이 됩니다. 클래스 상속의 장점 기존의 클래스를 재활용할 수 있습니다.즉 부모클래스에 공통으로 가져야 할 멤버변수를 선언하고 공통으로 가져야 할 기능을 멤버함수로 만들어준 후에 개별적인 내용들만 자식클래스에 따로 조금씩 만들어서 하나의 객체를 만들때 사용합니다... c++ 2021. 8. 13. 20210811 Hashtable 안녕하세요 틴구입니다 오늘은 Hashtable이라는 것에 대해서 적어보려고 합니다. 1.Hashtable Hash Table: 키에 대한 데이터를 저장하는 데이터 구조이고 키만 알면 데이터가 어디에 저장되어있는지 알 수 있는 데이터 구조입니다. 장점 : 데이터 저장/읽기 속도가 빠릅니다. (검색에서 배열보다 해쉬 테이블 구조가 더 빠르다) 검색에서 배열보다 해쉬테이블 구조가 좋은 이유 배열 : index별로 일일이 검색해야, index를 순차적으로 검색할 때 찾고자 하는 데이터가 배열의 마지막 인덱스에 값인 경우 시간이 오래 걸립니다. 해쉬 테이블 : 데이터를 받고 그에 해당하는 키를 찾으면 해쉬 함수를 한 번만 돌리면 바로 그 데이터 저장 위치를 해쉬 테이블에서 찾을 수 있습니다. 키에 대한 해쉬 값이.. c++/자료구조 2021. 8. 12. 20210810 Dijkstra(다익스트라) 알고리즘 안녕하세요 틴구입니다 이번 글은 Dijkstra 알고리즘에 관한 설명입니다 1.Dijkstra 정의 a정점과 b점점 사이의 최단 경로를 찾는 데이크스트라의 알고리즘입니다. 가장 낮은 값을 가진 방문하지 않은 꼭짓점을 선택하고, 방문하지 않은 각 인접 노드와의 거리(가중치)를 계산하고, 작을 경우 인접 거리를 업데이트하는 개념입니다. 단, 음의 가중치가 없는 그래프여야 하고, 방향 그래프, 무방향 그래프 모두 상관없습니다. 2. 이론 설명 위와 같이 1번부터 5번까지의 노드가 있고 그를 연결해주는 엣지와 엣지의 가중치값(Cost)이 있다고 가정을 한다. 이때 처음 시작지점인 1번 노드의 시작 값은 0으로 지정해둔다 여기서 1번에서 4번까지 가는 최단 루트를 구한다고 가정을 했을 때 1번 노드에서 연결되는 .. c++/자료구조 2021. 8. 11. 20210810 Graph알고리즘 안녕하세요 틴구입니다. 안녕하세요 오늘은 자료구조 Graph에 관해서 설명을 해드리려고합니다. 1. Graph란 그래프는 정점과 간선으로 이루어진 자료구조입니다. 그래프를 구현하는 방법에는 인접행렬와 인접리스트방법이 있는데 저 같은 경우는 인접리스트방법으로 구현하도록 하겠습니다. Graph에는 두가지의 종류가있는데 방향성 그래프와 무방향 그래프입니다(배운 가지수가 두가지) 방향성 그래프란 : 방향 그래프는 두 정점을 연결하는 간선에 방향이 존재하는 그래프입니다. 방향 그래프는 그 간선의 방향대로 움직일 수 있습니다. Graph에는 탐색방법이 두가지의 종류가 있습니다 그래프 탐색의 방법은 깊이 우선 탐색(DFS) 방식과 너비 우선 탐색(BFS)방식이 있습니다. 깊이우선 탐색(DFS) : 갈 수 있는 정점까.. c++/자료구조 2021. 8. 11. 20210810 병합정렬(합병정렬) 안녕하세요 틴구입니다. 오늘은 병합정렬에 대해서 설명드리려고 해요~ 병합정렬이란 : 합병 정렬(merge sort)은 하나의 배열을 두 개의 균등한 크기로 분할하고 각 분할된 배열을 정렬한 다음, 두 개의 정렬된 부분 배열을 합하여 전체가 정렬된 배열을 얻고자 하는 것이다. 3, 5, 2, 6, 4, 1, 7, 8 의 배열이 구성되어 있다고 하면 3, 5, 2, 6 | 4, 1, 7, 8 3, 5 | 2, 6 | 4, 1 | 7, 8 3 | 5 | 2 | 6 | 4 | 1 | 7 | 8 이렇게 나뉜다음 돌아가면서 정렬을 이루는 형식입니다 3, 5 | 2, 6 | 1, 4 | 7, 8 2, 3, 5, 6 | 1, 4, 7, 8 1, 2, 3, 4, 5, 6, 7, 8 이런 식으로 요 원리를 알았으니깐 코드.. c++/자료구조 2021. 8. 10. 이전 1 2 3 다음
