본문 바로가기

전체 글

 (22)
2024 대학수학능력시험 수학영역 풀이 목요일에 기숙사에 일찍 들어왔는데 딱히 할 게 없어서 재미삼아 수능 수학 문제를 풀어보기로 했다. 금방 풀 수 있을 것이라고 예상했으나, 실제로 미적분이나 기하는 올림피아드와 범위가 달라 개념이 익숙치 않고 문제와 직관을 곧바로 연결짓지 못하여 매우 오래 걸렸다. 46문제를 모두 푸는 데 150분 정도 걸렸던 것 같고, 조금 부끄럽지만 이중 절반 이상이 미적분과 기하에 쓰였다. 아직 고1이라 미적분과 기하를 충분히 연습하지 않았기에 당연한 결과다. 채점 결과는 미적분 30번에서 엉뚱한 실수로 틀렸는데 실제 수능이었으면 굉장히 아쉬웠을 것이다. 어차피 영재학교는 수능과는 무관하므로 결과는 상관없고 문제의 핵심 아이디어를 막힘없이 떠올렸다는 것이 중요한 것 같다. 수능 문제 풀이를 간단히 적어보려고 한다. ..
Mixtilinear circle의 성질 Mixtilinear circle은 수학 올림피아드의 기하 영역에서 자주 등장하는 원이다. 이 원이 명시적으로 주어지는 경우도 있지만, 이보다는 이 원을 보조적으로 잡으면 문제 풀이가 쉬워지는 경우가 있다. 그래서 이 원의 성질을 알고 있으면 문제를 날로 먹을 수 있는 경우가 상당히 있으므로, 문제를 풀면서 이 원을 접하게 될 때마다 추가적인 성질들을 기록해 두고자 한다. Mixtilinear circle의 정의 삼각형 ABC에서 AB, AC에 접하고 (ABC)에 외접하는 원을 A-mixtilinear excircle 이라 하고, AB, AC에 접하고 (ABC)에 내접하는 원을 A-mixtilinear incircle이라 한다. 여기서 (ABC)는 삼각형 ABC의 외접원을 의미한다. 기초 성질; EGMO..
BOJ 30513번: 하이퍼 삼각형 자르기 SASA Programming Contest 2023 Div. 1 (Arena #11)을 쳤다. 원래는 학교 작은 실험실 일정과 겹치고 아레나가 참가 범위가 아니어서 치지 않으려고 했다. 그러나 작은 실험실 행사가 예상보다 일찍 끝났는데 백준을 열어보니 대회창에 진행중인 대회가 보여서 갑자기 치고 싶어져서 쳤다. 15시~18시에 한 대회인데, 사실상 15시 20분에 문제풀이를 시작했다. 늦게 시작했고 아레나 참가범위가 아니어서 성적이 아무 의미 없으니, 재미로 어려운 문제들부터, 즉 H번(A번에서 N, Q 제한이 바뀐 조건)부터 B번까지의 역순으로 풀기로 했다. E번까지 풀고 나니 17시 25분 정도였고, 부모님께 전달받을 물건이 있어서 빨리 내려갔다 오니 17시 35분이었다. B, C, D는 쉬우므로 ..
BOJ 15507번: 연산 최적화 개요 - 알고리즘 분류: KMP, BFS - 문제에 대한 평가: 아이디어가 기발함. 함수를 단순화해서 문제를 해결하는 것에 대한 시사점을 제공함. 문제 요약 0과 1로만 이루어진 길이 N의 문자열 S가 있다. 연산 F는 다음의 세 연산으로만 이루어진다. A: 끝에 0 추가, B: 끝에 1 추가, C: 앞의 문자열을 한번 더 복사 A, B, C의 합성으로 이루어진 함수 F에 대해, F(F(O)) = S인 F가 존재하는지 판별하고, 존재한다면 이중 합성횟수가 가장 작은 것의 횟수를 구하라. 단, O는 빈 문자열이다. 문제 풀이 과정 문자열에 대해 여러 가지를 시도해 보았으나 잘 안 되었다. 그래서 가장 원초적인 것부터 하기로 했다. 문자열의 길이만 따지는 것이다. 길이가 X인 문자열에 A, B, C를 적용하..
BOJ 18193번: 비행기 타고 가요 개요 - 알고리즘 분류: Dijkstra, Merge Sort Tree, Segment Tree Lazy Propagation - 문제에 대한 평가: 2차원을 관리하는 효과적인 자료구조에 대한 시사점을 제공함. 아이디어가 기발함. 구현이 상당히 많음. 문제 요약 N개의 정점이 있는 그래프에서 간선 M개가 다음과 같이 주어진다. (cost, s1, s2, e1, e2): 모든 s1 이상 s2 이하의 정점에서 모든 e1 이상 e2 이하의 정점으로 가는 가중치 cost의 간선이 있다. V에서 각 정점까지의 최단 거리를 구하라. 문제 풀이 과정 먼저, s1을 인덱스로 삼고 s2에 대해 정렬하는 Merge Sort Tree를 만든다. Dijkstra를 수행하되, 티켓을 정점으로 생각한다. 이때 (e1, e2)로 ..
PS에 사용되는 C++ 기능 정리 C++의 Standard Template Library에는 C언어보다 훨씬 많은 함수와 기능들이 있기 때문에, 이들을 모두 익히는 것은 불가능하다. 하지만 PS에 사용되는 함수와 자료구조들은 굉장히 한정적이다. 이에 이들을 간략히 정리하고자 한다. 다른 사람들도 볼 수 있게 해서 문제를 풀다가 필요한 기능에 해당하는 C++ 함수를 찾아볼 수 있도록 하고, 나도 가끔씩 C++의 함수가 헷갈리기 때문에 정리해 두고 참고용으로 사용하기 위함이다. 나는 C++ 언어 자체는 깊게 모르고, PS에 사용되는 기법들만 익히는 정도이기 때문에, 이론적인 내용에는 오류가 있을 수 있으며 오류를 발견하면 댓글로 달아주면 감사하겠다. iterator 객체지향형 프로그래밍 언어인 C++의 가장 큰 특징은 class와 templ..

티스토리툴바