키큰개발자

문제 링크 : https://www.acmicpc.net/problem/1699

해결 방법 :

이 문제는 다이나믹 프로그래밍 문제다.

그렇기 때문에 먼저,

우리가 구하고자 하는 문제가 뭔지 본다. 

문제는 주어진 자연수 N을 제곱수들의 합으로 표현할 때에 그 항의 최소개수 이다. 

ex) N = 3  , 1^2 + 1^2 + 1^2 = 3개 

    N = 7,  3^2 + 1^2 + 1^2 = 3개

나는 처음에 접근한 방법이 제곱을 했을때 (N 과 가장 가까운 수에 대해 최소항의 개수  + N- 가장가까운수 에대한 최소항의 개수) 로 점화식을 세워서 풀었었다. 하지만 이는 12를 구할때 깨져버린다. 

위점화식을 적용해보면, 9의 최소항의개수 + 12-9의 최소항의개수 = 4가 나오게 된다.

2^2 + 2^2 + 2^2 = 3개 이것이 최소개수인데 말이다. ㅜㅜ

다시 생각해 본 후 , 모든 경우를 고려하면 답을 구할수 있다고 봣다.

즉, 어떤 수 12는  제곱의 합에서 1의 제곱이 포함됬다고 보면 11의 최소항의개수 + 1 이 될것이다. 여기서 +1 은 1의 제곱이 포함됬기 때문이다.

12는 또 제곱의 합에서 2의제곱이 포함됬다고 보면 10의 최소항의 개수 + 1 이 된다.

12는 또 제곱의 합에서 3의 제곱이 포함됬다고 보면 9의 최소항의 개수 + 1이 된다.

이렇게 모든 경우를 포함하는 점화식을 세운다면 DP[N] = MIN ( DP[N], DP[N-j의제곱] + 1)  이될것이다.

(이때, j는 제곱해서 N보다 같거나 작을때까지의 수를 반복해서 도는 경우이다.)

문제링크)

- http://codeup.kr/problem.php?id=3733

해결방법)

어떤 임의의 자연수 n 을 입력받고 홀수 or 짝수 일때의 각각의 규칙에 따라 재귀함수를 호출한다.

이때 재귀함수 호출 횟수가 몇번인지가 문제에서 말한 우박수의 길이가 되고 이것을 구하면 된다.

규칙은 다음과 같다.

1. 어떤 자연수 n이 입력되면,

2. n이 홀수이면 3n+1을 하고,

3. n이 짝수이면 n/2를 한다.

4. 이 n이 1이 될때까지 2~3과정을 반복한다.

예를 들어 5는 5 → 16 → 8 → 4 → 2 → 1 이 된다.

여기서 생각해야할 부분이 있는데, 입력이 자연수 a, b 구간으로  1<= a <= b <= 10,000,000 의 아주 큰 범위를 갖는다.

그래서 이 문제가 large 버전으로 이름이 붙여진 것 같다.

이 큰 값의 범위 입력을 풀기 위해서 대표적인 방법으로 메모이제이션을 써서 시간복잡도를 줄여야 겠다는 생각을 했다.

그리고 코딩하면서 알게 된것이 배열을 천만으로 선언할 수 있다는 것을 알 수 있었다. 너무 비효율적이라 생각되는데 무튼 문제만 푼다면야...하고 일단 넘어가자.

메모이제이션을 할때 천만으로만 하기 때문에 n이 홀수여서 천만의 값을 넘어간다면 이는 따로 조건을 추가해서 메모이제이션을 안하고 다음 재귀함수를 그냥 호출 하는 방식으로 구해보았다.

문제 링크 : https://www.acmicpc.net/problem/1932

해결 방법 :

제일 단순하게 처음 시도했던 방법은 완전탐색으로 왼쪽합누적, 오른쪽 합누적 하는 방법으로 n번째 줄까지 전부 구했었다.

그리고 n번째줄에서 모든 합들을 비교해서 최대값을 찾아서 출력했었는데, 시간초과로 틀렸었다. 알고보니 2의 n승의 시간복잡도....ㅜ

그래서 다이나믹프로그래밍의 메모이제이션 기법을 사용해야겠다는 생각을 했다. 왜냐 시간초과니까 ㅜ

시간을 줄일방법을 생각해보니까 재귀를 줄여야겠다고 생각했다.

