본문 바로가기

전체 글548

백준 11444 c++ "피보나치 수 6" -PlusUltraCode- https://www.acmicpc.net/problem/11444[필자 사고]자 왜우자. 주어진 숫자가 말도 안되게 크다?? 이분 탐색 분할정복 이런식으로 logN 시간복잡도로 이용해야 되는 문제다.반드시 해당 문제는 어느정도 수학을 알고 있어야 된다.f(2k) = f(k){2*f(k+1)-f(k)} 와 f(2k+1) = f(k)^2 + f(2k)^2 의 형태로 구할 수 있다.즉 fib(n/2) 로 탐색을 하면서 반환값을 f(k)와 f(k+1) 형태로 반환해주고 재귀 형태로 구해나가면 문제를 풀 수 있다.[코드 해설]문제 개요피보나치 수열은 0과 1로 시작해,각 항이 이전 두 항의 합으로 정의되는 수열입니다.하지만 이 문제에서는 입력 n이 최대 10¹⁸에 이를 수 있으므로,일반적인 반복문이나 DP로는.. 2025. 10. 19.
백준 14391 c++ "종이 조각" -PlusUltraCode- https://chatgpt.com/c/68f185ee-3028-8320-b601-4756c1a10fb7[필자 사고]N과 M의 크기를 보았따. 최대 4다. 즉 브르트 포스 알고리즘이다. 다막 막 하려면 막막하다. 각각의 위치를 1과 0으로 생각하고 1 1 10 1 01 1 1 이라고 생각을 해보자. 1들의 집합은 가로 형태로 0은 세로 형태라고 생각을 해보자.그렇다 비트마스킹으로 경우의 수를 나눌수 있었다. 여기서 조심해야 될 점은 마지막 sum을 또 더해줘야 된다. 필자 사고 과정을 잠시 적겠다.mask =0에서 시작하여 최대 (1 가로 형태에서 1들의 모여잇는걸 찾기 위해 반복문 시행세로 형태도 마찬가지 idx = i*M+k; 형태를 이용하여 현재 몇번째 배열인지 순서대로 찾는다.해당 idx를 (1만.. 2025. 10. 17.
백준 1726 c++ "로봇" -PlusUltraCode- https://www.acmicpc.net/problem/1726[필자 사고]처음에 DFS로 모든 경우의 수를 고려해야 하나?? 생각했는데 단순히 visited를 한차원 늘려 방향까지 기록하게되면 BFS로 충분히 풀 수 있었다.이 문제에서 조심해야 될 부분은 i=1~i=3 까지 이동할 때 병이나 이동할수없는 구간을 만나게 되면 반드시 break을 해줘야한다.예를들어 2에서 벽이 있는데 3에는벽이 없을경우 탐색을 한 경우로 쳐지게 된다.사전에 차단해야 된다.놓치기 쉬운 부분이니 조심하자. 아래는 자세한 코드 해설이다.[코드 해설]1. struct NodeNode 구조체는 로봇의 현재 상태를 표현한다.구성 요소는 다음과 같다:sero: 세로 좌표 (행)garo: 가로 좌표 (열)dir: 현재 바라보는 방향 .. 2025. 10. 17.
백준 14786 c++ "Ax+Bsin(x)=C ②" -PlusUltraCode- https://www.acmicpc.net/problem/14786[필자 사고]이분 탐색으로 매개변수 탐색이라는 것을 알고 있었다.그러나 지금껏 정수 범위 내에서만 매개변수 탐색을 해와서 정확한 값을 도출이가능했는데 소수 범위다. 이럴 경우 적당히 많이 해서 추정치로 접근해야 된다는 것을 알았다. 사고의 확장을 준 문제다.[코드 해설]1. 문제 접근 개념식 Ax+Bsin⁡(x)=CA x + B \sin(x) = CAx+Bsin(x)=C를 다음과 같이 바꿀 수 있다.f(x)=Ax+Bsin⁡(x)−Cf(x) = A x + B \sin(x) - Cf(x)=Ax+Bsin(x)−C여기서 우리가 찾아야 하는 것은 f(x)=0f(x) = 0f(x)=0을 만족하는 xxx이다.이 함수는 A>0A > 0A>0이기 때문에 .. 2025. 10. 15.

티스토리툴바