Skip to content

README.md

Latest commit

 

History

History
837 lines (679 loc) · 11.9 KB

README.md

File metadata and controls

837 lines (679 loc) · 11.9 KB

CodeUp > ProblemSet

Recursion

2023.10.16

https://codeup.kr/problemsetsol.php?psid=21

<List>

1901. (재귀 함수) 1부터 n까지 출력하기

Test Input & Output

Input

10

Output

1
2
3
……
10
Codes (C++)

C++

#include <iostream>

#define endl '\n'

using namespace std;
void recursion(int n, int cnt)
{
    cout << cnt << endl;

    if (n == cnt)
        return;
    else
        recursion(n, cnt + 1);
}
int main()
{
    int n, cnt = 1;
    cin >> n;

    recursion(n, cnt);

    return 0;
}

Submissions

정확한 풀이

1902. (재귀 함수) 1부터 n까지 역순으로 출력하기

Test Input & Output

Input

10

Output

10
9
8
……
1
Codes (C++)

C++

#include <iostream>

#define endl '\n'

using namespace std;
void recursion(int n, int cnt)
{
    cout << cnt << endl;

    if (cnt == 1)
        return;
    else
        recursion(n, cnt - 1);
}
int main()
{
    int n;
    cin >> n;

    int cnt = n;
    recursion(n, cnt);

    return 0;
}

Submissions

정확한 풀이

1904. (재귀함수) 두 수 사이의 홀수 출력하기

Test Input & Output

Input

2 7

Output

3 5 7
Codes (C++)

C++

#include <iostream>

#define endl '\n'

using namespace std;
void recursion(int a, int b)
{
    if (a % 2 == 1)
        cout << a << ' ';

    if (a >= b)
    {
        cout << endl;
        return;
    }
    else
        recursion(a + 1, b);
}
int main()
{
    int a, b;
    cin >> a >> b;

    recursion(a, b);

    return 0;
}

Submissions

정확한 풀이

1905. (재귀함수) 1부터 n까지 합 구하기

Test Input & Output

Input

100

Output

5050
Codes (C++)

C++

#include <iostream>

#define endl '\n'

using namespace std;
void recursion(int n, int m, int sum)
{
    sum += m;

    if (n == m)
    {
        cout << sum << endl;
        return;
    }
    else
        recursion(n, m + 1, sum);
}
int main()
{
    int n;
    cin >> n;

    int m = 1, sum = 0;
    recursion(n, m, sum);

    return 0;
}

Submissions

정확한 풀이

1912. (재귀함수) 팩토리얼 계산

Test Input & Output

Input

5

Output

120
Codes (C++)

C++

#include <iostream>

#define endl '\n'

using namespace std;
void factorial(int n, int prod)
{
    prod *= n;

    if (n == 1)
    {
        cout << prod << endl;
        return;
    }
    else
        factorial(n - 1, prod);
}
int main()
{
    int n;
    cin >> n;

    int prod = 1;
    factorial(n, prod);

    return 0;
}

Submissions

정확한 풀이

1915. (재귀함수) 피보나치 수열

Test Input & Output

Input

7

Output

13
Codes (C++)

C++

#include <iostream>

#define endl '\n'

using namespace std;
int Fibonacci(int n)
{
    if (n <= 2)
        return 1;
    else
        return Fibonacci(n - 1) + Fibonacci(n - 2);
}
int main()
{
    int n;
    cin >> n;

    cout << Fibonacci(n) << endl;

    return 0;
}

Submissions

정확한 풀이

1916. (재귀함수) 피보나치 수열 (Large)

Test Input & Output

Input

7

Output

13
Codes (C++) - Trial 1

C++

#include <iostream>

#define endl '\n'

using namespace std;
int Fibonacci(int n)
{
    if (n <= 2)
        return 1;
    else
        return (Fibonacci(n - 1) % 10009 + Fibonacci(n - 2) % 10009) % 10009;
}
int main()
{
    int n;
    cin >> n;

    cout << Fibonacci(n) << endl;

    return 0;
}
Codes (C++) - Trial 2 : Use Memoization

C++

……
#include <vector>

……
vector<int> memo;
int Fibonacci(int n)
{
    if (memo[n] > -1)
        return memo[n];
    else if (n <= 2)
        return 1;
    else
        return (Fibonacci(n - 1) + Fibonacci(n - 2)) % 10009;
}
int main()
{
    ……

    memo.assign(n + 1, -1);             // not 0 but -1 (∵ 100009 % 100009 = 0)
    ……
}
Codes (C++) - Trial 3 : Use Legacy Array (crazy)

