키큰개발자

아이디어

입력된 숫자부터 0 까지 숫자만 출력해주면 됨. 이때 입력된 숫자는 0보다는 큼.

range(초기숫자(default:0), 끝숫자, 증감수(default:1)) <- 이 파이썬 문법을 이용해서 간단하게 거꾸로 출력

소스 코드

문제 링크 : 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=1925

해결 방법 :

nCr을 구하기 위해서 생각해보면, 

n개 중 r개를 뽑는 것은  

n개 중 먼저 하나를 보는데 이게 뽑혀져있는 상황에서 r-1개(하나가 먼저뽑혓다)를 뽑는 경우 + n개 중 하나를 먼저 보는데 이게 안뽑혀있는 상황에서 r개를 뽑는 경우의 수랑 같다는 것을 아는 것이 이 문제를 푸는 핵심인것 같다.

이제 이를 이용해서 점화식을 세운다면, 

 가 된다.

이식을 바탕으로 재귀함수를 디자인하면 된다.

기저조건은 r 부분이 0이 되거나 혹은 n과 r이 같을 때 이 두가지로 나눌수있다.

기저조건이 아닐때는 점화식대로 재귀함수를 호출해주면 된다.

문제 사이트 : http://codeup.kr/problem.php?id=3015

문제 설명 : 

n명의 학생에 대해 이름과 점수를 입력받고 주어진 조건(단, 출력순서는 점수가 높은 학생이 먼저 출력되며, 점수가 같을 경우 입력 순서가 빠른 순서로 출력한다.) 에 따라 첫번째부터 m번째 까지의 학생 이름을 출력하는 문제이다.

-입력-

4 2

Jeon 95

Kim 59

Lee 90

Bae 100

-출력-

Bae

Jeon

요롷게 되면 된다.

해결 방법 : 

구조체 설계를 할때 조건에 맞게 정렬을 하기위해서 입력된 순서를 알고있는 녀석을 추가해서 

멤버변수로 학생이름, 성적, 학생입력순서 이 세개를 갖도록 설계한다.

struct student{

char name[];

int score;

int number; // 입력순서정보!

}

그리고 sort 함수로 비교함수를 넣어서 구조체 멤버변수 기준으로 조건을 정해서 정렬시키면 원하는 답을 구할 수 있다.

여기서 비교함수를 구현 하는게 조금 애매할 수 있는데 멤버변수 두개를 비교해서 < 면 오름차순 , >면 내림차순, == 같으면 입력순서로 기호에 맞게 정렬을 시켜주면 된다.

문제링크 : 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로나눈 나머지만 갖다가 붙이면 되는것이다.

문제링크)

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

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

해결방법)

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

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

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

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

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

소스코드)

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

해결방법 :

RGB 거리의 모든 집들을 R,G,B 색으로 칠했을때 드는 최소비용을 구하는 문제인데, 나는 제일 마지막집을 때내어 생각했다. 

제일 마지막 집이 빨간색으로 칠해질 때 이웃한 집은 G, B 두가지중 하나로만 색칠해야된다.

마찬가지로 그린 이라면 이웃한 집은 R,B 두가지 중 하나로 칠해져야한다.

즉, 하나의 색깔이 정해지면 이웃한집은 그에 따라 두가지의 경우로 나눠진다.

위의 컨셉을 이용해서 점화식을 세워보면 다음과 같이 만들 수 있다.

D[N][0] = N번째 집이 빨간색으로 칠할 때,  모든 집의 최소비용 으로 정의한다. (0 : 레드, 1 : 그린, 2: 블루)

그러면 D[N][0] = min(D[N-1][1], D[N-1][2]) + rgb[N][0]  의 점화식을 세울 수 있다.

마지막집이 r,g,b 세가지의 경우를 가지기 때문에 D[N][0], D[N][1], D[N][2] 를 각각 구해서 최소값을 찾으면 답을 구할 수 있다.

소스코드)