본문 바로가기
C++/자료구조와 알고리듬

1. Recursive Function, Array

by GameStudy 2022. 10. 21.

 

1.1 재귀함수

1.1-1 단순 재귀

  Ex)

<hide/>

#pragma once

#include <stdio.h>

void SimpleRecursion(int _nCount)
{
    printf("%d\n", _nCount);

    if (1 == _nCount)
    {
        return;
    }

    SimpleRecursion(_nCount - 1);
}

 

  Ex) 
    재귀함수를 이해하기 위한 가장 정확한 방법. 글쓴이는 이걸 "전개도를 펼친다"라고 생각함.
    3차원의 도형을 전개해서 2차원으로 차원을 낮추는 것과 같음. 즉, 한 눈에 보기 편해서 쉬워짐.

<hide/>

#include <stdio.h>

void recursive(int count)
{
    if (4 == count)
    {
        return;
    }
    
    recursive(count + 1);

    printf("%d\n", count);
}


int main(void)
{
    recursive(1);

    return 0;
}
<hide/>

r(1)
{
    if (false)

    r(2);
    {
        if (false)

        r(3);
        {
            if (false)

            r(4)
            {
                if (true)
                {
                    return;
                }
            }

            p(3);
        }

        p(2);
    }

    p(1)
}

 

  Codeup1901)
    1부터 n까지 출력하는 문제. 전개도 펼치기를 여러 번 해보았다면 충분히 이해 가능.

<hide/>

#include <iostream>

void PrintRecursively(int InCurrentN)
{
    if (0 == InCurrentN)
    {
        return;
    }

    std::cout << InCurrentN << std::endl;

    PrintRecursively(InCurrentN - 1);
}

int main(void)
{
    int n;
    std::cin >> n;

    PrintRecursively(n);

    return 0;
}

 

  Codeup1902)
    n부터 1까지 출력하는 문제.
    출력과 재귀함수 순서의 중요성. 이해가 안된다면 전개도 연습이 많이 필요함.

<hide/>

#include <iostream>

void PrintRecursively(int InCurrentN)
{
    if (0 == InCurrentN)
    {
        return;
    }

    std::cout << InCurrentN << std::endl;

    PrintRecursively(InCurrentN - 1);
}

int main(void)
{
    int n;
    std::cin >> n;

    PrintRecursively(n);

    return 0;
}

 

  Codeup1094)
    두 수 사이의 홀수 출력.

<hide/>

#include <iostream>

void PrintOddNumbers(int InCurrentA, int InCurrentB)
{
    if (InCurrentB + 1 == InCurrentA)
    {
        return;
    }

    if (InCurrentA % 2 == 1)
    {
        std::cout << InCurrentA << " ";
    }

    PrintOddNumbers(InCurrentA + 1, InCurrentB);
}

int main(void)
{
    int a, b;
    std::cin >> a >> b;

    PrintOddNumbers(a, b);

    return 0;
}

 

  Codeup1905)
    1부터 n까지의 누적합을 구하는 문제. 이전 문제와 다르게 반환 자료형을 활용하는 재귀함수 문제.

<hide/>

#include <iostream>

int AccumulateN(int InCurrentN)
{
    if (0 == InCurrentN)
    {
        return 0;
    }

    return InCurrentN + AccumulateN(InCurrentN - 1);
}

int main(void)
{
    int n;
    std::cin >> n;

    std::cout << AccumulateN(n);

    return 0;
}

 

  Codeup1912)

    1부터 n까지의 누적곱을 구하는 문제. 반환 자료형을 신경써야 함.
    int의 누적곱은 long long 반환자료형을 고려해야함.

<hide/>

#include <iostream>

long long FactorialN(int InCurrentN)
{
    if (1 == InCurrentN)
    {
        return 1;
    }

    return InCurrentN * FactorialN(InCurrentN - 1);
}

int main(void)
{
    int n;
    std::cin >> n;

    std::cout << FactorialN(n);

    return 0;
}


  Ex)
    재귀함수로 자릿수의 합 구하기.

<hide/>

#include <iostream>