재귀를 줄이려면 각각의 요소가 최대값을 가져야했고 그거를 재호출했을때 미리 저장해놓은 최대값을 툭 내뱉어버리면 다시 재귀호출을 안할수 있다고 생각했다.

그래서 n번째 줄에서 부터 거꾸로 찾아나갔다. (top-down 방식)

n번째줄의 i번째 요소까지의 최대값은 max(n-1번째줄의 i번째 최대값, n-1번째줄의 i-1번쨰 최대값) + n번쨰줄의 i번째요소값 의 점화식으로 구할 수 있었다.

그리고 이를 기록해야한다. 왜? 재호출 방지위해서

식으로보면, d[x][y] = max(solve(x-1,y), solve(x-1,y-1)) + a[x][y] 이다.

또한, -1은 범위밖에있는 것들을 미리 저장해놔서 그곳에 호출하려하면 0을 리턴한다.  왜냐? 존재하지 않는 값이니까..

문제링크 : https://www.acmicpc.net/problem/7490

해결방법 : 

1 부터  N까지 -, +, " " 의 연산을 사이에 각각 넣어서 최종 합이 0이 되는 식을 모두 출력하는 문제다.

일단 식을 누적하는 변수 str, 최종합을 누적하는 변수 sum을 설정하고 생각해봤다.

자연스레 3가지경우에 대해 재귀호출을 하면 모든 경우를 만들 수 있기에 3가지의 재귀함수를 설계하면 답을 구할 수 있다.

여기서 ""연산에 대해 주의할 점이 있는데, 

다음 재귀에 +나 -를 만나면 이전의 값(num)을 sum에 더해주거나 빼준다. 그전에는 sum에 아무런 계산하지 않는다.

이말은 ""로 된부분은 num에 합쳐진숫자로 업데이트만 하고, 다음에 +나-가 오면 계산을 해준다는 것이다.

나머지 -, +의 경우에는 다음에도 -,+일때 sum에 num*sign 값을 더해준다. 참고로 sign을 곱해주고 더해주면서 뺄셈을 한다. 

재귀함수로 넘겨주는 값을 보면 이해가 될것이다.

소스코드)

문제 링크 : https://www.acmicpc.net/problem/1003

해결 방법 :

피보나치 함수를 재귀함수, Top-down 방식으로 푼다고 했을 때 fibonacci(0), fibonacci(1) 의 호출 개수를 각각 출력하는 문제다.

처음에는 단순히 

if(n == 0) 일때 0의 카운트 증가,

if(n == 1) 일때 1의 카운트 증가로 바로 풀수가 있었는데 채점해보니 시간초과가 떴다.. ㅋ

아 그러면 익히알고있는 다이나믹프로그래밍으로 메모를 쓰고 읽어서 시간을 줄여야 되는 구나라고 생각했다.

테스트 케이스를 가지고 여러번 하다보니 다음과 같은 규칙을 발견했다.

N의 0호출 개수는 N-1의 1호출 개수라는 것

example)  5의 0의 호출개수 = 4의 1의 호출개수, 다른것도 직접해보면 알것이다.

따라서 N과 N-1의 피보나치함수를 호출하고 N==1일때 1의 카운팅을 리턴하여서 각각 총 1의 호출개수를 각각 구할 수 있었다. 

이때, 재귀함수에서 여러 N의 1의호출개수를 메모로 저장해둬서(d[N]) 시간을 줄였다.

소스코드)

문제 링크 : https://www.acmicpc.net/problem/14891

해결방법)

문제를 읽고나서 생각해 봣는데 각 명령마다 순차적으로 톱뉘를 돌려나가면 되겠다라고 생각했다.

즉, 단순구현으로 풀었고(소스가 더러운느낌,..) 톱니번호와 회전방향을 가지고 있는 그대로 코드를 짜보았다.

- 알고리즘 순서 

1. 톱니 바퀴 정보를 입력받는다.

2. 각 명령을 하기 직전에 톱니들 사이의 접합부분이 맞닿았는지 혹은 떨어졌는지를 확인한다

3. 명령마다 주어진 바퀴번호와 회전방향을 보면서 해당 바퀴번호 기준으로 접합정보를 차례대로 비교해 나가면서 바퀴를 회전 시켜준다.

4. 명령이 끝날때까지 2,3번을 반복하고 반복이 끝나면 답을 구해줄 수 있다.

소스코드)