내일 국민대 알고리즘 대회라서 장장 두 달만에 키보드를 잡아보았다. 사실 그 사이에 쇼미더코드 치느라 딱 하루 한 적이 있긴 하다. 문제집 문제 링크 위상정렬 + 순서 관계 없는 것들끼리는 번호순으로. 예전에 풀어봤던 문제라 거의 5분 컷 한 것 같다. 풀이 더보기 칸 알고리즘으로 구현해야 한다. 코사라주 알고리즘(역간선 활용)으로는 아마 방법이 없을 것이다. 기존의 칸 알고리즘의 큐 부분을 우선순위 큐로 바꾸어 풀어주면 된다. #include #define rep(i,a,b) for (auto i = (a); i sync_with_stdio(0); cin >> n >> m; rep(i,1,m) { int a, b; cin >> a >> b; adj[a].push_back(b); ind[b]++; } r..

알고리즘 트레이닝 초록책 2판을 오늘 받아보았다. 새롭게 추가된 내용이 곳곳에 있을 것이기 때문에 앞에서부터 살펴보았다. 역시나 따로 언급되지 않은 '3.3 코드 최적화'라는 목차가 생겼다. 코드 최적화는 고인물들이 아니더라도 통용되고 잘 알려진 기법이다. 하지만, 그 최적화를 깊이있게 이해하는 사람은 드물고, 그냥 입에서 입으로 전해지는 정도인 것 같다. 따라서 최적화의 중요한 부분들을 보충해주는 것이 마음에 들었다. 덕분에 갖고 있던 의문점들도 많이 해결되었다. 컴파일러 출력 컴파일러 최적화 /2, %2 등을 비트연산으로 대체하는 코드들을 보면서 안 예쁘다고 느껴왔었다. 그래서 세그트리 기본문제에다가 비트 연산을 사용한 경우와 그렇지 않은 경우를 비교해 본 바 있다. 하지만 유의미한 속도 차이가 없어..