공부 정리346 [백준] 자바 1463 1로 만들기 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 접근 아래 과정을 f(x)라고 생각하면 값을 넣었을 때 f(x)를 몇 번써야 1이 되는지 출력하는 문제입니다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. dp문제이므로 문제를 잘게 쪼개어 다음 문제를 풀 수 있게끔 .. 2021. 2. 11. [백준] 자바 1010 다리 놓기 문제 재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M) 재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지.. 2021. 2. 9. [백준] 자바 1003 피보나치 함수 피보나치 함수 문제 다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다. 1 2 3 4 5 6 7 8 9 10 11 int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); } } fibonacci(3)을 호출하면 다음과 같은 일이 일어난다. fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다. fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다. 두 번째 호출한 fibonacci(1)은.. 2021. 2. 8. [알고리즘] 동적계획법(Dynamic Programing) 1. 동적 계획법이란 알고리즘 기법 중 하나로, 주어진 문제를 부분 문제로 잘게 쪼개어 해결함으로써, 궁극적으로 최종 문제를 해결하는 방법 2. 동적 계획법 사용 조건 문제를 부분문제로 나눌 수 있을 때 부분 문제들로 최종 문제를 풀 수 있을 때 3. 동적 계획법 예시 위 그림에서 보듯이 F(1) , F(0)을 구하여 최종 F(5)까지 구하여 최종답을 제시 한다. 대표 예제) 피보나치 4. 주요 특징 주로 점화식을 이용하여 푸는 경우가 많다 계산한 값을 메모리에 저장하기 때문에 속도는 빨라도 공간을 많이 차지할 수 있다. 동적 계획법 계산할 때 채우는 배열을 동적 테이블이라 함(Dynamic table) 2021. 2. 7. 이전 1 ··· 55 56 57 58 다음 반응형
