Algorithm

[BOJ/JAVA] 23631번: 진심 좌우 반복뛰기

키워드위치 x = 0에서 시작하여, 처음에는 오른쪽으로 Km를 뛴 다음 방향을 바꾼다.방향을 바꿀 때마다 이전에 움직인 거리에 Km만큼 더한 거리를 뛰고, 다시 방향을 바꾼다.정확히 (N - 1)m만 뛸 것구현다음을 정의하자. 전부 뛴다 → 해당 뛰여야할 길이만큼을 전부 뛴다.n전부 뛴 횟수전부 뛸 수 있는 n값을 구한다.low = 0high = 5000(5000)(5000+1)/2 ≥ 10,000,000 이므로 5000을 상한선으로 정했다.n을 매개변수로 하여, 이분 탐색으로 진행한다.숫자가 매우 크므로, java에서는 BigInteger를 활용한다.n번째에서 전부 뛰었을 때 위치는 다음과 같다.이동 횟수좌표1K2-K32K4-2K53K6-4K위 표에서 알 수 있듯이 이동횟수를 보면, 좌표를 알아낼 수 ..

동적 계획법

동적 계획법이 뭔데?분할 정복에서 중복 부분문제를 캐시(cache)를 이용하여 계산 결과를 재활용하여 속도 향상을 꾀하는 기법이다.예시피보나치 수열의 [i]번째 결과값을 출력하고싶다고 하자.해당 메소드는 fibo(i)를 이용하여 값을 얻는다.int fibo(int i){ // 기저사례 if(i == 0 || i == 1){ return 1; } if(cache[i] != -1){ return cache[i]; } cache[i] = fibo(i-1) + fibo(i-2); return cache[i]; }초기 cache 상태는 다음과 같다.fibo(4)는 fibo(3) + fibo(2) 연산이 이루어진다.fibo(3)에서는 fibo(2) + fibo(1) 연산이 이루어진다.fibo(2)에서는 fibo(1..