LIS에 대해 알아보자
LIS LIS(Longest Increasing Subsequence) : 최장 증가 부분 수열 수열 하나가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구할 때 3가지 방법이 있다.
LCS에 대해 알아보자
LCS LCS는 두 가지로 나뉘어진다. 최장 공통 부분 문자열(Longest Common Substring)과 최장 공통 부분 수열(Longest Common Subsequence) 두 가지로 나뉘는데 비슷하나 차이점이 뚜렷하다. 그 차이점은 해당 부분의 연속 여부이다. 아래 예시를 봐보자.
LCA에 대해 알아보자
LCA Lowest Common Ancestor(LCA) 즉, 최소 공통 조상을 구하는 알고리즘이다. 두 정점 u,v에서 가장 가까운 공통 조상을 찾는 과정이다.
KMP에 대해 알아보자
KMP 문자열 검색 알고리즘 중 접두사와 접미사를 구하는 알고리즘으로 naive 문자열 검색과 달리 문자열 전부를 검색하는 것이 아닌 접두사와 접미사가 같은 조건에 의해 만들어진 실패함수로 적절하게 인덱스를 조정하여 검색하는 알고리즘이다.
RABIN KARP에 대해 알아보자
라빈-카프(Rabin-Karp) 라빈-카프 알고리즘은 문자열 매칭 알고리즘 중 하나이다. 항상 빠르지는 않지만 일반적인 경우 빠르게 작동하는 간단한 구조의 문자열 매칭 알고리즘이라는 점에서 자주 사용된다.
문자열 검색에 대해 알아보자
문자열 검색 Naive Matching 먼저 Naive Matching 알고리즘은 찾고자하는 문자열과 주어진 문자열을 하나하나 비교하면서 처음부터 끝까지 확인하는 방식이다. 최악의 경우 시간복잡도 O((n-m)m)이 걸린다. 하나하나 일일이 검사하므로 작은 문자열이라면 시도할만 하다. 하지만 대부분이 큰 문자열이 주어지므로 최대한 피하자.
트라이(TRIE)에 대해 알아보자
트라이 문자열에서 검색을 빠르게 해주는 자료구조이다. 정수형 자료형에서 이진색트리를 이용하면 O(logN), 문자열에서 이진검색트리를 사용하면 문자열의 최대 길이가 M 일때 O(MlogN) 시간복잡도를 갖는다.
DOCKER에 대해 알아보자
IT 업계에 종사하는 사람들이라면 한번 쯤은 들어보거나 봤을 법한 고래 캐릭터와 Docker를 공식페이지에서 대문글로 이렇게 표현한다.
이항계수에 대해서 알아보자 (FEAT. 페르마의 소정리)
이항 계수 이항 계수란 n개의 원소에서 r개의 원소를 뽑아내는 경우의 수 즉, 조합. 수식으로는 n!/(r!(n-r)!)
JENKINS에 대해 알아보자
Jenkins 란? CD Foundation의 프로젝트 중 하나인 Jenkins는 오래 전부터 사랑받아온 CI/CD Tool 중 하나이다.