[백준(BOJ)] 10872번&10870번 C++ 풀이

최근 준비했던 일이 마무리되어 한달 정도의 시간적 여유를 가질 수 있게 되었다.

무엇을 할까 고민하다 최근 코딩 공부에 소홀했던터라 당분간은 빡세게(?) 전공 공부를 해볼까한다.

 

백준 알고리즘을 매일 풀어보려 하는데 특별한 목적이 있는게 아닌터라 그냥 내 마음가는대로 아무거나 선택해서 풀어볼 생각이다. 더불어 프로그래밍언어 중에서도 C++에 가장 소홀했기 때문에 백준 문제 풀이 겸 C++ 문법 정리 겸...(정말 거짓없이 C++ 문법 하나도 생각 안난다......;;;) 

 

그래서 글이 개인적인 복습노트(?)가 될 터라 내용이 엉망진창이겠지만 누군가에게는 도움이 될 수도 있으니 글을 이어나가려 한다.

 

[C++ 문법]

C++의 표준 입력과 출력 : cin, cout   //std 네임스페이스의 객체, <iostream> 클래스 내 인스턴스

#include <iostream>

int main( ){

      int a;

      std::cout << "hello" << std::endl;     //hello문자열 출력, std::endl는 개행 명령어

      std::cin >> a;      //입력을 원하는 변수 a에 저장

}

//이때 using namespace std;를 상단에 작성 시 namespace는 C++의 각종 요소들을 한 범주로 묶어주는 문법이기 때문에 std:: 은 생략 가능하다.

#include <iostream>

using namespace std;

int main( ){

      int a;

      cout << "hello" << endl;

      cin >> a;    

}

 

[BOJ 문제 10872번]

가장 대표적인 재귀함수 문제 중 하나이다. 재귀함수(Recursion)란 어떤 함수가 자신을 재참조 혹은 재호출해 작업을 수행하는 방식을 말하며 이때 함수 내 다시 자신을 호출한 후 그 함수가 끝날 때까지 하뭇 호출 이후의 명령문이 수행되지 않는다는 사실과 종료 조건이 반드시 포함되어야 무한루프를 방지할 수 있음을 기억해야 한다.

팩토리얼의 원리인 n! = n * (n-1)! 을 이용한다.

 

 

해당 문제를 재귀함수로 풀면 다음과 같다.

재귀함수에 대해 잠깐 이야기하자면 사용할 때 정말로 조심해야한다. 알고리즘 측면에서는 코드를 보는 이로 하여금 이해가 쉽고 보기 간편하지만 프로그래밍 측면에서 보면 언제 버그가 생길지 모른다. 재귀함수의 원리가 자기 자신, 즉 함수를 다시 호출하는 것이기에 한 번의 함수호출에 매개변수, 복귀주소 등의 값이 Stack에 쌓이게 된다. 때문에 조금이라도 n의 값이 커져 함수호출이 많아진다면 Stack Overflow(Stack Overhead)가 발생하게 된다. 

때문에 재귀함수를 반복문으로 표현하는 방법과 꼬리 재귀 최적화로 구현하는 방법을 모두 알고 있기를 권장한다.

 

반복문을 이용해 구현한 팩토리얼

int fac(int n){
      int result = 1;
      if(n == 0 || n == 1)
      else{
            for(int i = 1; i <= n; i++)
                  result = result * i;
      }
      return result;
}

 

꼬리 재귀를 이용해 구현한 팩토리얼  -> 재귀 호출 이후 추가적인 연산을 요구하지 않도록 구현

int facTail(int n, int acc){
      if(n == 0 || n == 1)
            return acc;
      return facTail(n-1, acc * n);
}
int fac(int n){
      return facTail(n, 1);
}

일반 재귀함수의 경우, 재귀호출 이후 n을 곱하는 연산이 필요하다. 하지만 꼬리 재귀로 구현하면 facTail이 호출 된 후 n을 곱하지 않는, 즉 추가 연산이 없기에 Stack Overhead를 줄일 수 있다.

 

 

[BOJ 10870번]

마찬가지로 피보나치 수열의 특징을 재귀함수로 표현하여 풀면 다음과 같다.

 

반복문을 이용해 구열한 피보나치

int fib(int num){
      int result;
      int a=0;
      int b=1;
      if(num == 0)
            result=0;
      else if(num == 1)
            result=1;
      else{
            for(int i = 2; i <= n; i++){
                  result = a + b;
                  a = b;
                  b = result;
            }
      }
      return result;
}

 

꼬리 재귀를 이용해 구현한 피보나치

int fibTail(int n, int a, int b){
      if(n == 0)
            return a;
      else
            return fibTail(n-1, b, a+b);
}
int fib(int num)
      return fibTail(n, 0, 1);