기본적인 배열을 통한 누적합은 구간합을 구하는 데 O(1)의 짧은 시간복잡도가 걸리지만 값이 변경됐을 때는 최대 N번을 통해 변경을 해야므로, 변경을 한 후 누적합을 구하는 시간복잡도는 O(N)이라고 할 수 있다. 하지만 세그먼트 트리를 구하면 O(lgN)만에 연산을 끝낼 수 있다 문제: https://www.acmicpc.net/problem/2042 깃허브주소: https://github.com/surinoel/boj/blob/master/2042.cpp

구간 합을 구할 때 사용하는 유용한 자료구조인 세그먼트 트리다. 구간 합은 데이터가 나열되어 있을 때, 특정 범위에서의 데이터 합을 말한다. 누적합을 구했다는 가정 하에 구간 합은 O(1)의 시간복잡도로 구할 수 있지만, 변경된 사항이 생긴다면 다시 O(N)의 시간복잡도로 누적합을 수정해야 한다. 하지만 세그먼트 트리를 이용하면 수정했을 때도 트리의 높이인 O(lgN)만으로 누적합을 구할 수 있다 1. 세그먼트 트리(누적합) 만들기 리프 노드를 배열 원소를 하고 루트로 올라갈수록 재귀적으로 누적합이 계산된다. 완전 이진트리로 구성하기 때문에 자식 인덱스는 2*부모 + 1, 2*부모 + 2로 구성된다 long long init(int idx, int start, int end) { if (start == ..

가장 큰 차이는 고정된 크기와 유동적인 크기에 있다. std::vector는 멤버함수로 resize를 가지고 있지만, std::array는 가지고 있지 않다. 즉 선언할 때 std::array는 반드시 크기를 명시해야지만 std::vector는 push_back 멤버함수로도 사이즈를 동적으로 늘릴 수 있다는 특징이 있다 단 std::array를 쓰는 이유는 기본 C에서 배열을 명시하는 것보다는 size, swap 등 다양한 함수와 연산자가 가능하기에 사용하는 것이다 #include #include using namespace std; int main(void) { array arr = { 1, 2, 3, 4, 5 }; for (int& u : arr) { cout

디버깅모드로 동작시킬 때 사용자가 아닌 컴퓨터에게 디버깅을 맡겨서 보다 편하게 할 수 있게 하는 함수다. 컴파일 단계가 아닌 런타임 단계에서 에러를 출력한다 assert(식)을 쓰게 되는데, 식이 거짓이라면 오류를 출력한다. 장점이 오류가 발생한 라인도 출력을 해준다 #include #include using namespace std; int main(void) { assert(false); return 0; } 단, Release 모드이고 전처리기 명령에 NDEBUG; 명령이 추가되면 assert 실행이 되지 않는다 주로 API를 작성할 때, 디버깅 도구로 많이 사용된다. 예를 들어 사용되지 않는 메모리를 읽으려고 할 때 오류가 발생한다 #include #include #include using nam..

전 포스팅에 이어서 작성해보려고 한다 https://noel-embedded.tistory.com/1175 카메라에 비친 AR마커 위치에 따라서 Turtlesim이 움직이도록 하는 코드를 작성해보려고 한다 따라서, 카메라 - AR마커 alvar - 새 작성 노드 - turtlesim으로 노드 구성을 하려고 한다 터틀심 속도를 publish를 하고, 속도 제어를 하면서, 동시에 pose를 실시간으로 체크한다 회전과 병진속도는 각각 z, x 축에 의해서만 움직인다. 즉 전방은 x축, yaw는 z축을 의미한다 pose 값은 다음과 같이 발행이 된다. 왼쪽 아래는 (0, 0), 오른쪽 위는 (11, 11)이다 다음은 AR 마커 토픽에 대한 내용이다. 이 토픽을 Subscribe를 할 것이다 $ catkin_cr..

재귀적으로 명령어를 실행할 때 사용된다. 다음 쉘 스크립트는 재귀적으로 ls -al을 실행하지 못하는 것을 알 수 있다 $ a="ls -al" $ echo $a > ls -al eval은 이때 사용하는데, eval "$(명령어)" 구조로 사용한다 $ a="ls -al" $ eval "$(echo $a)" 두 개 이상의 명령어를 실행하고 싶으면, 새미콜론으로 구분할 수 있다. 그래서 다음과 같이 작성할 수 있다 $ a="ls -al; cat README.md;" $ eval "$(echo $a)" 실제로 다음과 같은 복잡한 명령도 한 번에 실행할 수 있다 $ eval "$(ssh-agent -s)"