연세대학교에서의 3번째 학기를 마치며 작년 11월 카투사에 합격해서 올해 7월에 입대하는 것으로 결정이 되었다. 입대일 결정부터 실제 입대까지의 텀이 상당히 긴 편이다. 남들보다 빠르게 입대일이 결정되어서 내가 빨리 입대하는 편이겠구나 싶었지만 1학기 동안 엄청나게 많은 지인들이 입대를 했다. CS의 다양한 분야들 중 관심 있는 분야가 많았기에 얼른 이것저것 공부하고 싶었지만, 이미 한 학기 후 입대가 결정된 상황이라 공부해 봤자 흐름이 끊길 거라고 생각했다. 그래서 3번째 학기는 '전역 후 원하는 전공 강의를 마음대로 들을 수 있도록 prerequisite를 모두 채운다'라는 목표를 가지고 시작했다. 공부 이야기는 보기 싫을 수도 있으니 접은글로 넣었다. 더보기 이미 1학년 때 계절학기까지 들어가며 교양과목은 모두 수강해서 이번 학기는 졸.. 2021. 6. 21. 선형 시간에 힙 만들기 Building Heap in Linear Time 힙을 만드는 방법 힙을 만들기 위해서 heapify라는 연산을 정의하겠다. heapify(x): 노드 x의 왼쪽, 오른쪽 자식을 루트로 서브트리가 각각 힙일 때 노드 x를 루트로 하는 서브트리를 힙으로 만든다. 이 연산을 bottom-up으로 모든 노드에 대해서 수행해 주면 해당 트리는 힙이 된다. Heapify의 시간 복잡도 heapify는 다음과 같은 알고리즘으로 수행할 수 있다. 노드 x의 자식이 없다면 이미 힙이므로 종료한다. 그게 아니라면(자식이 있다면) 자식 중 값이 더 큰 노드를 찾는다. 해당 노드의 값이 노드 x의 값보다 작다면 이미 힙이므로 종료한다. 그게 아니라면(1번에서 찾은 노드의 값이 노드 x의 값보다 크다면) 해당 노드와 노드 x를 swap한다. 1번으로 돌아간다. 이 알고리즘은.. 2021. 5. 14. 오로지 PS만을 위한 Sprague-Grundy Theorem(스프라그-그런디 정리) PS를 하다 보면 Combinatorial Game Theory(조합론적 게임 이론) 분야가 있다. 이번 방학 동안 참가한 알고리즘 캠프에서 알게 된 분야인데, 내용이 상당히 어려웠고 다른 사람들도 어렵게 느낄 것이라는 생각이 들었다. 이 분야를 이해하기 위해 열심히 발버둥친 결과, 증명 등은 배제하고 몇 가지 핵심만 안다면 많은 사람들이 충분히 이 분야의 문제들에 도전해볼 수 있을 것이라는 생각을 했다. 따라서 이 글은 엄밀하게 Combinatorial Game Theory를 공부해 보자는 글은 아니며 오로지 PS만을 위한 응용을 목적으로 하는 글이다. 이어지는 내용에서 결론만 이야기하고 넘어가는 부분들이 많은데 이 글의 목적을 위해서 그렇게 서술한 것이니 관심이 있는 사람들은 마지막에 달아 놓은 링크.. 2021. 3. 2. C++의 타입 추론(auto) 주의사항 PS를 하다가 로직이 아무리 생각해도 완벽한데 계속 틀릴 때가 가장 답답하다. 대부분의 경우 오타가 났거나, 오버플로우/언더플로우를 고려하지 못했거나, 문제를 잘못 읽었거나 중 하나인데 드문 경우 프로그래밍 언어의 기능을 잘 숙지하지 못한 경우가 있다. C++로 PS를 하다 보면 auto라는 키워드를 자주 쓰게 된다. range-based loop보다 훨씬 짧게 쓸 수 있고 간편하기 때문이다. 근데 오늘 다음과 같은 상황이 있었다. struct x { int e; long long t; }; vector g[501]; int main(void) { ... while (TC--) { for (auto x: g) x.clear(); ... } ... } 정의된 array of vector를 매 tc마다 초기.. 2021. 2. 15. 교환학생 우리 학교의 최대 장점은 교환학생 제도가 잘 되어 있다는 거 아닐까? 매년 1000명 정도가 교환을 간다고 한다. 통계 방법 상의 차이가 있을 수 있지만 다른 학교들에 비해 압도적인 수치이다. 교환학생을 잘 이용하면 미국 진출에 큰 도움을 받을 수 있을 것 같다. 외국 학교에서 랩 생활도 해 보고 사람들도 만나면 좋겠다 우리 학교의 교환학교 중 이공계에서 가장 랭킹이 높은 곳이 ucb와 gatech인데 둘 다 위상이 대단해서 어디든지 너무 좋을 거 같다. 버클리 eecs는 요즘 너무 핫해서 그런지 교환을 모집하지 않는 걸로 보인다. 버클리에서 모집하는 전공 중 내가 그나마 제일 관심있는 전공은 math나 physics 정도가 있었다. cs와 수학의 시너지는 알려진 바 있으니 수학을 복전할까 일단은 생각 .. 2021. 1. 26. [BOJ #2110] 공유기 설치 BOJ #2110, 공유기 설치 문제입니다. 이전에 풀어서 맞은 문제였는데 얼마 전 재채점이 되면서 틀렸길래 다시 풀어보면서 글을 작성하기로 했습니다. 접근 가장 인접한 두 공유기 사이의 거리가 최대가 되도록 하는 '배치'를 찾는 것은 상당히 어려워 보입니다. 모든 배치를 다 검토해 보는 것은 2 N >> C; for (int i = 0; i > x[i]; sort(x, x + N); int l = 1, r = x[N - 1], mid; do { mid = (l + r) / 2; if (!b(mid)) r = mid; else l = mid + 1; } while (l != mid); cout = C; } 매우 간단한 코드로 이 문제를 해결할 수 있습니다. 2021. 1. 5. 이전 1 2 3 4 다음
