BOJ27 Trie 자료구조 길이 L 짜리 문자열이 N개 담긴 list 에서 특정 문자열을 검색하는 시간복잡도가 어떻게될까? 이진탐색을 쓴다면 O(log N) 처럼 보이지만, 두 문자열을 비교하는 strcmp 함수의 시간복잡도가 O(L) 이기에, 전체 시간복잡도는 O(L log N) 이 된다. 심지어 list 가 정렬되어 있어야 한다. Trie 를 쓴다면, O(NL) 의 시간복잡도로 전처리를 하게 된다. 이후에는 어떤 문자열이 오더라도 O(L) 만에 list 에서 검색이 가능하다. BOJ 5670 휴대폰 자판을 예시로 들어보자. hell, hello, heaven, goodbye 4개의 문자열이 들어온다. hell 이 먼저 들어오니까 이 때의 Trie 를 그림으로 확인해보자. 0. 초기 상태 Trie의 초기 상태. 루트 노드만 존재.. 2022. 8. 24. KMP 알고리즘 : 문자열 검색 문자열을 검색하는 KMP 알고리즘은 Failure Function 에 대한 이해가 필수다. Failure Function 길이 N 짜리 문자열에서 길이 M의 문자열을 검색하는 작업을 O(N+M)에 하는 KMP 알고리즘을 이해하려면, 우선 Failure Function (실패 함수) 를 이해해야 한다. 이 글에서는 Failure Function 에 관한 내용만 daisylum.tistory.com 들어가기 전에, Failure Function 을 포함하여 이 글은 1-based index 를 기반으로 한다. 즉 모든 문자열은 배열의 1번 인덱스부터 담겨 있다고 가정한다. 문제 상황은 다음과 같다. 문자열 Str 에서 문자열 Want 가 나타나는 위치를 모두 파악할 수 있을까? Str 의 길이를 S, Wan.. 2022. 8. 19. Failure Function 길이 N 짜리 문자열에서 길이 M의 문자열을 검색하는 작업을 O(N+M)에 하는 KMP 알고리즘을 이해하려면, 우선 Failure Function (실패 함수) 를 이해해야 한다. 이 글에서는 Failure Function 에 관한 내용만 작성한다. 길이가 Len 인 문자열 S가 존재한다고 하자. 이 때 S의 index는 1-based 이다. 즉 S[1] ~ S[Len] 까지 문자가 있다. (개인적으로 이 알고리즘은 1-based가 더 직관적으로 이해하기 좋다고 생각한다.) Failure Function의 정의 1 ~ Len 범위의 수 i 에 대해 F(i) 를 아래와 같이 정의한다. F(i) := S[1...i] 에서 앞쪽 K자리의 문자열과 뒤쪽 K자리의 문자열이 일치하는 가장 큰 K (자기 자신은 제외.. 2022. 8. 19. BOJ 1733 : 등번호 문제 링크 : https://www.acmicpc.net/problem/1733 N명의 사람이 앞 뒤에 숫자가 적힌 유니폼을 갖고 있다. 각자 앞 또는 뒤에 적힌 숫자를 골라 N명의 사람이 고른 숫자가 겹치지 않게 하는 해를 출력하면 되는 문제다. 처음에 문제를 보자마자 든 생각은 이게 왜 플레1 이나 하지? 였다. 그냥 이분매칭인데, 단순한 이분매칭은 플레4~5 이기 때문이다. 하지만 N 제한이 100만인 것을 알고 납득했다. 혹시 새로운 이분매칭 알고리즘을 배워야만 하나? 하고 검색하니 Hopcroft - Karp 가 있긴 했다. 그래도 O(N 루트 N) 이라 시간초과 뜰 것 같아 다른 해법을 고민하기 시작했다. 약간의 관찰을 통해 그래프 탐색 느낌이 난다는 것을 알게 되었다. 예를 들어 1번 학생이.. 2022. 8. 16. BOJ 1211 : 보일의 법칙 문제 링크 : https://www.acmicpc.net/problem/1211 BOJ 24970 처럼 내가 좋아하는 digit DP 문제. 자기곱 := (자신) * (자신의 각 자리 숫자의 곱) 으로 정의한다. 예를 들어 24 의 자기곱은 24 * 2 * 4 = 192 이다. 1018 미만의 두 수 A, B가 주어졌을 때, 자기곱이 A 이상 B 이하인 숫자의 개수를 출력하면 된다. 우선 나는 F(N) := 자기곱이 N 이하인 숫자의 개수로 정의했다. 그렇게 된다면 답은 F(B) - F(A-1) 이 될 것이다. 이제 F(N)을 구하는 방법만 생각하면 된다. 나는 백트랙킹을 했는데, Naive 하게 돌아봐도 시간초과가 나지 않기 때문이다. 물론 1 ~ N 까지의 자기곱을 다 구한다는 소리가 아니고, 수를 .. 2022. 8. 15. BOJ 24970 : 균형 수 문제 링크 : https://www.acmicpc.net/problem/24970 "균형 수"란, (앞쪽 절반의 각 자리 수 합) = (뒤쪽 절반의 각 자리 수 합) 이 되는 수를 말한다. 예를 들어 13504, 2415 가 균형수라고 할 수 있다. T(n) := n 자리의 균형수들의 총 합일때, T(1) + T(2) + ... + T(N) 을 315 으로 나눈 나머지를 구하면 된다. (N은 100 이하) 내가 좋아하는 유형의 DP 문제인데, 처음 생각한 것은 d[i][j], s[i][j] 두 개를 정의하는 것이었다. d[i][j] = 맨 앞에 0이 와도 되며, 각 자리 수의 합이 j 가 되는 i 자리 수의 개수 s[i][j] = 맨 앞에 0이 와도 되며, 각 자리 수의 합이 j 가 되는 i 자리 수의 .. 2022. 8. 15. 이전 1 2 3 4 5 다음
