리유나의 항해일지

오래간만에 글을 올리네요. 최근에 풀었던 "악마의 수열"이라는 문제가 꽤나 인상이 깊게 남아서 포스팅을 올립니다! solved 기준 골드 1인 문제고, 개인적으로 골드1이라기엔 너무 쉬운 거 아닌가 싶지만, 그건 제가 주력이 수학이라 그런 거려나 생각합니다() 문제를 요약하면 다음와 같습니다. "x_0=0, x_1=1, 그 뒤로는 앞 두 항의 평균으로 이루어진 수열에 대해서, x_n에서 0 뒤로 6이 몇개 연속하는지"를 묻는 문제입니다. 실제로 이 수열을 한번 구해볼까요? 엑셀로 빠르게 만들어 본 결과, 대략 이런 규칙을 가지고 나아가는 것을 알 수 있습니다. 무언가 점점 0.666.....으로 가까워지는듯한 기분이 들죠? 실제로 그런지를 확인하기 위해서는 수열의 일반항을 구해야 하는데, 평범한 등차/등..

(2022년의 마무리를 맞아서) 2022번 사다리라는 문제를 풀었습니다. 난이도는 솔브드 기준 골드 5고, 실제로(제 기준)그리 어려운 문제는 아니지만 적당히 접근하는 방법과 풀이가 problem solving과 단순 기하학/수학이 잘 접목되어서 이루어지는 느낌이라 꽤 괜찮은 수학 문제라고 생각했습니다. 문제 링크는 다음과 같습니다. https://www.acmicpc.net/problem/2022 2022번: 사다리 첫째 줄에 차례대로 x, y, c에 해당하는 양의 실수 세 개가 입력된다. 수는 소수점 여섯째 자리까지 주어질 수 있으며, 3,000,000,000보다 작거나 같다. www.acmicpc.net 문제 자체는 아주 간단합니다. 위 그림에서 x, y, c가 주어졌을 때 두 건물 사이의 거리를 ..

너무나도 감개무량하네요. 이걸 달 수 있을거라곤 전혀 생각 못하고 살았어요. 이 과정에서 편식하던 알고리즘들 이것저것 많이 먹게 되어서 좋았다고 생각해요. 다만 아직도 트리 같은 걸 너무나도 편식하는 것 같아서 조금 걱정이네요. 클래스 8 가는 길에 풀었던 문제들은 다음과 같습니다! 몇개 빼고 거의다 수학/기하학/게임이론 쪽이네요 ㅋㅋㅋ; 앞으로 두루두루 여러 분야의 문제들을 풀면서 연습해보겠습니다!

https://www.acmicpc.net/problem/10167 10167번: 금광 첫 줄에는 금광들의 개수 N (1 ≤ N ≤ 3,000)이 주어진다. 이어지는 N개의 줄 각각에는 금광의 좌표 (x, y)를 나타내는 음이 아닌 두 정수 x와 y(0 ≤ x, y ≤ 109), 그리고 금광을 개발하면 얻게 되는 이 www.acmicpc.net 정말로 유명한 문제입니다. 당시 중등부에 이정도 난이도 문제가 나와서 말이 많았다고도 하고, 풀이 자체는 여러 문제에서 유용하게 쓰일 수 있기 때문에 세그트리 응용을 공부할 때 꼭 한번씩은 짚고 넘어가는 문제입니다. 이 문제의 프리퀄 격이라 할 수 있는 연속합과 쿼리(예전에 쓴 블로그 글)를 풀어보신적이 있으시다면 더욱 이해가 쉬울 것입니다. 문제를 요약하면, "..

www.acmicpc.net/problem/18138 18138번: 리유나는 세일러복을 좋아해 너비가 3인 티셔츠와 너비가 2인 세일러 카라를 붙이고, 너비가 5인 티셔츠에 너비가 5인 세일러 카라를 붙이고 너비가 7인 티셔츠에 너비가 4인 세일러 카라를 붙이고 너비가 10인 티셔츠에 너비� www.acmicpc.net 가끔 이 문제 관련해서 질문을 받습니다. '이거 정말 너가 만든 거야??' 네 맞아요...제가 만든 문제고 이분매칭 한창 배울 때 연습 겸해서 만들었던 문제입니다. 사실 딱봐도 이분매칭스러워 보이지 않나요? (참고로 제 닉네임이 등장하는 문제들은 대부분 제가 만들었습니다. 14556 Balance 제외하고) 일단 이분매칭에 대해서 정말 간단하게 설명하자면, 이분 그래프가 있을 때(정점이 ..