복습용 블로그

C++ algorithm 라이브러리에는 lower_bound와 upper_bound가 있다. 이는 오름차순으로 정렬되어 있는 vector 등에서 특정 값을 binary search를 이용해 해당 값이 위치하는 iterator를 리턴한다.  lower_bound(iter1, iter2, data) : iter1 ~ iter2 사이에서 data 이상인 값 중 가장 작은 값의 iteratorupper_bound(iter1, iter2, data) : iter1 ~ iter2 사이에서 data 초과인 값 중 가장 작은 값의 iterator  #include #include #include using namespace std;void lowerBoundVec(vector &vec, int num){ auto it..

C++에서 map, set은 기본적으로 red black tree를 기준으로 만들어져 있다. red black tree는 balanced binary tree로 특정 기준에 따라 좌우 tree가 균형있게 만들어진다.(즉, 좌 작은 값, 우 큰 값일 때 큰 것만 계속 insert 되어 오른쪽 tree만 커지게 되는 문제 해결 등)  red black tree를 직접 구현하는 것은 다음 번에 정리한다.(PS 같은 거에서 직접 tree 만들기는 너무 빡세므로 다음 번에....) 그렇다면 insert, erase, find 모두 O(log N) 으로 동작하므로 이에 대한 내용을 간단히 정리한다. C++ 기본 타입 (int, double, string 등) 이 아닌 struct에 대해 map, set의 key로 ..

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