블로그 검색

algoshipda의 블로그

확률문제

공유 링크 만들기
Facebook
Twitter
Pinterest
이메일
기타 앱

10월 17, 2015

PS일지

공유 링크 만들기
Facebook
Twitter
Pinterest
이메일
기타 앱

이 블로그의 인기 게시물

BOJ 11478 - 서로 다른 부분 문자열의 개수

5월 28, 2017

길이 $N$인 문자열 $S$의 서로 다른 부분 문자열의 개수를 세는 문제이다. 방법 1) Suffix Array + LCP $O(NlgN)$에 해결할 수 있다. 다른 곳에서 많이 볼 수 있는 풀이이다. 방법 2) 트라이 $O(N^2)$에 해결할 수 있다. 트라이에 $S$의 ${N(N + 1)} \over 2$개 부분 문자열을 모두 넣으면 최종적으로 트라이에 존재하는 노드의 수 - 1(루트 제외)이 답이 된다. 방법 3) 해싱 $O(N^2lgN)$에 해결할 수 있다. $S$의 ${N(N + 1)} \over 2$개 부분 문자열을 해싱하면서 유니크한 해싱값들의 수를 세면 된다. 코드 (트라이) : http://ideone.com/bugbDy 코드 (해싱) : http://ideone.com/hkjw5n

계속 읽기

repeated squaring

10월 05, 2015

https://www.acmicpc.net/problem/1533 최대 가중치 5인데 한 정점을 정점 다섯개로 치환하고 모든 간선의 가중치가 1인것처럼 만든다. 그런식으로 만든 인접행렬을 거듭제곱하면 답을 구할 수 있다. http://codeforces.com/problemset/problem/621/E

계속 읽기

Powered by Blogger

테마 이미지 제공: Michael Elkan

algoshipda

오현석

프로필로 이동

홈

글 보관함

2017 7
- 6월 1
- 5월 3
- 1월 3

2016 9
- 2월 8
- 1월 1
2015 33
- 12월 1
- 11월 2
- 10월 7
- 9월 5
- 8월 1
- 5월 6
- 4월 5
- 1월 6

자세히 보기 간략히 보기