rimugi

핵심 : 중간에서만나기큰 부분을 두가지의 갈래로 잘라 계산한뒤 이 두개의 부류를 비교 계산한다는 의미이다 조금 쉬운 버전으로는 https://www.acmicpc.net/status?problem_id=16287&language_id=1001&from_problem=1&top=91671698이 문제가 있다 하지만 현재 문제가 왜 플레냐? 분류해서 풀면 시간초과가 걸린다 ㅎㅎ. 1. unordered_map으로 분류 미리 2가지로 계산되는 합들을 저장해둔뒤 가능한 배치들을 서로 비교해 본다.-> 원인은 map의 오버헤드라고 생각되는데 제대로 몰라서 질문을 남겨놨다. 고수분들이 해결해 주면 답을 남겨보겠다.-> map의 접근은 일반 배열보다 10배정도는 느리다고 한다 c++ 코드를 접근해서 확인해보면-> 실..

해결 방법이번 문제는 비트마스킹과 **DP(동적 계획법)**을 활용하면 효과적으로 해결할 수 있습니다.고려해야 할 두 가지 핵심 개념큰 수의 나머지를 어떻게 구할 것인가?n!이나 되는 경우의 수를 어떻게 효율적으로 구할 것인가?1. 큰 수의 나머지 계산큰 수의 나머지를 직접 계산하기 어려울 때는 다음 성질을 활용하면 편리합니다.이 공식을 활용하면 나머지를 효율적으로 계산할 수 있습니다.2. 경우의 수 계산 (DP + 비트마스킹)n이 최대 15 이하의 작은 값이라면, 비트마스킹과 메모이제이션을 활용하여 중복 계산을 방지할 수 있습니다. 이미 방문한 부분집합이라면, 해당 지점에 미리 계산된 값을 저장해 두어 빠르게 결과를 가져올 수 있습니다.이러한 원리를 바탕으로 코드를 작성하면 문제를 효과적으로 해결할 수..

강한 연결 요소(SCC) 찾기: 유니온 파인드 & 코사라주 알고리즘이 문제를 해결하는 대표적인 방법은 두 가지가 있습니다.1️⃣ 타잔(Tarjan) 알고리즘2️⃣ 코사라주(Kosaraju) 알고리즘이번 풀이에서는 최종적으로 코사라주 알고리즘을 사용하였습니다.1. 첫 번째 접근: 유니온 파인드 + DFS처음에는 위 알고리즘을 알지 못한 상태에서,🔹 유니온 파인드와 DFS 탐색을 조합하면 해결할 수 있지 않을까? 🤔 라고 생각했습니다.✅ 접근 방식1️⃣ DFS를 이용하여 사이클을 찾는다.2️⃣ 사이클이 발견되면, 유니온 파인드를 이용해 해당 노드들을 결합한다.3️⃣ 탐색되지 않은 노드를 찾아 1~2 과정을 반복한다.4️⃣ 같은 그룹에 속한 노드들을 map을 이용해 관리하고 출력한다.❌ 실패 원인이 방식으..

pow 함수는 매우 유용하지만, 사용할 때 주의해야 할 점이 있습니다.1. pow 함수의 반환 타입pow는 double 타입을 반환하며, double은 정수부가 최대 15자리까지 표현됩니다.즉, 15자리를 넘어가는 값을 다루기 시작하면, 정확한 값을 보장하지 못할 가능성이 높습니다.이로 인해 원하는 결과를 얻지 못할 수도 있으므로, 정확한 정수 계산이 필요할 때는 다른 방법을 고려해야 합니다.2. 해결 방법정수 연산을 보다 정확하게 수행하려면 다음과 같은 방법을 사용할 수 있습니다.✅ Fast Exponentiation (빠른 거듭제곱, fastpow) 직접 구현✅ 2의 거듭제곱인 경우, 비트 연산 (1LL 이렇게 하면 double 타입에서 발생하는 부동소수점 오차 문제를 피할 수 있습니다.3. 오버플로..