[C++] 기초 (2) : 재귀 함수 & 전역변수와 지역변수 & Problem Solving

재귀함수

함수가 자기 자신을 호출하여 문제를 해결하는 기법

특정 알고리즘(DFS, Union-Find, Divide & Conquer, DP{Top-down})에 많이 사용

특징

1. 함수가 자신을 호출한다.
2. 무조건 종료가 필요하다. (기저 조건의 편성이 필요하다)
3. 이론상으로만 반복문 ↔ 재귀의 구성이 가능하다.물리적으로 작성할 수 없는 코드를 스스로 변경하여 작성하는 형태
4. e,x, 주사위를 던져서 나올 수 있는 모든 눈금의 경우의 수를 사전 순으로 출력해라.

구성

1. 기저 조건 (언제 끝나고 빠져나와야 하는가?)
2. 수행 내용 (어떤 작업을 반복해서 할 것인가?)
3. 재귀 구성 (어떻게 다음 재귀를 진행할 것인가?)

// 1부터 5까지 출력하는 재귀 함수의 예
void func(int now){

	if (now == 5){          // 기저 조건
		cout << now;
		return;
	}

	cout << now << " ";     // 수행 내용

	func(now + 1);          // 재귀 구성

언제 쓰이는가?

• 모든 경우의 수(조합&순열)를 확인
• 경로를 기록하는 DAT
• BackTracking → 경우의 수 줄이기 (가지치기)

---

지역 변수와 전역 변수의 차이

#include<iostream>
using namespace std;

int a = 3;

void func1(){
	int a = 10;
	int b = 10;
	cout << a << " " << b << "\\n";
}

void func2(){
	a = 7;
	int b = 7;

	cout << a << " " << b << "\\n";
	func1();
	cout << a << " " << b << "\\n";
}

int main(){
	int b = 5;

	cout << a << " " << b << "\\n";
	func2();
	cout << a << " " << b << "\\n";
}

<결과>
3 5                // main()
7 7                // func2()
10 10              // func1()
10 7               // func2()
10 5               // main()

#include<iostream>
using namespace std;

int a = 3;

void func1(){
	a = 10;
	cout << a << "\\n";
}

void func2(){
	int a = 7;

	cout << a << "\\n";
	func1();
	cout << a << "\\n";
}

int main(){

	cout << a << "\\n";
	func2();
	cout << a << "\\n";
}

<결과>
3               // main()
7               // func2()
10              // func1()
7               // func2()
10              // main()

 

위의 결과로 알 수 있는 사실

1. 전역변수
   • 함수 내에서 전역변수가 변화하면, 변화가 저장됨
   • 함수 외부에서 만들어진 변수 (a)
2. 지역변수
   • 선언된 함수 내에서 함수가 끝나면, 이전 상태로 복구됨
   • 함수 내부에서 만들어진 변수 (b)

stack 메모리에 변수가 없다면, 밖에서 변수를 찾아본다. → 두 번째 결과의 4번째 줄이 7인 이유

 

Problem Solving

1. 문제 지문 읽기
   • 꼼꼼하게 읽어야 함 (이해가 안되는 것이 하나도 없이)
2. 설계
   • 어떻게 풀 지 → 어떤 알고리즘이 사용 가능할 지
   • 설계한 내용을 가지고 복잡도 계산 → 설계한 알고리즘이 시간제한 내에 돌아갈 지 등
3. 구현
   • 실력이 기반
     • 무조건 쉬운 것부터, 양으로 승부
     • 조금씩 추가적인 조건이 첨가된 내용으로 올라간다
     • 쉐도우 코딩은 최악의 공부 방법
4. (여유 있을 때) 검증
   • Sample case (일반적으로는 채점에 x, 자체 검증용 케이스)
   • Hidden case (코드 채점용 case)
   1. test case를 만들어보기
   2. edge case (극단적 case 생각)