구현팁

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)

DP 탑다운을 바텀업으로 rewrite할때에는 다음처럼 dp값 접근함수를 따로 두는게 구현이 훨씬 깔끔한거같다. https://www.acmicpc.net/source/61920552 음수인덱스쓰면 거의 몇배씩 낭비되는 경우도 있고 그래서 속도도 빠름.

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()매크로로 감싸줘야 하는데, 타입에 콤마(,)가 들어가면 인자가 쪼개져서 인식되기 때문이다.