int SumDigits(int InCurrentN)
{
    if (0 == InCurrentN)
    {
        return 0;
    }

    return InCurrentN % 10 + SumDigits(InCurrentN / 10);
}

int main(void)
{
    int n;
    std::cin >> n;

    std::cout << SumDigits(n);

    return 0;
}

 

  Codeup1920)
    10진수를 2진수로 변환하는 함수 구현. 2진수 변환 과정이 반복됨을 캐치해야 이해 가능.

<hide/>

#include <iostream>

void MakeBinary(int InCurrentN)
{
    if (0 == InCurrentN)
    {
        return;
    }

    int NextN = InCurrentN / 2;
    int Remain = InCurrentN % 2;

    MakeBinary(NextN);

    std::cout << Remain;
}

int main(void)
{
    int n;
    std::cin >> n;

    if (0 == n)
    {
        std::cout << n;
        return 0;
    }

    MakeBinary(n);

    return 0;
}

 

  CodeUp1928)
    우박수(콜라츠 추측) 출력. 재귀함수 호출에 예외처리가 관건.

<hide/>

#include <iostream>

void PrintCollatzSequence(int InCurrentN)
{
    std::cout << InCurrentN << std::endl;

    if (InCurrentN == 1)
    {
        return;
    }

    if (InCurrentN % 2 == 0)
    {
        PrintCollatzSequence(InCurrentN / 2);
    }
    else
    {
        PrintCollatzSequence(3 * InCurrentN + 1);
    }
}

int main(void)
{
    int N;
    std::cin >> N;

    PrintCollatzSequence(N);

    return 0;
}

 

  백준1629)
    A의 B승을 구하는 문제. 이때 C로 나눈 나머지를 반환해야함.
    B를 절반으로 나누며, 재귀함수를 호출함. B가 계속 반으로 줄어들기에, 시간복잡도가 O(logB)
    나눠서 구한 절반값을 제곱하여 결과 구하기.

<hide/>

#pragma once

#include <iostream>
#include <stack>
#include <limits>

using namespace std;

long long modExp(long long A, long long B, long long C) {
    if (0 == B)
    {
        return 1;
    }

    long long HalfExp = modExp(A, B / 2, C);
    long long Result = (HalfExp * HalfExp) % C;
    if (B % 2 == 1)
    {
        Result = (Result * A) % C;
    }

    return Result;
}

int main() {
    long long A, B, C;
    cin >> A >> B >> C;

    cout << modExp(A, B, C) << endl;

    return 0;
}


    

 

1.1-2 트리 재귀

  Ex)
    아래와 같은 재귀함수 코드를 전개해보면 마치 트리 모양과 같아서
    글쓴이는 Tree Recursion이라고 이름 지음. 그림을 그려가면서 파악해도 좋음.
    점화식과 같다고 생각해도 좋음. 초기식과 점화식으로 구성되어 있음.

<hide/>

// Template2_TreeRecursion.h

#pragma once

int f(int n)
{
    if (1 == n) { return 1; }
    if (2 == n) { return 1; }

    return f(n - 1) + f(n - 2);
}
<hide/>

// main.cpp

#include <iostream>

#include "Template1_SimpleRecursion.h"
#include "Template2_TreeRecursion.h"
#include "Practice.h"

int main()
{
    int n;
    scanf("%d", &n);
    printf("%d", f(n));

    return 0;
}

 

  CodeUp1915)
    피보나치 수열의 N번째 값을 반환하는 재귀함수. 기초적인 점화식 문제.

<hide/>

#include <iostream>

int Fibonacci(int InCurrentN)
{
    if (0 == InCurrentN)
    {
        return 0;
    }
    else if (1 == InCurrentN || 2 == InCurrentN)
    {
        return 1;
    }

    return Fibonacci(InCurrentN - 1) + Fibonacci(InCurrentN - 2);
}

int main(void)
{
    int N;
    std::cin >> N;

    std::cout << Fibonacci(N);

    return 0;
}

 

  CodeUp3704)
    계단을 오르는 경우의 수 구하기. 결국 쉬운 타일링 문제.
    재귀함수에 메모이제이션을 활용하는 DP 문제.

<hide/>

#include <iostream>

