문제사이트 : 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이 홀수여서 천만의 값을 넘어간다면 이는 따로 조건을 추가해서 메모이제이션을 안하고 다음 재귀함수를 그냥 호출 하는 방식으로 구해보았다.

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

해결방법)

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

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

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

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

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

소스코드)

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

해결방법 :

정수 n이 입력으로 들어오면 1부터 n까지의 합을 재귀함수로 구현해야한다.

따라서 재귀함수를 구현하기 위해 다음을 설계해야한다.

1.기저조건

2.재귀처리구문 

기저조건은 입력 n이 1이하인 것이고 그때는 n을 리턴한다.

재귀처리는 n(현재 숫자) + f(n-1) (하나 전의 숫자까지의 1부터 총합) 을 하면 우리가 구하고자하는 1부터 n까지의 합을 구할 수 있다.

여기서 재귀함수인 f(n-1)은 우리가 원하는 값을 리턴해준다는 것을 가정해두고 설계한다. (실제 직접따라 들어가보면 값을 구해준다. 신기신기)

이렇게 가정하고 설계해도 답을 구하는 것은 귀납적인 식으로 설정해두었기 때문에 오류가 안나는 것이다.

그 이유는 기저조건을 세웠고(처음오는 자연수에 대한 증명), f(n-1)과 f(n)은 같은 방식(n이만족되면 n+1도 맨족..)으로 구해나가기 때문에 귀납적 증명을 한 것과 동일하기때문이다. 

다음 수학 귀납법 설명 참조

모든 자연수가 어떤 성질을 만족시킨다는 명제에 대한 수학적 귀납법을 통한 증명은 다음과 같은 두 단계로 구성된다.

1. 처음 오는 자연수(0 또는 1)에 대한 증명
2. $${\displaystyle n}이 만족시킨다는 가정 아래, $${\displaystyle n+1}에 대한 증명

소스코드)

캔디팡 문제 링크 : http://codeup.kr/JudgeOnline/problem.php?id=2605

해결 전략)

2차원 맵정보가 있는데 각 좌표마다 방문하면서 4방향(상,하,좌,우)에 인접해있는 모든 개수정보를 알고 결국, 인접해있는개수가 3개이상이면 카운팅을 해줘서 답을 구할수있다.

예를 들어서 그린 그림입니다.

여기서 인접해 있는 것이 보인다면 그 곳으로 좌표이동하고 다시 4방향으로 인접해 있는 개수정보를 파악한다.

이 작업을 모든 맵 좌표를 방문하면서 체크하게 된다. 단, 방문이 된 곳은 체크를 따로해줘서 재탐색이 이뤄지지 않도록 한다.

소스코드)