10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 읽기 어제 풀었던 문제와 비슷한 부분이 있어서 분할 정복을 빠르게 떠올렸다. 행렬 곱 식을 통해 문제를 풀었다. 문제 풀기 문제를 요약하면 행렬의 거듭 제곱 문제이다. 행렬 내가 행렬 곱을 제대로 알고 있는지 몰라서 일단 연습해봤는데 맞는 것 같다. 이렇게 계산할 수 있고, 다음과 같은 식을 얻을 수 있다. 분할 정복을 이용한 거듭 제곱 → O(logN) 두 번째로 고려할 것은 B의 크기이다. N도 최대 5로 작고, 행렬의 원소도 1000 이하이므로 작은데, B의 크기가 ..

11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 읽기 문제는 일단 조합을 구하는 문제이다. 문제는 N이 매우 크다는 것.. 수식 외에 조합을 어떻게 빨리 구할 수 있을 지를 먼저 생각했다. 첫 번째로 떠오른 것은 DP이다. C(n, k) = C(n-1, k-1) + C(n-1, k) 위 식이 떠올랐고, DP가 떠올랐다. 하지만 N이 4백만이므로, 400만 X 400만 하면 메모리가 터진다. 혹시나 해서 해봤지만 역시나 터졌다. 수식으로 접근 C(n, k) = n! / (k! * (n-k)!) 위 식을 계산하여 풀 수 있을까 했는..

1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 문제 읽기 문제를 읽어보면 결국 사람은 두 분류로 나뉘게 된다. 지민이의 (진실을 아는 사람 + 알게 될 사람 / 전혀 모를 사람) 이 두 분류만 확실하게 구분하면 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티의 최대 개수를 구할 수 있을 것이다. 진실을 아는 쪽이 하나라도 포함되어 있는 파티에서는 거짓말을 치지 못할 것이고, 그 외에 전혀 모를 사람에게는 거짓말을 칠 수 있을 것이다. 이러한 부분을 봤을 때, 유니온 파인드를 쓰면 빠르게 해결할 수 있..

1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 문제 읽기 유니온 파인드를 모른 채로 이 문제를 처음 봤다면 인접 리스트 만들어서 DFS로 그래프 탐색을 했을지도 모른다.. 하지만 지금은 유니온 파인드를 알기 때문에, 훨씬 단순하게 생각할 수 있었다. 유니온 파인드의 개념이 궁금하면 다음 글을 참고하고 오면 좋다. 분리 집합, Disjoint Set : Union-Find 분리 집합, Disjoint Set 💡 분리 집합, Disjoint Set = 서로소 집합 분리 집합이란 이미 존재하는 집합 U에 대해, ..

1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 문제 읽기 이전이었으면 이게 뭐지.. 하면서 끙끙댔을 테지만, 어제 유니온 파인드를 공부했기 때문인지, 읽자마자 이건 그냥 유니온 파인드라는 생각이 들었다. 유니온 파인드에 대해 개념을 알고 싶으면 우선 이 포스팅을 먼저 보고 오길 추천한다. 분리 집합, Disjoint Set : Union-Find 분리 집합, Disjoint Set 💡 분리 집합, Disjoint Set = 서로소 집합 분리 집합이란 이미 존재하는 집합 ..

3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 문제 읽기 처음에 문제를 읽었을 때는 일반적인 시뮬레이션 문제 같았다. 단순하게 생각하면 다음과 같은 구조로 풀이를 할 수 있을 것이다. 모든 판을 순회하며 물과 인접한 얼음에 없앤다는 표식을 남긴다 다시 모든 판을 순회하며 표식이 있는 얼음을 녹여 물로 만든다 위 과정이 끝났으면 백조 한 마리의 위치에서 BFS를 수행하여, 물로만 이동했을 때 다른 백조까지 도달하는 지 파악한다 두 백조가 만났다면 끝내고, 만나지 않았지만 1-3 과..