본문 바로가기

전체 글

 (774)
라빈-카프 [3033] [1. 문제 설명]https://www.acmicpc.net/problem/3033[2. 풀이 접근]완전 탐색으로 접근부분 문자열이 발생할 수 있는 대상은 아래와 같다.부분 문자열의 길이는 1 부터 L-1 까지길이 L-1 부터 발생 할 수 있는 모든 부분 문자열을 모두 확인하여 비교하는 방법라빈-카프 알고리즘 등을 이용하여 문자열 비교를 진행하더라도, O(L2) 의 시간 복잡도 발생이분 탐색으로 접근길이가 4인 부분 문자열이 2개 이상 존재한다고 했을 때,길이가 3인 부분 문자열의 존재는 굳이 확인하지 않아도 된다."ABCDE"FGH"ABCDE"XYZ=> ABCD 라는 중복 되는 부분 문자열이 있음을 바로 알 수 있다.즉, 중복 되는 부분 문자열이 있을 때, 그 보다 작은 길이의 부분 문자열의 중복 존재..
라빈-카프 알고리즘 [1. 개요] [2. 해시 함수 구현]해시 충돌을 최대한 적게 발생 시키게 하기 위해 K 와 mod 값을 선택해야 하는데두 값 모두 소수 (prime number) 로 선택하는 편이 좋다고 한다.K: 31, 53, 101, 127, 131, 137, ...mod: 1e9+7 과 같은 큰 수. (1e9+3, 1e9+9)# 십만자리 : 1e5+3# 백만자리 : 1e6+3특히 K 는 문자열의 상황에 따라 다른데,알파벳 소문자로 구성 된 경우 : 31, 127, 131, ...알파벳 대소문자 + 숫자 로 구성된 경우 : 53, 131, 911, ...그 외, 257, 997, 1009최소 31 부터 소수 인 값을 선택하면 좋음특히, 거듭제곱 등의 연산이 발생하기 때문에 overflow 에 유의하도록 한다.
wchar_t 사용에 관하여 [2] [1. 개요]멀티바이트 문자열에서 wide char 문자열로 변환 혹은 그 반대 방향으로 변환 시 주의 점.Locale 에 대한 이해인코딩 변경이므로, 데이터 인코딩이 적절한지 확인출력에 관하여.[2. Locale 에 대한 이해]리눅스 기준으로는locale -a 를 이용하여, 현재 시스템에 설치된 locale 을 확인 할 수 있다.# locale-gen ko_KR.UTF-8 을 이용해서 한국어 관련 locale 을 설치 할 수 있다.윈도우에서 파워 쉘 기준으로는Get-WinSystemLocale 명령어로 확인 가능[3. 리눅스 관련 코드]#include #include #include #include #include int main(){ wchar_t wstr[128]; std:..

티스토리툴바