문자열 처리 알고리즘 - LCP

LCP (Longest Common Prefix) 문자열이 하나만 주어졌을때 공통된 문자열(substring; subsequence가 아님)의 최대 길이가 얼마인지 구해야 하는 문제가 주어졌다고 하자. 이 때 이 문자열에 대한 Suffix Array를 구해놨다면 O(N)에 문제에 대한 답을 구할 수 있다. 그럼 이 부분을 KMP로 구할 수 있을까? 안된다. Needle에 대한 스트링이 O(N^2)개 만큼 존재하는데, 이걸 모두 비교하려면 O(N^3)이 걸릴 것이다. 그래서 나온 방법이 SA를 구한 상태에서 LCP를 O(N)에 구하는 방법이다. (이전에 내가 올린 포스팅에서 Suffix Array를 O(NlogN)에 구할 수 있는 방법만 소개하였으나 O(N)에 구할 수도 있다. 그러면 SA구하고 LCP까지..
Algorithm/String 8년 전

문자열 처리 알고리즘 - Suffix Array

해당 posting은 다시 작성되었습니다. 새글 보러 가기: http://plzrun.tistory.com/entry/Suffix-Array-ONlogNlgN과-ONlogN-구현-및-설명 Suffix Array (접미사 배열) 만약 suffix array에서 1,2,4,8 이런식으로 건너뛰면서 소팅하는 것 자체가 이해가 안됐다면, https://algospot.com/forum/read/2779/#c12715 여기 갓 설명글이 있다. 이 글 읽으면 무조건 이해가 될 것이다. 나도 여기서 막혔었고, 종만북 보면 이 문자열 파트 부분 설명이 상당히 좋지 않기 때문에 대부분 여기서 헤맨다.
Algorithm/String 8년 전

문자열 처리 알고리즘 - KMP

문자열 처리 알고리즘 나름 블로그의 모양새를 갖추기 위해 오늘부터 문자열처리 알고리즘에 대해 작성해보려고 한다. ㅋㅋ 1. KMP Algorithm 어떤 문자열(H)에서 내가 찾고자 하는 문자열(N)이 있는지 확인하려면 어떻게 해야할까? H와 N을 하나하나씩 비교하다가 match되지 않는 부분이 나오면 N 문자열을 통째로 한칸 이동해서 다시 처음부터 비교하면 될 것이다. 그럼 시간복잡도는 … ㄷㄷㄷ H와 N이 10만씩 주어지면 100억이나 된다. Tip: H는 Hay의 약자, N은 Needle의 약자이다. 건초더미에서 바늘찾는다고 생각하면 된다. ㅋ 그럼 어떻게 할까? 이 문제를 만에 해결하는 방법이 있으니 그게 바로 KMP 알고리즘이다. 근데 이게 처음 코드만 보면 사실 뭐하는건지도 모르겠고, 설명들어..
Algorithm/String 8년 전

최대공약수 (GCD: Greatest Common Divisor)

123456789#include using namespace std;long long gcd(long long b, long long s) { return s?gcd(s,b%s):b; }int main() { long long x,y; scanf("%lld%lld",&x,&y); printf("%lld",gcd(x,y)); return 0;}Colored by Color Scriptercs 처음 ps를 배울 때 gcd구하는 법도 몰랐다. 뭔가 이런 코드를 보고 엄청 감동받았던 적이 있었는데 ㅋㅋ 지금 생각해보면 참 안타까운 시절이었다. 설명은 없다. 어차피 자세한 설명은 구글에 널렸다. ㅋ 가서 찾아보시길...
Algorithm/String 8년 전

8217 유성 (Meteors)

유성 (8217 Meteors) https://www.acmicpc.net/problem/8217 (BOJ Meteors) http://www.spoj.com/problems/METEORS (SPOJ Meteors) http://codeforces.com/blog/entry/45578 (Codeforces parellel binary search tutorial) 블로그 만든 기념으로 최근에(거의 한달 전인 것 같지만) 풀었던 문제중 꽤 난이도가 있었던 문제를 올려본다. ㅎ 이 문제 번역도 내가했다 ㅋㅋ 번역글 도저히 못보겠다 생각되면 원문을 보시길 바랍니다. (ㅈㅅㅈㅅ) parallel binary search(pbs) 알고리즘으로 푸는 가장 대표적인 문제인 것 같다. 코드포스 가서 pbs검색해보면 제..
PS - OJ/BOJ 8년 전

아스가르드 다시 하고 싶다~

요즘 부쩍 아스가르드가 다시 하고 싶어졌다. 3년 정도 아무런 업데이트도 없고 일본 아스마저도 서비스를 종료하면서 한국 아스도 조만간 사라질 것 같았는데, 이번에 어둠의전설과 같이 업데이트를 한다는 소식이 들려왔다. 요즘 또 계속 아스인 사이트와 아스가르드 컴퍼니 사이트를 눈팅중인데... 정말 하고 싶긴한데, 일단 내가 밥 벌어먹을 수단( = 개발 능력 )이 너무 허접해서 그것부터 해야할 듯 싶다. ㅠㅜ
Hobby/Asgard 8년 전

2016.11.16

삼성전자 DS 면접 합격 전, 그리고 그 후. 현재시각 18:11 벌써 11월의 반이 지나갔다. 아까 집에 4시쯤 돌아와서 점심을 먹으며 평소와 같이 TV를 켰다. 이전에 2번 정도 봤던 '리미트리스'라는 영화가 또 나오고 있었다. 아마 2014년 다이어리인가? 거기에도 이 영화를 언급했던 적이 있었던 것 같은데.. 아무튼 지금 내겐 그 약이 필요하다. NZT? 약 이름이 벌써 기억이 안나네... 딱 10년만 살아도 정말 그렇게 살고 싶다. 사실 내가 멍청한건 아닌데, 아니.. 아니라고 생각했는데 올해 초 PS를 시작하면서 깨달았다. 내 머리는 평균이하구나... 어렸을 때 조금 똑똑해 보였던건 남들보다 성장속도가 빨라서 그래 보였던 거였다. 조금 형편이 괜찮은 집안에서 태어나 정말 조금 먼저 배워서, 그..
Diary/2016 8년 전