BOJ 검색 결과

해당 글 10건

백준 온라인 저지 - 13716. 피보나치 수열처럼 보이지만...

https://www.acmicpc.net/problem/13716 13716번: 피보나치 수열처럼 보이지만... 첫째 줄에 n과 k가 주어진다. (1 ≤ n ≤ 1017, 1 ≤ k ≤ 40) www.acmicpc.net 피보나치 수열이 주어질 때, $$F_1 = 1,\quad F_2 = 2,\quad F_{n+2} = F_n + F_{n+1}$$ 아래 수식의 값을 $10^9+7$로 나눈 나머지를 구하는 문제이다. $$ S(n, k) := \sum_{i=1}^n F_i \cdot i^k $$ (풀이) $k$에 대한 점화식을 세워본다. (단, $[P]$의 값은 명제 $P$가 참이면 $1$, 아니면 $0$으로 정의한다.) $$ S(n, 0) = \sum_{i=1}^n F_i = F_{n+2} - 2 = F..
Problem Solving 2021. 11. 23. 19:15

백준 온라인 저지 - 16141. 정수론과 응용: 레시테이션

https://www.acmicpc.net/problem/16141 16141번: 정수론과 응용: 레시테이션 정수론과 응용 조교를 맡게 된 청응이는 바뻐 레시테이션 문제를 준비할 여를이 없었다. 수강생들이 이번 주 수업 때 오일러 피 함수(Euler's totient function, $\varphi$)를 배운 것을 알고 어떤 $n$을 주 www.acmicpc.net 재밌는 breaktrough가 있어서 블로그에 옮긴다. (풀이) 우선 아래 식부터 정리한다. $$ \begin{align*} \sum_{m=1}^n \varphi(m, u) &= \sum_{m=1}^n \left(\sum_{k_1=1}^m \cdots \sum_{k_u=1}^m [\gcd(k_1, \dots, k_u, m) = 1] \rig..
Problem Solving 2021. 10. 11. 05:44

Dijkstra 알고리즘에 관하여

최단 거리를 빠르게 계산해주는 알고리즘이다. Negative cycle이 없어야만 정당하게 돌아간다. 일반적으로 모든 간선의 거리가 0 이상일 때 사용한다. 시작 정점에서부터 임의의 정점까지 도달하는데 필요한 거리 배열을 구한다. 처음 배웠을 때 굉장히 어려웠던 알고리즘으로 기억한다. 알고리즘이 작동하는 방식보다도 수학적인 매커니즘이나 직관을 잡는데 시간이 오래 걸렸다. 개인적으로 탐욕법과 관련된 모든 것들이 처음 습득하기가 다 어려운 것 같다.. 확실히 응용 문제를 많이 다루면서 개념이 점점 잡힌다. https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는..
Problem Solving 2020. 3. 16. 21:59

백준 온라인 저지 - 16336. Points and Rectangles

https://www.acmicpc.net/problem/16336 16336번: Points and Rectangles You need to print out q lines, the i-th line must contain one integer number — the number of pairs of rectangles and points, in which the point lies on the side or inside the rectangle. www.acmicpc.net SEERC 2018년 K번 문제이다. 2차원 정수 좌표계에서 쿼리가 $Q$개 들어온다.($Q \leq 10^5$) 초기에 점들의 집합 $P_0$와 직사각형들의 집합 $R_0$는 공집합이다. $i$번째 쿼리가 주어짐에 따라 두 집합..
Problem Solving 2020. 3. 16. 20:47

백준 온라인 저지 - 8232. Leveling Ground

https://www.acmicpc.net/problem/8232 8232번: Leveling Ground In the first line of the standard input there are three integers, n, a, b (1 ≤ n ≤ 100,000, 1 ≤ a,b ≤ 109), separated by single spaces. The number n denotes the valley's length in meters. The second line contains n integers, h1,h2,…,hn, separated by single www.acmicpc.net 미친 문제이다.. 풀이를 보고 소름 돋았던 문제. 혼자 힘으로는 못풀었다. 구글에 검색했는데 중국 사이트 풀이가 나와..
Problem Solving 2020. 3. 5. 18:02

백준 온라인 저지 - 18297. Pixels

https://www.acmicpc.net/problem/18297 18297번: Pixels Note that the order in which switches are pressed is not important, and that it is never necessary to press twice the same switch. Thus, a solution can be fully described by the set of switches pressed. There might be several solutions, i.e., several adequ www.acmicpc.net 오랜만에 아주 재미있는 문제를 본 것 같다. N*M 격자 평면의 각 좌표마다 픽셀이 있다. 각 이미지 픽셀은 B/W(Black, ..
Problem Solving 2020. 3. 1. 17:10

백준 온라인 저지 - 13970. Power towers

오일러 파이 함수(Euler's totient function)은 정수론적 함수이다. $$\phi(n) = \left| \{ 1\leq m \leq n : \gcd(m, n) = 1 \} \right|$$ 로 정의된다. 페르마 소 정리부터 오일러 정리 등 KMO에서도 많이 다룬다. 코딩에서는 어디에 쓰일까? 단적인 예로는 확장 유클리드 호제법 없이 modular inverse를 구할 때 사용된다. $a^{\phi(p) - 1} \mod p$가 바로 $p$에 대한 $a$의 modular inverse이다. 좀 더 어려운 예시로는.. https://www.acmicpc.net/problem/13970 13970번: Power towers In this example, as M = 10, we are inte..
Problem Solving 2020. 2. 21. 13:56

문자열 Hashing에 대하여

Hash는 특정 조건을 만족하는 함수이다. 정의역은 굉장히 넓고 그에 비해 치역은 좁다. 그래도 충분히 넓어서 서로 다른 정의역 원소에 대해 함수값이 충돌할 가능성이 적다. 치역은 보통 C++에서의 long long 등의 자료 형태로 표현되어 처리하기 간단하다. 그렇기 때문에 해시값이 같은 경우 두 대상은 서로 같을 확률이 아주 높다. 특히 부분 문자열에 대한 문제에서 많이 사용한다. 부분 문자열끼리 서로 완벽하게 비교하는데 걸리는 시간은 너무 오래 걸린다. 그렇기 때문에 해시값을 통해 비교와 처리를 하는 경우가 많다. 문자열 Hashing을 사용하는 문제 예시 https://www.acmicpc.net/problem/10840 10840번: 구간 성분 첫 두 줄에 신호 서열이 공백 없는 하나의 문자열로..
Problem Solving 2020. 2. 21. 00:00