전체 글 (23) 썸네일형 리스트형 Optimal Binary Search Tree 염치 없이 돌아왔다. 이번 학기에는 자료구조 수업을 듣게 되었는데, 상당히 흥미로운 내용이 많아서 정리할 겸 블로그에 올려두려고 한다. 그 첫 시작은 바로 최적 이진탐색트리(OBST)에 관한 것! 1. 문제 정의 보통 우리가 생각하는 이진탐색트리(BST)에 관한 문제는: BST가 어떤 경우에서든 균일한 성능을 보이도록 최적화(AVL, Splay) BST의 높이, 노드 개수 등에 관한 수학적인 탐구 BST를 어떻게 응용할 수 있는가(허프만 인코딩) ..뭐 이런 문제들이다. 근데 이번에는 다루는 문제의 결이 조금 다르다. "각 노드들에 대한 방문횟수가 모두 정해져 있을 때, 탐색횟수가 가장 작은 형태의 BST는 무엇인가?" 즉, 이번에는 BST를 최적화한다기보다도 이론상으로 가장 최적인 BST가 무엇인지, .. 7/14~7/15 Codeforce 연습 학기가 끝났다. 정말 열심히 놀았다. 학점도 적당히 받았고 하니 이제 PS를 해보자! 1000-1500 rating의 그리디 문제들을 잡았다. 1703F. Yet Another Problem About Pairs Satisfying an Inequality 문제에서 요구하는 식이 웃깁니다. $a_i 졸업식을 하고 나서 어느새 졸업입니다. 사실 전혀 믿기지가 않습니다. 3년 전 입학했을 때는 학교의 모든 것이 어색했습니다. 7시부터 자습해야 하고, 잠은 반드시 12시 이후에 자야 하고.. 평소엔 당연하게 생각했던 것들을 빼앗겨서 너무 힘들었던 기억이 납니다. 그 중에서도, 주변 사람들은 다 너무 멋지고 똑똑한데, 저만 보잘것없다는 것이 제일 힘들었습니다. 돌이켜보면 힘들었던 기억들이 대부분입니다. 그래도 좋은 친구들이 있었기에 힘든 시간 속에서도 즐거움을 찾을 수 있었습니다. 놀 때는 확실히 놀 줄 알던 1학년 4반 친구들, 인문예술주간 동안 밤새면서 함께해준 친구들, PS라는 괴상한 취미를 함께해준 친구들, 자습시간마다 4층 엘베앞에서 놀아 준 친구들, 제가 힘들어할 때마다 언제라도 연락을 받아주고 도와 준 친구들까지.. 지금까지의 삶 + 12/25 PS 입시가 끝났다. 서울대학교 컴퓨터공학부에 입학하게 되었다. 이제 다시 PS를 시작해야 한다. 내 큰 계획은 다음과 같다. 1. PS 재활 + 코드포스 기초 쌓기 2. 백준 기초부터 다시 풀기 3. 흥미로운 것들 학습. 지금은 가우스 소거법과 hld를 배우고 싶다. 4. 코드포스 블루 찍기 일단 코드포스에서 쉬운 문제들을 잡고 풀어보았다. 실력이 처참함을 다시 깨닫는다. Codeforces 1620B. Triangles on a rectangle 간단한 문제이다. 삼각형의 넓이는 밑변과 높이에 의존한다. 최소한 두 점이 같은 변 위에 존재하므로 높이가 최대일 때는 나머지 한 점이 반대편에 존재할 때이다.따라서 네 변 각각에 대해 거리가 최대인 점의 쌍을 찾아서 높이를 곱해주면 된다. Codeforces 1.. 2021(2022학년도) 연대논술 후기 UPD: 최초합 했습니다. 보고 와서 점심 먹자마자 바로 쓰는 글입니다. 심각하게 아무말이고 두서가 없을 수 있습니다. 저는 물리 선택했고, 시간은 수학 4문제 + 물리 4문제 해서 2시간 30분 받았습니다. 타임라인 순서대로 정리되어 있습니다. 제 스스로 복기하고자 하는 글이어서 문제풀이 자체를 엄밀히 하진 않고 그냥 제 실수/반성할 점 위주로 적겠습니다. 전날 전날 밤에는 그다지 떨리지가 않았습니다. 이게 시험을 보는 거긴 한가.. 챙겨야 할 물품들을 몇 개 챙겼습니다. 물, 마스크, 워밍업 문제집, 필통(지우개 2개) 뭐 이렇게 챙긴 것 같습니다. 제 집에서 연세대까지 1시간 정도 걸리기 때문에 4시 반에 일어나서 5시에 출발하는 것으로 계획을 잡았습니다. 그런데, 쇼미10 1화를 하더라구요..너무.. 내가 본 천재의 특징 수학을 잘 하는 친구들을 보면..물론 직관이 아주 뛰어난 사람들도 많지만 내가 본 천재들 중 대부분은 시행착오가 엄청 빨랐다. 그들의 문제 풀이 과정은 이렇다: 1. 연습을 통해서 풀이 데이터베이스를 쌓는다. 2. 이미 아는 문제는 푼다. 3. 모르는 문제가 나오면, 자기가 가지고 있는 모든 풀이 후보들을 아주 빠르게 훑으면서 되는지 안 되는지 파악한다. 4. 뭔가 의미 있는 결과를 얻으면 답을 얻기 위해 새로운 결과에 대해 3~4번을 반복한다. 천재들은 3~4번이 엄청 빨라서 나 같은 사람이 보기에는 말도 안되는 직관을 가진 것처럼 보이지만, 실제로는 머릿속에서 내가 몇 시간동안 할 연산을 몇분만에 진행해서 답을 찾는 것 같다. 결국 그들도 노력 안 하고 그 실력을 얻은 건 아니다. 나보다 효율이 훨씬.. 2021 NYPC 연습문제 풀기 2021년도 NYPC가 내일 시작한다. 연습문제 2개가 올라와서 풀어보았다. 1. 최대구간합 너무 유명한 문제다. $dp[i] = max(dp[i-1]+a[i],\,\, a[i])$ 2. 도토리를 주워라 출력 결과만 제시하면 되지만, 그냥 평범한 문제라고 생각하고 풀어 보자.좌우로 움직이는 것이 자유롭기 때문에 칸별로 보는것보다는 움직일 수 있는 구간별로 보는 것이 좋다. 만약 어떤 두 구간 사이에 유저가 존재한다면 두 구간에 있는 도토리를 동시에 먹을 방법이 없다.따라서 dp를 다음과 같이 세운다: $dp[i][j]=$ $i$번째 가로줄에서 $j$번째 구간에 있는 도토리를 모두 먹을 때 최대 도토리의 개수 구간끼리의 연결 관계를 설정하면 상태 전이는 $dp[i][j] = max(dp[i-1][k])$ .. Codeforces Round #738 후기 -56 gg 구현이 정확한 건 너무 좋았는데 전혀 빠르지 않았다. D1의 핵심적 관찰을 해놓고도 기초가 없어서 못 푼건 좀 아프다. A. Mocha and Math 시행을 하면 할수록 값들이 작아진다. 따라서 그냥 모든 쌍에 대해서 한번씩 시행해주면 된다. B. Mocha and Red and Blue 연속된 ?들의 색을 번갈아 칠하는데, 연속된 ? 앞의 문자와 다른 문자로 시작해서 번갈아 칠하면 된다. 이 전략대로 칠하면 연속된 색이 1개 이하로 추가된다. 따라서 중간에 연속된 것이 존재하는 해는 무의미하다. C. Mocha and Hiking 예제를 가지고 놀다 보면 가능한 경로가 몇 개 없다는 걸 알게 된다. 1. n+1 -> 1 -> .. -> n 경로 2. 1 -> .. -> n -> n+1 경.. 이전 1 2 3 다음
