오늘 학습 키워드

• 값에 의한 전달

• 백트래킹

값에 의한 전달

• C에서는 함수에 인자로 넘겨줄 때 값에 의한 전달이 일어남

• 배열 역시 마찬가지로, 배열의 이름이 첫 번째 요소의 주소값이므로 값이 전달되는 것

void foo(int a, int b[5]);

int main() {
	foo(a, arr);	// a는 수정 안 되고, arr은 foo에서 수정됨
}

• C++ 역시 거의 모든 인자는 기본적으로 값에 의한 전달이 일어나며, 이때 복사비용이 발생

void foo(std::vector<int> v);	// v는 새로운 복사본
void func(MyClass obj);			// obj 역시 복사본

• 따라서 &를 이용하여 복사비용을 아끼고, const를 이용해 읽기전용으로 사용하여 복사비용을 아낀다

void func(std::set<int>& s);              // 원본 그 자체
void func(const std::map<int,int>& m);    // 읽기 전용(복사X)
void func(MyClass obj);                   // 객체 복사
void func(MyClass& obj);                  // 원본 그 자체
void func(const MyClass& obj);            // 읽기 전용(복사X)

백트래킹

• 해를 탐색하는 도중, 더 이상 해가 나오지 않을 상황이라면 탐색을 종료하고 뒤로 돌아가는 문제 해결법
  

• 부분 집합의 합, N-queen이 대표적인 백트래킹 문제

풀이 방법

1. 상태-공간 트리로 해의 후보를 정의하기
   

2. 유망함수 정의하기
   해를 더 탐색할지 말지를 정하는 유망함수를 정의