Processing math: 100%

본문 바로가기

전체 글

(26)

내가 본 천재의 특징 수학을 잘 하는 친구들을 보면..물론 직관이 아주 뛰어난 사람들도 많지만 내가 본 천재들 중 대부분은 시행착오가 엄청 빨랐다. 그들의 문제 풀이 과정은 이렇다: 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 경..

8월 1주차 PS 컨셉은 쉬운 문제 밀기 + 그리디 Codeforces Round 703B. Eastern Exhibition Sol)

$y$ 축이 독립이기 때문에, 각각에 대해서 최소인

$y$ 좌표를 찾으면 충분하다. 이때, 거리가 절댓값들의 차의 합으로 정의되기 때문에 거리의 합의 함수가 아래로 볼록해진다. 따라서, 맨 밑의 계곡에 있는 원소의 개수를 찾으면 된다. 점 개수가 홀수일 때는 1, 짝수일 때는 중앙값 2개의 차이를 곱하면 답이다. Codeforces Round 703D. Max Median Sol) 어떤 값의 최댓값을 묻고 있으므로, Parametric Search를 적용해서 답이 x보다 크거나 같은가?라는 질문으로 바꾼다. 어떤 구간에 주어진 값이 오직 1과 -1뿐이라고 하자. 그렇다..

2021 2차 물리인증제 고전역학 간단한 후기 총 문제는 4문제였으며, 시간은 105분이었다. 난이도는 꽤나 평이했다. 파울스 예제를 잘 풀 수 있다면 충분했고, 회전과 해밀턴 역학 쪽은 안 나와서 살짝 아쉬웠다. 다만 계산량이 조금 있었고, 연습을 안 하다가 들어가면 당황할 수 있었다. 문제를 써도 되는지 몰라서 그냥 각각의 유형 정도만 정리해 보았다. 1. 보존력장에서 속도 구하기 파울스 예제에 있거나 기출이거나 둘 중 하나일 것이다..

$mv {{dv}\over{dx}} = F$ 식으로 슥삭하면 된다. 2. 위치에너지와 보존력장 이건 진짜 파울스 예제이다. ㄷㄷ 3. 중력위치에너지, 간단한 조화의 법칙 이것도 파울스 예제인 것 같다.

$mv {{dv}\over{dx}} = F$ 로 속력 구하고 $\int_{0}^{x} {{dx}\over{v}..

Codeforces Round #735 후기 +38 gg 난도는 A

최근 근황 PS 블로그를 한다는 생각으로 티스토리로 옮겨왔으나.. 정작 학교에 가서는 PS보다는 다른 공부에 열중하고 있다. 심지어 중간고사가 끼어있었기에 2~3주 정도는 그냥 시험공부만 했다. 시험은 선형대수, 물리, 수학, 일본어 네 과목이었는데 문제가 전반적으로 되게 재밌었다. 잘 볼지는...ㅠㅠ 손이 아팠다는 점이 특징.. 이제 진짜 시험 딱 하나 남았다. 힘내보자. 그럼 PS는 뭘 했냐고? 3월부터 지금까지 나는 PS 관련해서.. CHT 공부 (활용이 아니다!) 기타 문제 찍먹 실~골 동아리 시간에 찍먹 학교 정보 과목 공부 등등을 했는데..이게 블로그에 올릴 정도로 잘 한것도 아니고 해서 따로 글을 쓰진 않았다. 그리고 놀랍게도 최근에는 PS가 아닌 다른 취미가 생겼다. 바로바로!! 이 녀석이다. 너무 ..

물리인증제 하나 틀렸다 ㅠㅠ 졸업 전에 역학 따고 싶다.

목록 더보기

티스토리툴바