Problem solving/Algorithm6 트라이 (Trie) 문자열을 효율적이게 저장하고 탐색하는 트리 형태의 자료구조 문자열의 문자 순서대로 자식노드를 생성하는 방식이다 구조 struct Trie { Trie *node[26]; Trie() { for (int i = 0; i < 26; i++) node[i] = NULL; } ~Trie() { for (int i = 0; i < 26; i++) { if (node[i]) { delete node[i]; } } } void insert(string &str, int idx) { if (idx == str.size()) return; // 문자열 끝까지 탐색 시 종료 if (node[str[idx] - 'a'] == NULL) node[str[idx] - 'a'] = new Trie(); // 해당 문자 노드가 없.. 2023. 8. 7. 문자열 검색 알고리즘 (KMP) 일반적으로 문자열에서 패턴을 검색한다고 할 때, 모든 경우를 검색해야 할 것이다. KMP (Knuth Morris Pratt) 알고리즘 모든 부분을 비교하지 않아도 부분 문자열을 찾을 수 있는 알고리즘 접두사와 접미사가 일치하는 최대 길이 찾기 일치하는 경우에는 점프할 수 있다 알고리즘 1. 패턴 문자열에 대해 접두사이면서 접미사인최대 문자열 개수 구하기 2. 문자열과 패턴을 비교하기 (위 : 문자열, 아래 : 패턴) 3. 다른 부분이 있다면 해당 위치에서 접두사와 접미사가 동일한 만큼 이동시킴 처음부분과 끝부분이 4개 동일하다는 것을 알고 있으므로 이동시킨만큼은 항상 같다 코드 1. 접두사 접미사가 일치하는 최대 길이 배열 구하기 // KMP 전통적인 방법 vector pi(pattern.size()).. 2023. 8. 4. 누적합과 구간합 알고리즘 배열에서 특정 구간의 합을 구할 때 시간 복잡도를 O(1)로 만들 수 있는 방법 누적합 배열에서 순차적으로 누적해서 합을 저장한다. 1차원 배열 1 2 3 4 5 1 3 6 10 15 for(int i = 1; i > S[i]; S[i] = S[i-1] + S[i]; } 2차원 배열 for (int i = 1; i S[i][j]; S[i][j] += S[i][j - 1] + S[i - 1][j] - S[i - 1][j - 1]; // 중복되는 부분을 한번 제거 } } 예를들어 14의 경우 6(왼쪽) + 3(위쪽) + 6(자신) - 1(대각선)으로 계산해서 나온 결과이다. 구간합 위에서 구한 누적합 배열을 바탕으로 구간합을 구할 수 있다. 1차원 배열 i에서 j까지 구간합 S[j] - S[i-1] 2차원 .. 2023. 7. 31. 위상 정렬 (Topology Sort) 그래프에 다양한 조건들이 얽혀있을 때, 조건에 부합하는 일직선의 경로를 찾는 알고리즘 특징 방향 그래프 여러개의 경로가 존재할 수 있음 사이클이 존재하지 않음 알고리즘 구조 진입 차수가 0인 정점을 모두 큐에 삽입하기 큐에서 정점을 꺼냄 꺼낸 순서가 위상정렬된 순서 꺼낸 정점과 연결된 간선의 진입 차수를 1씩 빼기 이후 다시 진입차수가 0이 된 정점을 큐에 삽입 만약, V번 반복하기 전에 큐가 비어있다면 사이클이 발생한 것임 // 인접 행렬과 진입 차수 초기화 vector adj(N + 1); vector inDegree(N + 1); for (int i = 0; i > A >> B; adj[A].push_back(B); inDegree[B]++; } // 진입 차수가 0인.. 2023. 7. 24. 이전 1 2 다음
