2021. 8. 24. 21:15ㆍ알고리즘 문제풀기/코딩
제가 PS를 할 때 사용하는 여러 코딩 팁을 소개하려고 합니다.
일반
0/1-based
zero-based와 one-based 중 무엇을 써야 하는지에 대한 질문을 종종 봐요. 저는 one-based로 일단 가다가, 몇 가지 사정이 생기면 zero-based로 바꾸는 편이에요.
- circular array, 환형 배열. 크기가 n인 배열이 있는데, 마지막 원소 다음이 첫 번째 원소인 것처럼 원형으로 취급하고 싶다고 합시다. zero-based에서
i
번째 원소의 다음 원소는(i+1)%n
, 이전 원소는(i+n-1)%n
입니다. one-based에서i
번째 원소의 다음 원소는(i%n)+1
, 이전 원소는(i+n-2)%n+1
입니다. zero-based가 훨씬 깔끔해요. 나눗셈 연산은 삼항 연산자(ternary operator)로 쓰면 속도도 빨라질 수 있죠. vector
등 zero-based 자료구조와 오가야 할 때. 가끔 이런 걸 하긴 해요. one-based로 저장한 자료를vector
에 쓰고 처리하는데, 진짜 헷갈리고 비효율적이에요. 그냥 zero-based로 통일하는 게 훨씬 낫죠.lower_bound()
같은 함수를 쓸 때에도 zero-based인 경우가 훨씬 예뻐요.
one-based를 쓰는 게 훨씬 나은 상황도 있어요.
- DP의 base case가 필요할 때. 냅색 알고리즘의 예를 들게요. 이 알고리즘은 물건을 하나씩 추가하면서 그에 맞게 배열을 가꾸며 작동해요. 그런데 i번째 물건을 추가하기 위해서 (i-1)번째의 상태를 참조하는 식으로 코딩한 경우, (i-1)이 음수이면 이를 인덱스로 쓰기 곤란하잖아요? 그래서 첫 번째 원소가 1이고, 아무 것도 없는 상태를 0으로 놓으면 깔끔하게 코딩할 수 있어요. 물론 base case가 예쁘게 산출되지 않는 경우에는 이러나 저러나 큰 차이가 없어요.
- 비어 있는 경우를 0으로 구분하고 싶을 때. 그러니까
nxt[i] == 0
이면 값이 비어 있고,1 <= nxt[i] && nxt[i] <= n
이면 값이 차 있다는 식으로 취급하고 싶을 때 굉장히 유용해요. 전역 변수는 0으로 초기화되니까 비어 있는 경우를 처음에 고려할 필요가 없어요. 만약 zero-based를 쓴다면nxt[i] == -1
일 때를 비어 있는 걸로 취급하고,memset()
등으로 초기화해야겠죠.
목록 저장하기
이건 뭐라고 할까요, 제가 쓰는 원리? 방법론? 패턴? 일단 설명할게요.
값 여러 개를 순서대로 저장해야 할 경우가 있어요.
bool chk[maxn];
for (int i=1; i<=n; ++i) {
if (chk[i]) { /* ... */ }
}
chk[i] == true
인 i
들을 모으고 싶다고 합시다. 물론 vector
를 쓰는 방법이 있죠.
bool chk[maxn];
vector<int> lst;
for (int i=1; i<=n; ++i) {
if (chk[i]) lst.push_back(i);
}
그런데 저는 vector
사용을 되도록 삼가는 편이에요. 시간이나 메모리 사용이 아쉬운 일이 가끔 있고, 또 아예 #include
를 하지 않은 경우엔 이거 하나를 위해 #include
하기도 아깝거든요.
그래서 저는 배열을 더 많이 써요.
bool chk[maxn];
int lst[maxn], lstn = 0;
for (int i=1; i<=n; ++i) {
if (chk[i]) lst[lstn++] = i;
}
해당 목록을 저장할 배열 이름(lst
) 뒤에 n
을 붙인 이름의 변수(int lstn
)로 원소 개수를 저장해요. 원소의 추가가 보시다시피 lst[lstn++] = i;
이렇게 깔끔하게 나와요. 사실 스택을 배열로 구현할 때 이런 모양이 나오는데, 그 때도 0/1-based 등 구현 디테일이 조금씩 다르잖아요. ++
을 전항으로 할 지 후항으로 할 지도 그 선택에 따라 달라지는데, 저는 항상 이렇게 해요.
lstn
은 원소의 개수, lst[lstn]
은 새로 추가할 원소가 들어갈 위치, lst[lstn-1]
은 마지막으로 넣은 원소의 위치지요.
lstn
이 개수라서 초기값이 0이라 전역으로 잡아도 깔끔해요. 순회도 쉽게 가능하고요.
// Longest increasing subsequence
int a[maxn];
int lis[maxn], lisn;
for (int i=1; i<=n; ++i) {
int j = upper_bound(lis, lis+lisn, a[i]) - lis;
lis[j] = a[i];
if (lisn < j) lisn = j;
}
// one-side convex hull
pair<int,int> hull[maxn]; int hn;
for (int i=1; i<=n; ++i) {
while (hn>=2 && ccw(hull[hn-2], hull[hn-1], pt[i])) --hn;
hull[hn++] = pt[i];
}
convex hull 예시에서는 hulln
이 너무 기니까 hn
으로 줄여서 썼어요. ans
도 ansn
타이핑이 굉장히 헷갈리니까 an
으로 쓰구요. 벡터는 자기가 크기를 가지고 있기 때문에 int(v.size())
이렇게 가져 와야 하는데, 위의 방법처럼 배열로 쓰면 변수 하나로 해결되는 장점이 있어요.
앞에서 vector
의 문제점을 몇 개 들었는데 저건 대부분 제가 그렇게 느끼는 것뿐이에요. 실제로 성능에 끼치는 영향은 보통 미미할 거거든요. 다만 이 배열 접근이 굉장히 잦다든가, 서너 개밖에 안 저장할 예정이라든가 하는 경우에는 성능 차이가 약간 날 수 있어요. 전역 변수는 컴파일 타임에 메모리 주소가 정해지기 때문에 동적으로 포인터를 잡아 사용하는 벡터보다 indirection이 하나 적게 들거든요. 로컬 변수도 레지스터 기준 상대 위치가 고정이니 값에 한 번에 접근할 수 있구요.
반복문 매크로
#define rep(i, n) for (int i=0; i<n; ++i)
#define rrep(i, n) for (int i=1; i<=n; ++i)
// 이항계수 (binomial coefficient)
const int mod = int(1e9)+7;
int comb[100][100];
comb[0][0] = 1;
rrep(i, 100) {
comb[i][0] = comb[i][i] = 1;
rrep(j, i-1) comb[i][j] = (comb[i-1][j-1]+comb[i-1][j])%mod;
}
// Floyd-Warshall 알고리즘
int dist[101][101];
int n;
rrep(j, n) rrep(i, n) rrep(k, n) {
dist[i][k] = min(dist[i][k], dist[i][j] + dist[j][k]);
}
// 3-SUM, naïve
// 이번엔 zero-based로 써 볼까요?
int a[100];
int n;
rep(i, n) rep(j, i) rep(k, j) {
if (a[k]+a[j]+a[i] == 0) printf("(%d, %d, %d)\n", k, j, i);
}
이거, 처음에는 싫어했거든요. 미관을 해치는 느낌? 정격 C++가 아닌 느낌으로요. 근데 써 보면 확실히 좋아요. 플로이드-와샬 알고리즘을 한 번 for
문 매크로로 짜고 나면 그 쾌감을 잊을 수가 없어요! 엄청 편하고, 일정하게만 쓴다면 알아보기도 쉬워요. 반복문 매크로는 PS 바깥에서도 많이 쓰더라구요.
쓰신다면 0-based/1-based 매크로를 둘 다 추가해 두시는 게 편해요. 전자는 vector
를 순회할 때 특히 유용하구요, 후자는 human-friendly한 인덱싱을 쓸 때 유용해요. 또 제가 쓰는 것과 다른 모양도 가끔 있더라구요.
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define FOR(i, n) for (int i=1; i<=n; ++i)
#define F0R(i, n) for (int i=0; i<n; ++i)
// ^ 이거는 알파벳 o가 아니라 숫자 영이에요!
STL
std::pair
매크로
#define x first
#define y second
// 아래는 사용 예시입니다.
long long l2(pair<int,int> p) { return p.x*1ll*p.x + p.y*1ll*p.y; }
#define xy(a) a.x, a.y
// 아래는 사용 예시입니다.
pair<int,int> pt[1000];
int ia = 3, ib = 5;
// 이렇게 하면 어렵고 실수할 여지도 있습니다.
printf("line: (%d, %d) -> (%d, %d)\n", pt[ia].x, pt[ia].y, pt[ib].x, pt[ib].y);
// 이렇게 하면 알아보기 쉽고 편리합니다.
printf("line: (%d, %d) -> (%d, %d)\n", xy(pt[ia]), xy(pt[ib]));
저는 (x, y)로 쓰는 게 습관인데, 다른 분들은 아래처럼도 많이 쓰시더라구요.
#define fi first
#deifne se second
first
와 second
는 굉장히 길어요. 또 글자 수도 달라서 예쁘게 정렬되지도 않구요. pair
사용이 어느 정도 익숙해지셨다면 매크로를 쓰는 걸 추천드려요.
x
나 y
라는 이름의 변수를 잡더라도 자동으로 치환된다는 게 단점이에요. 즉 디버거에서 int x;
의 변수를 찾고 싶다면 first
라는 이름의 변수를 검색해야 하는 거지요. 또 애초에 first
나 second
라는 이름의 변수를 잡고 싶으신 분은 곤란할 수도 있어요. 저는 변수 이름을 짧게 짓는 습관이 있어서 그런 점에서 불편함은 많이 못 느꼈어요.
컨테이너 관련 매크로
#define pb push_back
#define eb emplace_back
vector<int> v;
vector<pair<int,int>> v2;
// 너무 길어요...
v.push_back(3);
v2.emplace_back(2, 5);
// 이렇게 하면 짧죠
v.pb(5);
v.pb(-4);
v2.eb(v[0]+1, v[1]+3);
#define all(v) (v).begin(), (v).end()
// 컨테이너 전체를 처리해야 할 때 굉장히 편리해요.
sort(all(v));
v.erase(unique(all(v)), v.end());
int i = lower_bound(all(v), 2) - v.begin();
// 물론 set에도 쓸 수 있구요.
set<int> s;
s.insert(3); s.insert(2); s.insert(5);
v.insert(v.end(), all(s));
#define sz(v) ((int)v.size())
for (int i=0; i<v.size(); ++i) {} // 컴파일러가 경고를 띄워요.
for (int i=0; i<sz(v); ++i) {} // 이러면 괜찮구요.
for (int i=0; i<v.size()-10; ++i) {} // 이러면 underflow로 낭패를 볼 수 있는데,
for (int i=0; i<sz(v)-10; ++i) {} // 이건 안전해요.
자료구조
Indexed tree
이걸 옛날에 설명한 다른 글도 블로그에 있는데, 그새 코딩 습관이 달라져서 새로 적어요.
const int M = 524288; // M은 원소의 최대 개수. 0부터 (M-1)번까지 있다고 생각합니다.
int tree[M<<1];
int range_sum(int l, int r) {
int ret = 0;
// 아래의 for문 선언이 핵심이에요.
for (l+=M, r+=M; l <= r; l/=2, r/=2) {
if (l%2 == 1) ret += tree[l++];
if (r%2 == 0) ret += tree[r--];
}
return ret;
}
위와 같이 코드를 짜는 습관을 들이고 나니까 실수가 확실히 줄었어요. 옛날엔 아래처럼 짰던 것 같아요.
int range_sum(int l, int r) { // 옛날에 짜던 방식
int ret = 0;
l+=M; r+=M; /** (1) **/
while (l<=r) {
if (l%2) ret += tree[l++];
if (r%2 == 0) ret += tree[r--];
l/=2; r/=2; /** (2) **/
}
return ret;
}
1번과 2번으로 표시한 줄을 빠트리는 실수를 정말 많이 했어요. 처음 코드는 for
문의 세 요소에 각각 중요한 내용을 채워 넣어야 하니 까먹을 일이 없죠. 또 l%2
와 r%2 == 0
의 글자 수가 달라서, 똑같은 코드인데도 정렬되지 않았구요. l%2
와 l%2 == 1
은 의미상으로는 다르지만 최적화를 걸고 컴파일하면 똑같아요.
Merge sort tree 초기화
const int M = 524288;
vector<int> ys[M<<1];
void add_point(int x, int y) { ys[x+M].push_back(y); }
void init() {
for (int i=0; i<M; ++i) sort(all(ys[M+i]));
for (int i=M-1; 1<=i; --i) {
auto &v = ys[i], &vl = ys[i*2], &vr = ys[i*2+1];
v.resize(vl.size()+vr.size());
merge(all(vl), all(vr), v.begin()); // std::merge() in <algorithm>
}
}
이렇게 하면 각 원소가 $\log (N)$단계만 올라가기 때문에 $O(N \log N)$ 시간에 완성이 돼요.
'알고리즘 문제풀기 > 코딩' 카테고리의 다른 글
PS에서 사용하는 C++ STL - 초급 (pair) (401) | 2021.08.29 |
---|---|
PS에서 사용하는 C++ STL - 초급 (vector) (374) | 2021.08.20 |
PS에서 사용하는 C++ STL - 기초 (0) | 2021.08.20 |
std::sort를 이용한 정렬 (2) | 2015.09.20 |
구조체 (0) | 2015.09.20 |