rimugi

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

해결과정선분 교차 알고리즘이라는 것을 몰랐던 처음에는 float을 이용하여 다양한 규칙을 세우며 도전해 보았지만 너무 복잡하였고 구현하여도 실패하였다. 곰곰히 생각해 보니 이 문제는 소수를 사용하면 안되는 문제라고 판단하였고 여러 가정을 생각하다 결국에는 구글에 선분 교차 알고리즘을 검색해 보게 되었다. 예전에 실발끈 공식을 위해 외적을 2차원 공간에서 다루는 것을 보았었는데 이 문제또이 이를 이용하여 해결하는 문제였다 어떤 점 p1, p2, p3, p4가 있을때 p1, p2, p3 을 p1p2, p2p3벡터로 만든뒤 z는 0으로 외적을 하면 z는 서로 평행일때 0 그외에는 1 또는 -1값을 나타내는데 p1, p2 ,p3 은 1 p1, p2 , p4는 -1일 경우 p1, p2를 기준으로 p3, p4는 서..

해결과정 - 사이클 찾기단순 사이클 찾기 문제라는 것을 깨닳고 재귀를 사용하려고 했으나 비슷한 유형의 문제를 너무 많이 풀어봐서 이번에는 반복문으로 해결해 보고 싶다는 생각이 들었다. 그래서 배열 담는 용도인 arr, 방문체크 목적인 visited, 사이클의 원소 수를 체크하기 위한 depth 배열을 구성하였다. 여기에서 visited의 값으로 현재 순환중인 노드의 첫번째 값 예를들어 1번째 노드부터 시작하여 순환하고 있으면 1번째 노드의 값을 넣어줌으로 써 다음번 순회를 돌경우 방문한 곳이 사이클로인해 방문한 곳인지 아님 전에 방문하여 못가는 곳인지 체크하도록 하였다 #include #include #include #include #define FAST ios::sync_with_stdio(0), ci..

해결과정 - DP첫번째 방법 무식하게 푸는 방법은 모두가 생각한듯이 S, E가 주어졌을때 {S, E} {S - 1, E - 1} 이런식으로 비교를 해가며 푸는 방식이다 하지만 질문 M이 많을경우 약 n^2 * m의 시간복잡도가 발생하게 된다 두번째 방식은 S와 E의 값이 같을때 S와 E의 안쪽이 팰린드롬이면 S 와 E도 팰린드롬이라는 것에서 미리 팰린드롬 보드를 제작할수 있다 1일때는 팰린드롬임이 분명하고 2일때부터 위의 발상을 적용할 수 있다 위를 표현하면if(S == E) 일때 board[Length][Start] = board[Length - 2][Start + 1] 이라는 공식이 나오게 된다계산의 편리성을 위해 board는 1부터 시작하도록 구성하였다 #include#include#include#..

해결과정처음 생각은 인간의 기초 상식으로 접근하여 각 칸마다 순회를 하며 반드시 특정 숫자여야 되는곳 ex) 가로 세로 square부분을 고려했을때 특정 숫자 만 되는 경우 값을 채우는 형식으로 하였지만 문제 조건에 맞지 않고 그런공간이 없을시 실패하는 당연한 실패였다 두번째 도전은 탐색을 떠나자 라는 식으로 재귀함수를 이용해 탐색을 하였는데 성공했다..솔직히 시간초과를 각오하고 그냥 해본건데 성공해서 찜찜한 문제여서 질문을 남겼다 답변이 돌아온다면 다시 후기에 그 이유를 적어보겠다 #include#include#include#include#include#include#include#include#include#include#include#include#define Fast ios_base::sync_w..

해결과정 - 투포인터왼쪽과 오른쪽을 비교해가며 두 값의 합이 가장 0에 가까운 값을 알아내는 문제라는 것을 파악하였고 한가지 왼쪽을 증가할지 오른쪽을 감소할지를 결정하는 일만 남았다. 결론은 두 값의 절대크기를 비교하여 절대크기가 큰 쪽의 값을 증가시키거나 감소시키는 것다3가지 경우의 수가 있는데1. 왼쪽수는 음수 오른쪽 수는 양수일경우 : 절대크기가 작은쪽을 이동하면 0에서 멀어진다2. 둘다 음수 : 절대크기가 작은쪽을 이동하면 0에서 멀어진다3. 둘다 양수 : 위와 같다 로 나올수 있는 모든 경우의 수에서 절대크기가 큰쪽의 값을 이동해야 된다는 결론이 나왔다 솔직히 감각적으로 알긴했는데 항상 알고리즘은 증명이 필요하다고 개인적으로 생각한다 #include#include#include#include#i..

해결과정문제를 보자마자 이건 신발끈 공식을 사용하는 거라는 생각이 들었고 역시 맛았다. 이 생각이 든 김에 신발끈 공식을 정리해보았는데 두 벡터가 있을때 두벡터의 외적이 두벡터가 이루는 사다리꼴의 넓이라는 것을 수식을 통해 증명한뒤삼각형의 넓이가 1/2 두벡터의 외적크기라는 것을 증명한뒤 다각형을 여러개의 삼각형으로 분리하고 각각의 삼각형의 넓이를 계산하는 방식이 신발끈 공식이였다. 의식의 흐름대로 정리하긴 했지만 방법을 알고 증명을 알면 내가 아는 거니깐 다음번에도 이런문제는 쉽게 풀수있을거같다 #include#include#include#include#include#include#include#include#include#include#include#include#define Fast ios_base..