본문 바로가기

전체 글

 (121)
트라이(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 //리스트 //기본적인연산:삽입,삭제,검색 등 //리스트를 구현하는 방법:배열,연결 //배열단점: 크기가 고정, 중간에 데이터 삽입 및 삭제하려면 다수의 데이터를 옮겨얗ㅁ //연결리스트:길이 제한 없음, 다른 데이터의 이동없이 중간..
[백준 2252]줄세우기 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다. 학생들의 번호는 1번부터 N번이다. www.acmicpc.net https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다. 학생들의..
정렬 총 정리 //삽입정렬, 선택 정렬, 버블 정렬, 병합정렬, 퀵정렬,힙정렬,기수정렬,위상정렬 #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..
위상정렬 출처:https://www.youtube.com/watch?v=qzfeVeajuyc //위상정렬-순서가 정해져있는 작업, 차례로 수행해야하는 작업을 수행해야할떼 그 순서를 결정해주기위해 사용하는 알고리즘 //사이클이 발생하지 않는 방향그래프에서 작업 //사이클이 발생하면 위상정렬을 수행하지 못한다. //위상정렬이 가능한지 //위상정렬이 가능하다면 그 결과는 무엇인지 //수행방식->스택 및 큐가 있는데 큐를 더 선호 //진입차수- 현재 노드에 들어오는 간선 개수 //1.진입차수가 0인 정점을 큐에 삽입 //2.큐에서 원소를 꺼내 연결된 모든 간선을 제거 //3.간선 제거 이후에 진입차수가 0이 된 정점을 큐에 다시 삽입 //4.큐가빌때까지 2번~3번과정을 반복 //단, 모든 원소를 방문하기전에 큐가 빈다면..
[백준 16437]양 구출 작전 문제 https://www.acmicpc.net/problem/16437 1)문제 분류-트리 2)문제 해결- 재귀로 후위순회 방법으로 구현한다. #include #includeusing namespace std;int N;vectorvt[123458];typedef struct Data{char T;long long int Cnt;}Data;Data arr[123458];long long int dfs(int idx){long long int sum = 0;for (int i = 0; i < vt[idx].size(); i++){sum += dfs(vt[idx][i]);}if (arr[idx].T == 'S')return arr[idx].Cnt + sum;elsereturn (sum - arr[idx]...
[백준 1068]트리 문제: https://www.acmicpc.net/problem/1068 1) 문제분류-트리 2)문제 해결- vector에 부모노드에 연결되어있는 자식노드들을 담아 연결을 시킨다.- DFS를 통해서 모든 리프노드를 조사를 하는데, 제거할 노드를 만났을때 return 함으로써 그 부분만 탐색을 안하면 된다.- DFS로 탐색을 할때에는 해당노드의 자식노드들의 개수가 0개라면 Leaf노드이므로 개수를 세어준다. #include #include using namespace std; vector tree[51];int n,root,ans, x;void search(int cur) {if (cur == x) return;int ok = 0;for (int i = 0; i < tree[cur].size();i++){..

티스토리툴바