기록(記錄)

본문 바로가기

알고리즘

백준 문제 풀이 [C++] 2370번 시장 선거 포스터 https://www.acmicpc.net/problem/2370 25/03/18 이전에 해결했던 좋은 문제인데, 복습할 겸 다시 적어본다. 문제 접근 방식: 일단 이 문제에는 아주 간단하고 나이브한 솔루션이 존재한다. 그 전에 내가 먼저 해결했던 방법을 소개하고자 한다. 문제를 요약하자면 다음과 같다. 1. 포스터를 순서대로 붙임.2. 즉, 포스터가 시작하는 지점 $l$과 끝나는 지점 $r$이 쿼리로 주어짐.3. 쿼리가 다 끝난 뒤에 보이는 서로 다른 포스터의 개수를 구하는 것이 우리의 목적. 포스터가 위치할 수 있는 범위는 $1$부터 $100 \ 000 \ 000$ ($1$억)까지이다. 또한 쿼리의 개수는 최대 $10 \ 000$($1$만)까지이다. 가장 단순한 방법은, $1$억짜리 배열을 하나 ..
백준 문제 풀이 [C++] 11440번 피보나치 수의 제곱의 합 / 28749번 Квадраты Фибоначчи https://www.acmicpc.net/problem/11440https://www.acmicpc.net/problem/28749 25/03/04 25/03/09 두 문제는 인덱스만 다르고 동일한 문제이므로, 같은 풀이 방법으로 설명하겠다. 문제 접근 방식: 피보나치 수의 거듭 제곱의 합을 구하는 문제이다. $F_{n} = F_{n-1} + F_{n-2}$를 생각해보자. 제곱을 하면 다음과 같다. $$\begin{align}{F_{n}}^{2} &= (F_{n-1} + F_{n-2})^{2} \\ &= {F_{n-1}}^{2} + {F_{n-2}}^{2} + 2F_{n-1}F_{n-2}\end{align}$$ 제곱 항은 공통이 되는데, 뒤에 붙은 $2F_{n-1}F_{n-2}$항이 공통이 되지 않..
백준 문제 풀이 [Python] 33756번 88888 https://www.acmicpc.net/problem/33756 25/04/05 실버 문제인데 재밌다고 느꼈던 문제라서 소개하고자 한다. 문제 접근 방식: 모든 자리수가 8인 수를 8-넘버라고 할 때, 어떤 수 $N$이 8개 이하의 8-넘버의 합으로 표현될 수 있는가를 물어보는 문제이다. 좀 생각하다가, 실버 3치고는 살짝 어려운데? 라고 생각이 들 때쯤 쉽게 아이디어가 떠올랐다. 생각을 해보면 모든 자리수가 8인 수는 모든 자리수가 1인 수 $\times$ 8 의 형태를 가지고 있다. 즉, 8의 배수라는 소리고, 8의 배수끼리 더해도 8의 배수이기 때문에, 일단 $N$은 8의 배수여야만 할 것이다. $N$이 8의 배수라면, 8로 나눠보자. 그러면 나눈 수가 모든 자리수가 1인 수들의 합으로 표현..

수학

회고록

감상록

티스토리툴바