전체 글 (116) 썸네일형 리스트형 백준 13182번: 제비 https://www.acmicpc.net/problem/13182 13182번: 제비 각 테스트 케이스마다 한 줄에 그가 잠을 자러 갈 때까지 뽑게 되는 제비 개수의 기댓값을 출력한다. 정확한 판별을 위해, 답을 기약분수로 나타내었을 때 a/b가 된다면, (a × b-1) mod 1,000,000,007을 www.acmicpc.net 이 문제 아주 어렵습니다... 일반항을 안 다음부터 구현 난이도는 너무 쉬운데 그 과정의 난이도만으로도 과거 루비5, 현재 다이아1에 위치합니다. 이 문제는 제 4회 kriiicon 에 출제된 문제이고, 같은 대회에 있던 문제 중에 제가 다룬 문제들은 다음과 같습니다. 2021.07.31 - [분할 정복을 이용한 거듭제곱/정수 거듭제곱] - 백준 13173번: Ω 2021.. 백준 11767번: Squawk Virus https://www.acmicpc.net/problem/11767 11767번: Squawk Virus Oh no! Hackers are threatening to shut down Twitface, the premier social networking site. By taking advantage of lax security protocols, nefarious cyber-bandits have developed a virus that spreads from user to user, amplifying over time and eventually brin www.acmicpc.net 왜 분할정복을 써야 하는 지 잘 모르겠습니다. $\left( T 백준 14559번: Protocol https://www.acmicpc.net/problem/14559 14559번: Protocol 메이지 나라에 사는 리샤는 전선을 이용한 통신 시스템을 만들었다. 리샤가 만든 통신 규약에 따르면 모든 전선에는 각자 정해진 용량이 있고, 전선의 용량이 $i$라는 것은, $i$개의 문자를 보낼 www.acmicpc.net 이 문제는 정말 의외로, 그래프 이론에 관한 문제입니다. 우선 용량이 $i$ 인 전선의 가치가 $112345^{i}$ 라고 주어져 있습니다. 그래서 $X$ 를 기준으로 $f\left( X \right) \; , \; g\left( X \right) \; , \; f\left( g\left( X \right) \right) \; , \cdots$ 를 다 구하려다가는, 절대 풀 수 없습니다... 백준 14289번: 본대 산책 3 https://www.acmicpc.net/problem/14289 14289번: 본대 산책 3 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 이 문제는 저번 문제를 확장한 것입니다. ( 백준 12850번: 본대 산책2 ) 풀이 방법도 똑같습니다. 저번 문제와 마찬가지로, 간선에 방향이 없어서 인접행렬이 symmetric 해야 합니다. 그렇게 구성한 인접행렬을 $D$ 제곱하면 문제가 해결됩니다. #include #define mod 1000000007 typedef struct { long long array[50][50]; } Matrix; Matrix matrix_multiply_modular (Matrix A, Matrix B, int size).. 백준 12850번: 본대 산책2 https://www.acmicpc.net/problem/12850 12850번: 본대 산책2 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 이 문제는 인접행렬의 형태가 정해져 있습니다. 그걸 그대로 구현해서, $D$ 제곱하여 정보과학관에서 정보과학관으로 가는 경로의 수를 출력하면 됩니다. 저의 경우, 위 그래프를 다음과 같이 재구성했습니다. 이 그림에서 각 번호에 대응하는 건물은 다음과 같습니다. 0 : 정보과학관 1 : 전산관 2 : 미래관 3 : 신양관 4 : 한경직기념관 5 : 진리관 6 : 형남공학관 7 : 학생회관 그 결과, 인접행렬은 다음과 같았습니다. (당연히 경로에 방향이 없으므로 symmetric 한 matrix가 됩니다.) $\be.. 백준 2099번: The game of death https://www.acmicpc.net/problem/2099 2099번: The game of death 첫째 줄에 세 정수 N(2 백준 12916번: K-Path https://www.acmicpc.net/problem/12916 12916번: K-Path 첫 번째 줄에 N, K ( 1 ≤ N ≤ 100, 1 ≤ K ≤ 109) 이 공백을 구분으로 주어진다. 다음 N개의 줄에 걸쳐 민호가 작성한 인접 행렬이 주어진다. i번 줄의 j번 수가 1이면 i번 마을과 j번 마을의 길이 있 www.acmicpc.net 글에서 제공하는 건 정확히 인접행렬의 정의와 같습니다. 따라서 행렬을 입력 받아 $K$ 제곱해주고, 각 요소의 값들을 전부 더해주면 길이가 $K$ 인 경로의 수가 됩니다. ( 기본 이론 3 ) 제 코드는 다음과 같습니다. #include #define mod 1000000007 typedef struct { long long array[100][100]; } .. 기본 이론 3 이번 글에서는 인접행렬의 거듭제곱에 대해 다루겠습니다. 인접행렬, adjacency matrix는 graph를 matrix로 나타낸 것입니다. 어떤 matrix $A$ 가 graph $G$ 의 adjacency matrix라는 것은 일반적으로 다음을 의미합니다. $G$의 임의의 두 vertices $i$ 에서 $j$ 로의 edge가 존재하면 $A_{ij}$ 의 값이 1, 그렇지 않으면 0 Adjacency matrix로 edge가 directed인 경우, weighted인 경우도 표현할 수 있습니다. directed가 아니면 $A_{ij}=A_{ji}=1$ 임이 자명합니다. 즉, $A_{ij} \ne A_{ji}$라면 directed graph일 것입니다. weighted의 표현은 간단하게 그 edge의.. 이전 1 ··· 5 6 7 8 9 10 11 ··· 15 다음