C++

……
int memo[201];
int Fibonacci(int n)
{
    ……
}
int main()
{
    ……

    fill(memo, memo + 201, -1);         // not 0 but -1 (∵ 100009 % 100009 = 0)
    ……
}
Codes (C++) - Trial 4 : Use the Bottom-Up Method

C++

……
#include <vector>

……
#define test

……
vector<int> bottomUp;
int Fibonacci(int n, int m)
{
    if (m <= 2)
        bottomUp[m] = 1;
    else
        bottomUp[m] = (bottomUp[m-1] + bottomUp[m-2]) % 10009;

    #ifdef test
        cout << m << ' ' << bottomUp[m] << endl;
    #endif

    if (m == n)
        return bottomUp[m];
    else
        Fibonacci(n, m + 1);
}
int main()
{
    ……

    bottomUp.assign(n + 1, -1);         // not 0 but -1 (∵ 10009 % 10009 = 0)
    cout << Fibonacci(n, 1) << endl;

    ……
}

Submissions

  • Tial 1 : 시간 초과

  • Tial 2 : 시간 초과

  • Tial 3 : 시간 초과

  • Tial 4 : 실행 중 에러(Runtime Error:Segmentation fault)

    때려치워!

1920. (재귀함수) 2진수 변환

Test Input & Output

Input

7

Output

111
Codes (C++) - Trial 1

C++

#include <iostream>
#include <vector>

#define endl '\n'

using namespace std;
vector<int> v {};
void Recursion(int n)
{
    v.push_back(n % 2);

    if (n < 2)
        return;
    else
        Recursion(n / 2);
}
int main()
{
    int n;
    cin >> n;

    Recursion(n);
    for (int i = v.size() - 1; i >= 0; i--)
        cout << v[i];
    cout << endl;

    return 0;
}
Codes (C++) - Trial 2 : Use String instead of Vector

C++

……
string str = "";
void Recursion(int n)
{
    str = to_string(n % 2) + str;

    ……
}
int main()
{
    ……

    ……
    cout << str << endl;

    ……
}

Submissions

  • Tial 1 : 이 문제는 for사용할 수 없습니다!
  • Tial 2 : 정확한 풀이

1928. (재귀함수) 우박수 (3n+1) (basic)

Test Input & Output

Input

5

Output

5
16
8
4
2
1
Codes (C++)

C++

#include <iostream>

#define endl '\n'

using namespace std;
void Recursion(int n)
{
    cout << n << endl;

    if (n == 1) return;
    else if (n % 2 == 1) Recursion(3 * n + 1);
    else Recursion(n / 2);
}
int main()
{
    int n;
    cin >> n;

    Recursion(n);

    return 0;
}

Submissions

정확한 풀이

1929. (재귀함수) 우박수 (3n+1) (reverse)

Test Input & Output

Input

5

Output

1
2
4
8
16
5
Codes (C++)

C++

#include <iostream>
#include <stack>

#define endl '\n'

using namespace std;
stack<int> stk;
void Recursion(int n)
{
    stk.push(n);

    if (n == 1) return;
    else if (n % 2 == 1) Recursion(3 * n + 1);
    else Recursion(n / 2);
}
void stkPop()
{
    if (!stk.empty())
    {
        cout << stk.top() << endl;
        stk.pop();
        stkPop();
    }
    else
        return;
}
int main()
{
    int n;
    cin >> n;

    Recursion(n);
    stkPop();

    return 0;
}

Submissions

정확한 풀이

1930. SuperSum

not attempted

1953. (재귀함수) 삼각형 출력하기 1

Test Input & Output

Input

3

Output

*
**
***
Codes (C++)

C++

#include <iostream>

#define endl '\n'

using namespace std;
void star(int m)
{
    cout << '*';

    if (m == 1) return;
    else star(m - 1);
}
void Recursion(int n, int m)
{
    star(m);
    cout << endl;

    if (n == m) return;
    else Recursion(n, m + 1);
}
int main()
{
    int n;
    cin >> n;

    Recursion(n, 1);

    return 0;
}

Submissions

정확한 풀이

3702. 파스칼의 삼각형 2

not attempted

3704. 계단 오르기 2

not attempted

3733. 우박수 길이 (3n+1) (large)

not attempted

4564. 계단 오르기

not attempted