복습용 블로그

Index Tree 는 말 그대로 tree를 index로 관리하는 것을 의미한다. 즉, left, right child, parent 를 직접적으로 연결하지 않고, balanced binary tree 라는 가정 하에 수식으로 부모와 자식 index 를 계산한다.  Index Tree 는 이진 트리 역할을 하면서 주로 구간 최대값, 최소값, 구간합 등을 구할 때 사용된다. 이진 트리이므로 트리 전체를 만드는데는 O(N log N), 트리를 업데이트 하는데는 O(log N) 이 소요된다.  단순히 특정 구간의 최대, 최소, 합 등을 구할 때 O(M) (구간 길이 M) 이지만, 쿼리가 매우 많다면 O(QM) 이므로 이를 O(Q log M) 로 줄일 수 있다. 또한 기존 입력의 값이 수시로 업데이트 되어도 트..

회사에서 웹공격 관련한 솔루션을 만들고 있어서 간단히 개념 공부를 위해 드림핵으로 웹해킹 개념 공부를 하려고 한다. 참고 사이트 : https://dreamhack.io/lecture/roadmaps/1 Web Hacking웹 해킹을 공부하기 위한 로드맵입니다.dreamhack.io (드림핵에서 워게임 문제도 몇 개 풀어보고 했지만, PS 푸는 게 더 재밌는 거 같다.)1. Cookie & Session HTTP 특징 : Connectionless, Stateless 을 기본적으로 가짐Connectionless : 하나의 요청에 하나의 응답을 한 후 연결을 종료하는 것. 이후 요청이 있을 때마다 새로운 연결을 만든다.Stateless : 통신이 끝난 후 상태 정보를 저장하지 않는 것. 다른 연결에서 이전..

combination, permutation 의 값만 계산하는 것은 공식을 이용하거나 dp 를 이용하거나 하면 구할 수 있다. 하지만 모든 케이스를 뽑아내야 한다면 단순 공식만으로는 안 된다.  이를 정리한 내용은 아래와 같다.https://ghqls0210.tistory.com/323 permutation, combination 구현 C++회사에서 치는 시험에 구글링이 안 되서 짬짬이 알고리즘들 개념을 다시 정리하고자 한다. 1. permutation (순열) 간단히 {0,1,2,3,4} 배열에서 5P3 을 구한다고 하면 {0,1,2} ~ {4,3,2} 까지가 계산된다. 이를ghqls0210.tistory.com

KMP 알고리즘은 ctrl + F 와 같이 긴 문자열에서 특정 패턴을 찾을 때 사용되는 알고리즘이다.  단순히 하나씩 검색 시, 검색 대상 문자열 길이가 N, 검색 패턴 길이가 M일 때 O(NM) 이 소요되지만, KMP를 이용 시 O(N+M)이 소요된다.  KMP 알고리즘은 다음과 같이 동작한다. - 실패 함수를 통해 패턴의 prefix와 suffix의 일치하는 최대 길이를 계산- 계산된 실패함수를 바탕으로 패턴 매칭 실패 시 suffix 위치로 이동 실패 함수 (아래에서 pi 함수)ababaabbabab 와 같은 패턴이 있을 때, prefix와 suffix의 공통 최대 길이를 구하는 함수이다. ababaabbabab의 경우, abab / aabb / abab 와 같이 prefix와 suffix의 공통 ..

Trie 자료구조는 Tree와 유사하지만, element 개별로 트리를 구성하는 것이 아닌, 공통 prefix를 기준으로 tree를 구성한다.  대표적인 Trie 예시는 string 간의 공통 substring 검색, 검색엔진에서 검색어 유무 확인, 이더리움의 state 저장에 사용되는 merkle patricia trie 등이 있다. Trie 예시 : 알파벳 소문자로만 이루어진 경우 입력 : apple, app, banana, bbb, ccc, cat  root를 기준으로 새로운 문자열 삽입 시, char 단위로 null이 아닌 곳을 따라 가다가 null 인 지점을 만나게 되면 해당 노드부터 한 글자씩 노드를 추가로 생성하면 된다.  입력된 문자열이 Trie에 존재하는 지 여부의 경우, 마찬가지로 Tr..