siino's 개발톡

세그먼트 트리란? (Segment Tree) 여러개의 데이터가 연속적으로 존재할 때 특정한 범위에 대한 질의를 O(logN)의 시간복잡도로 해결할 수 있습니다. 여기서 말하는 질의(query)란 특정 index에 대한 update, 특정 구간에 대한 SUM, MIN, MAX등이 해당됩니다. 기본적인 개념은 데이터의 범위를 반씩 분할하며 그 구간의 query를 수행합니다. 구간합을 구하는 Segment Tree 위 그림에서와 같이 [1, 3, 5, 7, 9, 11]이라는 배열이 주어질 때, 구간의 대표값을 Tree에 저장합니다. Root노드는 0 ~ 5까지의 index를 대표하는 값, left child는 0 ~ 2 까지의 index를 대표하는 값, right child는 3~5 까지의 index를 대표하..

https://www.acmicpc.net/problem/11053 최장 증가 부분 수열은 말 그대로 수열의 부분 수열 중에 가장 길이가 긴 것을 구하는 문제이다. 최장 증가 부분 수열을 푸는 방법은 크게 3가지로 분류된다. 1. 무식하게 풀기 - 완전탐색 (재귀) 2. dp 풀이 - 메모이제이션을 활용 3. 이분탐색을 활용한 풀이 - LIS(k): 길이가 k인 LIS 중 마지막 수가 최소인 수를 저장 ## 각각의 시간복잡도는 어떻게 될까? 1. 완전탐색 --------> O(2^N) 2. dp --------> O(N^2) 3. 이분탐색 --------> O(NlogN) 개념이 계속 헷갈려서 각각의 방법을 활용하여 직접 java 코드로 구현해보았다. 아래의 java 코드를 함께 보면서 알아보도록 하자...

문자열에 해싱기법을 사용해서 해시값으로 문자열을 비교하는 알고리즘 보통 문자열 매칭 알고리즘에 많이 쓰임 (특정 문자열 패턴이 원본 문자열에서 얼마나 나왔나?) 슬라이딩 윈도우와 비슷한 방식으로 rolling 기법을 사용해 문자열을 탐색하며, 기존의 문자열을 재활용하여 다음 문자열을 구함. 이때 소수 P와 a는 적당히 크게 잡아야하는데, 너무 작으면 해쉬 충돌의 가능성 너무 크면 오버플로우와 계산 시간의 증가 a진법을 사용하여 패턴과 원본 문자열들을 해싱. 정석: 적당히 큰 소수 P와 P의 원시근 a를 선언한 후, 문자열을 a진수로 나타냄(MOD P) 타협**: 적당히 큰 수 P, 소수 a를 선언. 해쉬충돌 방지를 위해 2~3 번의 해쉬 중첩 사용.** 예시 코드) BOJ 1786 찾기 import ja..