본문 바로가기

자료구조

 (11)
연결리스트(양방향,head 및 tail에 데이터추가) //양방향에,헤드에 추가 /* 양방향 연결리스트 기능 장점:탐색 양방향 가능 단점:메모리 더많이사용, 구현 복잡 */ #include using namespace std; struct Node { int data; Node *prev; Node *next; }; struct Linkedlist { Node *dummy; //헤드에 추가할때 ->순서가 그닥 필요하지 않을때 Node *tail; //꼬리에 추가할때 -> 연결리스트에 순서가 필요한경우 int len = 0; Linkedlist() //생성자 { dummy = (Node*)malloc(sizeof(Node)); dummy->data = -1; dummy->prev = NULL; dummy->next = NULL; tail = dummy; //같..
TREE (연결리스트) #include using namespace std; //노드생성 class Node //원하는 데이터 선언, 노드생성할때마다 포인터들 초기화 { public: char data; Node *parent; Node *brother; Node *child; Node() {} Node(char data) :data(data), parent(0), brother(0), child(0) {} ~Node() { parent = NULL; brother = NULL; child = NULL; } }; //탐색함수 Node* searchNode(Node *R, char pid) // 루트부터 탐색, 트리의 크기가 클경우에 매번 루트부터 탐색하면 호출횟수가 많아진다는 단점이있다. { } // 추가함수 void Inse..
트라이(Trie) 자료구조 Base. 트리 =>트리는 노드(node)와 에지(edge)로 구성되는 계층관계를 나타내는 자료구조 1.트라이(trie) =>트라이는 retrieval tree에서 나온 단어 =>문자열을 key로 사용하는 동적인 연관배열을 저장하는 트리의 확장된 자료구조 =>사용되는 곳은 Google의 dictionary, Excel의 Filtering 기능 https://brunch.co.kr/@springboot/75 트라이(Trie) 자료구조 - 문자열 검색을 위한, 트라이(Trie) 자료구조 기본 스터디 | 문자열을 저장하는 자료구조에서, 가장 효율적인 문자열 검색 알고리즘은 무엇일까? 가장 단순한 방법은 하나하나 찾아서 비교할 수 있지만 매우 비효율적인 방법이다. 문자열 검색에 좋은 알고리즘이 바로 "Trie"..
HASH(해쉬) ##해시테이블의 장점 해시충돌이 발생할 가능성이 있음에도 해시테이블을 쓰는 이유는 적은 리소스로 많은 데이터를 효율적으로 관리하기 위해서입니다. 예컨대 해시함수로 하드디스크나 클라우드에 존재하는 무한에 가까운 데이터(키)들을 유한한 개수의 해시값으로 매핑함으로써 작은 크기의 캐쉬 메모리로도 프로세스를 관리할 수 있게 됩니다. 색인(index)에 해시값을 사용함으로써 모든 데이터를 살피지 않아도 검색과 삽입/삭제를 빠르게 수행할 수 있습니다. 위 그림의 경우 해시함수에 ‘Lisa Smith’를 입력하면 02라는 색인이 생성됩니다. 해시함수는 언제나 동일한 해시값을 리턴하고, 해당 색인만 알면 해시테이블의 크기에 상관없이 데이터에 대단히 빠르게 접근할 수 있으며, 색인은 계산이 간단한 함수(상수시간)로 작동..
연결리스트[큐] 큐를 연결리스트로 구현해보자 기본문제를 통해 구현해봅시다~ 연결리스트에 대한 강의를 듣고 구현해보는 것을 추천합니다 https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다. www.acmicpc.net //리스트 //기본적인연산:삽입,삭제,검색 등 //리스트를 구현하는 방법:배열,연결 //배열단점: 크기가 고정, 중간에 데이터 삽입 및 삭제하려면 다수의 데이터를 옮겨얗ㅁ //연결리스트:길이 제한 없음, 다른 데이터의 이동없이 중간..
정렬 총 정리 //삽입정렬, 선택 정렬, 버블 정렬, 병합정렬, 퀵정렬,힙정렬,기수정렬,위상정렬 #include using namespace std; //선택정렬 -하나를 기준으로두고, 그외 나머지에서 우선순위 있는 것을 고른다. //시간복잡도 O(n^2) void selectSort(int *arr, int size) { for (int i = 0; i arr[j])temp = j; } swap(arr[i], arr[temp]); } } //버블정렬-서로 이웃한 데이터들을 비교하며 큰데이터를 가장 뒤로 보내 정렬하는방식(오름차순기준) //시간복잡도 O(n^2) vo..
Tree [TREE의 조건] 1) 연결 그래프이다2) 방향무시하였을때, 싸이클이 존재하지 않는다.3) 트리의 간선 개수는 트리의 정점 개수보다 1작다. TREE를 구현 할때 중요한 것은? - 트리는 재귀적인 구조를 띈다.(DP나 분할 정복의 기법과 굉장히 잘 맞다)-어떤 정점의 서브트리들은 서로 절대영역이 겹치지 않기때문에 각 서브트리에 대한 문제를 풀어 합치면 큰 트리의 문제를 풀 수 있다.(DP 및 분할 정복 ) [TREE의 순회] 1)전위 순회- 모든 정점에 대해서 자기자신을 먼저 방문한 후에 자식들을 방문 (DFS의 성향이 더 강함) 2)중위 순회-자식들 중간에 루트를 방문하는 순회, 왼쪽자식->루트->오른쪽 자식 순서 (차수가 최대 2인 트리에서 주로 사용된다.) 3)후위 순회- 자식들을 모두 방문하고서..
SORT종류2 복잡하지만 효율적인 정렬알고리즘 1.힙정렬 :힙의 특성을 활용하여 정렬하는 알고리즘 :힙의 루트 노드에 저장된 값이 가장 커야한다. :힙 관련 포스트 이용해서 자세하게 2.병합정렬 =>병합정렬은 데이터가 1개만 남을때까지 분할을 한다. 그리고 실제 정렬은 나눈것을 병합하는 과정에서 이루어진다. *성능 평가 :비교연산과 이동연산이 실제 정렬을 진행하는 Mearge TwoArea함수 중심으로 진행된다. :그래서 Mearge TwoArea 기준으로 시간복잡도를 계산해야한다. :정렬의 우선순위를 비교하는 비교연산이 중심이므로, 비교연산 횟수를 계산한다. 데이터수가 8개일때 병합의 과정은 3회 진행되었다. 마찬가지로 데이터수가 16개일때 병합의 과정은 4회 진행된다. 즉 데이터 수 n과 그에 따른 병합과정의 횟수..

티스토리툴바