복습용 블로그

사내 시험에서 나왔다고 알려진 36진법 사칙연산을 구현해보았다. (나눗셈은 얘기가 없었다. 시도는 했지만 아주 어렵군.... 다음 번에 나눗셈도 재도전해보겠다....) 덧셈 원리 : 맨 끝에서부터 더하면서 carry 있으면 carry 처리해준다.  뺄셈 원리 : 맨 끝에서부터 빼면서 마이너스 되는 경우, 앞 자리에서 base만큼 1개 빌려온다. (borrow)(진법 계산 시 음수 개념이 없어 절대값을 기준으로 뺄셈을 구현하였다.) 곱셈 원리 : 기본 곱셈은 덧셈과 비슷하게 맨 끝에서부터 곱하면서 carry 처리를 해주면된다. 하지만 이를 이용함과 동시에 카라츠바 빠른 곱셈을 적용하였다.  카라츠바 알고리즘 : 정석적인 곱셈은 O(n^2) 이지만, 카라츠바 알고리즘을 이용하면 O(n^1.5) 정도이다. 하..

mojo는 python의 느린 성능 개선을 위해 진행중인 AI 용 프로그래밍 언어 프로젝트입니다. (Modular 사에서 개발 중)범용 언어이기 때문에 꼭 AI에만 써야할 거 같진 않고, python3와 호환되므로 현재 python을 이용하는 AI 이외의 웹개발 등에도 충분히 적용 가능해 보입니다. 다만 아직 공개된지 2년 정도된 프로젝트다 보니 당장 현업에서 쓰기에는 부담이 있어 보입니다. (아직 오픈소스 공개는 아니며, MAX라는 AI 모델 실행 패키지는 개인 개발용에서만 무료입니다.) mojo는 python3와 호환되지만, rust의 영향을 많이 받았다고 알려진만큼, rust 스타일의 코드 작성, python 스타일의 코드 작성을 지원합니다. 대표적으로 fn, def 함수 키워드가 있습니다. 그리고..

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) 로 줄일 수 있다. 또한 기존 입력의 값이 수시로 업데이트 되어도 트..