dh_0e

트라이(Trie)여러 개의 문자열을 효율적으로 저장, 탐색 및 삭제 할 수 있는 자료구조 Retrieval tree에서 "Trie"를 도출한 이름사전 순 정렬이 자동으로 되며, 해시 충돌이 없기 때문에 해시 테이블보다 stable함자동 완성(검색어 추천 기능), 사전 구현, 문자열 패턴 매칭 등에서 사용됨  구조트라이는 루트 노드(root node)를 가지고 있으며, 각 노드는 알파벳(혹은 문자)별로 자식 노드를 가질 수 있음finish(또는 isEndOfWord) 변수를 두어 문자열의 끝을 나타냄(root) ├── C │ ├── A │ │ ├── T (finish=true) │ │ ├── N (finish=true) 위 예제에선 "CAT"과 "CAN"이 저장되어 있으며, T와 ..

자료구조 트라이(Trie) 기초 문제로 해시 테이블을 사용해서 풀 수도 있는 문제 Trie를 문제에 맞게 구현해주면 쉽게 풀 수 있다.insert 도중 finish가 true면 일관성 Xinsert가 끝난 후 finish에 true 값을 저장하려는데 number 배열이 비어있지 않으면 일관성 X  #include#include#includeusing namespace std;struct Trie { bool finish; Trie* number[10]; Trie() :finish(false) { memset(number, 0, sizeof(number)); } ~Trie() { for (int i = 0; i insert(key + 1); }};int main(){ int t; scanf("%d", ..

memset메모리의 특정 영역을 지정된 값으로 초기화하는 함수주로 배열이나 구조체의 초기화에 사용 헤더에 포함#include #include int main() { char str[50] = "Hello, world!"; printf("Before memset: %s\n", str); // Before memset: Hello, world! // str 7번째 값부터 5개의 바이트를 'X'로 설정 memset(str + 7, 'X', 5); printf("After memset: %s\n", str); // After memset: Hello, xxxxx! return 0;}  isupper / islower문자가 대문자인지 소문자인지 여부를 판별하는 함수 헤더에 ..

그래프 탐색에 대한 이해도만 있으면 쉽게 풀 수 있는 문제대게 bfs로 풀었던데 귀찮아서 dfs로 풀었다.각 열쇠마다 열지 못한 문의 좌표를 저장하는 벡터를 만든 다음, 새로운 열쇠가 나왔을 때 벡터에 저장되어 있는 열지 못했던 문을 다시 탐색하는 방식으로 구현하여  풀었다. #include#include#include#include #includeusing namespace std;char d[101][101];bool vi[101][101], key[27];int doc = 0, x_size, y_size;vector > blocked[27];int f(int x, int y) { if (d[y][x] == '*')return 0; else if (d[y][x] == '$')doc++; else i..

간단한 그래프 탐색 문제로 dfs 구현만 잘하면 쉽게 푸는 문제visit 체크를 해주는 배열에 각 학생들의 상태를 4개로 분리하였다. 아래 코드 기준으로 vi[] 배열에 저장된 학생들의 상태는-1) cycle을 탐색했지만 팀에 들어가지 못한 상태 0) 아직 cycle을 찾아보지 않은 상태 1) cycle을 찾아 팀에 들어간 상태 2) cycle을 찾는 중인 상태로 cycle을 탐색하다 next 학생의 vi에 저장된 값이 2(cycle을 찾는 중인 상태)라면 cycle이 완성된 것이므로 next 값을 return 하여 next 학생이 나올 때 까지의 학생들의 상태를 1로 바꿔주고, next 학생이 나오면 그 다음 학생부턴 0 값을 return 하여 상태를 -1로 바꿔주었다. dfs 풀이#include#in..