int Memoization[100001] = { 0, };

int CountStair(int InCurrentN)
{
    if (1 == InCurrentN)
    {
        return 1;
    }
    else if (2 == InCurrentN)
    {
        return 2;
    }
    else if (3 == InCurrentN)
    {
        return 4;
    }

    if (Memoization[InCurrentN] != 0)
    {
        return Memoization[InCurrentN];
    }

    return Memoization[InCurrentN] = ((CountStair(InCurrentN - 1) + CountStair(InCurrentN - 2) + CountStair(InCurrentN - 3)) % 1000);
}

int main(void)
{
    int N;
    std::cin >> N;

    std::cout << CountStair(N);

    return 0;
}


  Codeup1953)
    재귀함수로 별찍기. Tree 형태이긴 하지만 로직 변형이 필요한 재귀함수 문제.

<hide/>

#include <iostream>

void PrintStarsColumn(int InCurrentColumn)
{
    if (0 == InCurrentColumn)
    {
        return;
    }

    std::cout << "*";

    PrintStarsColumn(InCurrentColumn - 1);
}

void PrintStarsRow(int InCurrentRow)
{
    if (0 == InCurrentRow)
    {
        return;
    }

    PrintStarsRow(InCurrentRow - 1);

    PrintStarsColumn(InCurrentRow);
    std::cout << std::endl;
}

int main(void)
{
    int n;
    std::cin >> n;

    PrintStarsRow(n);

    return 0;
}

 

  ????)
    문제 이름이 기억이 안나는 문제. 재귀함수 장르 중 가장 어려웠던 문제여서 풀이만 기억남.

<hide/>

// Practice.h

#pragma once

using namespace std;

int f(int n)
{
    if (1 == n) { return 1; }
    if (2 == n) { return 1; }

    return f(f(n - 1)) + f(n - f(n - 1));
}

 

 

1.1-3 꼬리 재귀

  Note) 재귀함수는 가독성도 좋고, 유지보수에도 유리하다.

    그러나, 함수 호출에 대한 오버헤드가 있음.

 

  Def) 꼬리 호출(Tail Call)

    Caller 함수의 블럭 스코프 마지막에 Callee 함수를 호출하는 경우.

 

  Note) 꼬리 호출과 스택 프레임

    스택 프레임이 존재하는 이유는 Caller에서 사용중인 변수값을 저장하기 위함.

    Callee 호출 후에 반환되면, 스택 프레임에 저장 했던 값을 되돌려서 사용함.

 

  Note) 꼬리 호출 시에, Caller에서 더이상의 연산이 없다면?

    이는 Caller의 스택 프레임을 유지할 필요가 없다는 뜻.

    이런 경우에 컴파일러는 Caller의 스택 프레임을 안만들고,

    Callee의 스택 프레임만 만들기도 함.

    이를 꼬리 호출 제거 혹은 꼬리 호출 최적화라고 함.

 

  Def) 꼬리 재귀(Tail Recursion)

    꼬리 호출의 특수한 케이스. 재귀 함수 + 꼬리 호출.

    이 경우, 꼬리 호출과 똑같은 최적화가 적용됨.

 

  Ex)

<hide/>

// main.cpp

#include <iostream>

...

long long int fac(int n, int res)
{
    if (n <= 1) { return res; }
    return fac(n - 1, n * res);
}

long long int f(int n)
{
    return fac(n, 1);
}

int main()
{
    int n;
    cin >> n;
    cout << f(n);

    return 0;
}

 

  Ex)

<hide/>

// main.cpp

#include <iostream>

...

long long int sum(int n, int res)
{
    if (n < 1) { return res; }
    return sum(n - 1, n + res);
}

long long int f(int n)
{
    return sum(n, 0);
}

long long int sum2(int n)
{
    if (n < 1) { return 0; }
    return n + sum2(n - 1);
}

int main()
{
    int n;
    cin >> n;
    cout << f(n) << ' ' << sum2(n);

    return 0;
}

 

 

