키큰개발자

문제링크 : http://codeup.kr/problem.php?id=3704

해결 방법 :

n 이 5라면은 다음과 같이 총 13가지 경우의 수를 알 수 있다.

5=1+1+1+1+1

5=1+1+1+2

5=1+1+2+1

5=1+2+1+1

5=2+1+1+1

5=1+1+3

5=1+3+1

5=3+1+1

5=1+2+2

5=2+1+2

5=2+2+1

5=2+3

5=3+2

이걸 보고 생각해보면 5를 도달하기 직전 시점에서 보면 한 칸 전에오는 경우의수 가 있을 것이고, 두 칸 전에 오는 경우의 수도 있을거고 그리고 세 칸전에 오는 경우의 수가 있을것이다.

그렇다면 n에 도달하는데 모든 경우의 수는 n-1까지 오는데 경우의수 + n-2 까지 오는데 경우의 수 + n-3 까지 오는데 경우의수로 모든 경우를 다 합해주면은 원하는 답을 구할 수 있다.

이렇게하면 정답은 구할수 있지만, 이렇게 모든 경우를 세주면은 하나의 경우에있어서 계속 3가지의 경우의수가 발생이 되므로 3의 n승이라는 어마어마한 시간이 걸려서 틀리게 된다.

따라서, 중복되는 경우를 세주지 않게하기위해서 memo라는 배열에 n에 도달하는 경우의수를 미리 기록해둔다.

그렇게되면 일단 n이 1씩계속 감소하며 모든경우를 구하게 되고 n-2, n-3으로 부르는 재귀함수는 n-1의 재귀함수에 모두 포함되므로 경우의수가 확 줄어들게 된다. 

이제 코드를 작성해 보면 다음과 같다.

<해결 방법>

이 문제는 정수 n 을 입력받아서 2진수로 출력하는 문제이다.

예를들어 12라는 숫자가 입력되면 

1100 이 출력되면된다.

이 문제를 재귀함수로만 풀어야 하는 조건이 있기때문에 재귀적인 패턴을 먼저 찾아야한다.

우리가 일반적으로 2진수를 변환할때를 생각해보면, 12를 일단 2로 쭊쭉쭉 계속 나눠본후 나머지를 거꾸로 이어서 붙여주면 2진수가 완성된다.

이때, 12를 2로나눠서 생긴 나머지에 2로나눈 몫인 6을 다시 2로 쭉쭉쭉 나눠서 생긴 나머지와 붙여준다면 2진수가 완성된다.

이걸 그림으로 표현해 보면 다음과 같다. (그림 잘 못그림 ㅜ)

이걸보면 재귀적 패턴을 알수있다.  

string getBinaryNum(int n) : n을 입력받아 2진수를 반환하는 함수  라고 정의를 한다면, 

getBinaryNum(n/2) + (n % 2)  <- 이 식의 의미는 현재 n의 2를 나눈 나머지를 n/2로 나눈 숫자의 2진수를 반환하는 것에 갖다 붙인다. 즉, 원래 n에 대한 2진수를 반환할 수 있게된다. 

요약하자면 재귀함수가 n/2에 대한 2진수를 반환해줄거니까 우리는 이거에 현재 n을 2로나눈 나머지만 갖다가 붙이면 되는것이다.

문제 링크 : 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을 리턴한다.  왜냐? 존재하지 않는 값이니까..

문제링크) http://codeup.kr/problem.php?id=2606

해결방법)

분자와 분모가 주어지는데 실제 나누기를 해보면 소수점 이하부분만 출력하기위한 규칙이 보여진다.

처음에는 단순하게 생각할수있는 것이 실제 나눠봐서 정수부분을 빼고 *100억을해서 출력해서 정답이었지만,

모범답안은 그렇지 않았다.

항상 분자를 분모로 나눈 나머지 *10 에서 분모를 나눈 몫이 소수점 이하 부분의 값이었다.

이를 10번만 반복하면 소수점 이하 10번쨰자리까지 구할 수 있게 된다.

소스코드)

문제 링크 : 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]) 시간을 줄였다.

소스코드)

우연히 알고리즘 잡스에 대한 광고를 보고 호기심이 생겨 미루고 미루던 상담을 드디어 오늘 받게 되었다.

워낙에 요즘 대기업들이 sw 직군을 뽑을때, 코딩테스트를 본다. 여기서 이 코딩테스트를 도와주는 곳이 바로 알고리즘 잡스라는 곳이다.

솔직히 나는 알고리즘 강의나 학원을 잘 믿지는 않는편인데 (머 다른것도 잘못믿지만) .. 구글링이나 네이버에 이 학원명을 치면 좋은글들 뿐이고, 광고또한 솔깃햇어서 이게 대체 뭔가 해서(내눈으로 직접보고 정체를 알기위해 ㅋㅋ) 무거운 발걸음을 옮겼다....

긴 말 안하고 상담 받고 난 후의 느낌을 한문장으로 쓰고 포스팅을 마치겠다.