구현팁

  1. Negative Index Array

    많은 사람들이 상황따라 0base와 1base를 혼용한다. 그러나 나는 너무 헷갈려서 이진트리 노드번호 이외에 1base는 사용하지 않는다. 지금까지는 int& f(i)=arr[i+1]; 이런 인덱스 조정함수를 통해 음수인덱스를 해결해왔는데, 최근에 Pythonic한 음수인덱스 지원하는 배열클래스 만들어 써보니까 굉장히 편하다. 일단 prefix sum과 suffix sum 이 둘의 선언과 사용이 거의 똑같아진다.

    Arr<int> pf(n+1),sf(n+1);
    pf[i]=pf[i-1]+a[i];
    sf[i]=sf[i+1]+a[i];
    

    모듈러까지 추가해서 사용해봤는데, 심각하게 느려져서 모듈러는 제거했다. 모듈러 자체도 느린데, const 아닌 모듈러는 더욱 느려서 납득할 수 없는 속도가 나온다.

    다행히 음수인덱스만 지원할때는 조건분기(if나 ternary) 하나로 처리할 수 있어서 성능차이가 거의 없다.

    코드 (Line 54)
  2. Lambda Recursion

    람다함수를 정의할때 std::function<함수타입>으로 저장하면 Recursion이 가능하다. 전역변수를 지역변수캡쳐로 대체할 수 있어서 테케문제 풀때 편하다.

    그냥 쓸 경우 함수의 타입을 두번 써야 하는게 넘 귀찮은데, 아래의 코드처럼 매크로를 만들어두면 한번만 써도 된다.

    #include <bits/stdc++.h>
    using namespace std;
    #define RETT(...) __VA_ARGS__
    #define func(RetT,fname,...) function<RetT(__VA_ARGS__)> fname=[&](__VA_ARGS__)->RetT
    signed main(){
    	int z=5;
    	func(int,f,int x,int y){return (x+y)*z;};
    	cout<<f(3,4)<<endl;
    
    	func(RETT(pair<int,int>),g,pair<int,int> x){return {x.first*x.first,x.second*x.second};};
    	auto res=g({3,4});
    	cout<<res.first<<' '<<res.second<<endl;
    }

    두번째 예제의 경우 리턴타입을 RETT()매크로로 감싸줘야 하는데, 타입에 콤마(,)가 들어가면 인자가 쪼개져서 인식되기 때문이다.

home