1.2 배열
1.2-1 정적 배열

  Def)
    메모리 크기가 고정된 배열을 정적 배열이라고 함.

 

  Note) 장단점
    장점1. 연속된 메모리 공간을 가지므로, 캐시 지역성에 유리함. 임의 접근 가능.
    장점2. 메모리를 할당 및 해제하는 과정에서 생길 수 있는 성능저하가 없음.
    단점1. 가변 크기 데이터를 다룰 수 없음.
    단점2. 메모리 크기를 너무 크게 잡으면 메모리 낭비 가능성이 있음.
    결론: 고정된 크기의 데이터를 빠르게 처리해야하는 때에 사용.

 

  Note) 구현코드

<hide/>

#pragma once

#include <iostream>

template<typename T>
class SArray final
{
public:
    SArray(size_t InCapacity)
        : Data(new T[InCapacity])
        , Capacity(InCapacity)
    {

    }

    ~SArray()
    {
        delete[] Data;
    }

    size_t GetCapacity() const
    {
        return Capacity;
    }

    T& operator[](size_t InIndex)
    {
        if (InIndex < 0u || Capacity < InIndex)
        {
            std::cout << "Out of bounds." << std::endl;
            exit(0);
        }

        return Data[InIndex];
    }

    const T& operator[](size_t InIndex) const
    {
        if (InIndex < 0u || Capacity < InIndex)
        {
            std::cout << "Out of bounds." << std::endl;
            exit(0);
        }

        return Data[InIndex];
    }

private:
    T* Data;

    size_t Capacity;

};

 

 

1.2-2 동적 배열

  Def) 
    메모리 크기가 변경될 수 있는 배열을 동적 배열이라고 함.

 

  Note) 장단점
    장점1. 연속된 메모리 공간을 가지므로, 캐시 지역성에 유리함. 임의 접근 가능.
    장점2. 데이터의 크기를 예측 할 수 없을 때 유용함.
    단점1. 메모리 크기를 조정할 때 메모리 재할당 및 데이터 복사 오버헤드 발생.
    결론. 가변 크기의 데이터를 처리해야하는 때에 사용.

 

  Note) 구현코드

<hide/>

#pragma once

#include <iostream>

template<typename T>
class SVector final
{
public:
    SVector(size_t InCapacity = 2u, size_t InCapacityIncrement = 2u)
        : Data(new T[InCapacity])
        , Capacity(InCapacity)
        , CapacityIncrement(InCapacityIncrement)
        , Size(0u)
    {

    }

    ~SVector()
    {
        delete[] Data;
    }

    size_t GetCapacity() const
    {
        return Capacity;
    }

    T& operator[](size_t InIndex)
    {
        if (InIndex < 0u || Capacity < InIndex)
        {
            std::cout << "Out of bounds." << std::endl;
            exit(0);
        }

        return Data[InIndex];
    }

    const T& operator[](size_t InIndex) const
    {
        if (InIndex < 0u || Capacity < InIndex)
        {
            std::cout << "Out of bounds." << std::endl;
            exit(0);
        }

        return Data[InIndex];
    }

    size_t GetSize() const
    {
        return Size;
    }

    void PushBack(const T& InValue)
    {
        if (Capacity <= Size)
        {
            Resize(Capacity * CapacityIncrement);
        }

        Data[Size++] = InValue;
    }

private:
    void Resize(size_t InNewCapacity)
    {
        T* NewData = new T[InNewCapacity];
        for (size_t i = 0u; i < Size; ++i)
        {
            NewData[i] = Data[i];
        }

        delete[] Data;
        Data = NewData;
        Capacity = InNewCapacity;
    }

private:
    T* Data;

    size_t Capacity;

    size_t CapacityIncrement;

    size_t Size;

};



 

 

 

 

 

 

 

 

 

 

 

 

 

 

저작자표시 비영리 변경금지

'C++ > 자료구조와 알고리듬' 카테고리의 다른 글

6. Linked list, Hash table  (0) 2022.12.30
5. Dynamic Programming, Backtracking  (0) 2022.12.01
4. Graph, DFS, BFS  (0) 2022.11.22
3. Tree, Binary Search Tree  (0) 2022.11.04
2. Sort, Search, Stack, Queue  (0) 2022.10.23

관련글

댓글

티스토리툴바