15649 ~ 15652.N과 M(1~4)

이번에 풀어볼 문제는 순열과 조합 및 재귀함수와 관련된 문제이다.

15649번: N과 M (1)

 

15650번: N과 M (2)

 

15651번: N과 M (3)

 

 

15652번: N과 M (4)

저번에도 말했듯이 재귀함수는 너무나 헷갈리고 복잡하다.. 나의 약점이라고 생각한다.

그래도 약점을 알게됐으니까 보완하면된다!!!

그리고 이런 문제를 풀 때는 조금 떨어져서 어떤 유형인지 확인할 필요가 있다. 

이 문제들은 규칙성을 자세히보면 순열인지 조합인지 확인할 수 있다.

재귀함수의 사용은 백트래킹과 DFS와도 관련이 있으니 잘알아두자! => 스택과 큐를 잘알아두는 것도 중요함

---

* 순열은 순서가 상관있는 조합을 의미한다. ex) { 1, 2, 3 } , { 2, 1, 3 }, { 3, 1, 2 } => 순열에서 이 3가지는 모두 다른 것이다.

* 조합은 순서없이 그냥 조합만 성공하면 되는 것을 의미한다. ex) { 1, 2, 3 } , { 2, 1, 3 }, { 3, 1, 2 } => 조합에서 이 3가지는 같다.

---

# 재귀함수를 사용할 때는 주의할 점이 있다!

1. 재귀함수의 탈출구를 항상 생각해야한다

=> 언제 재귀함수를 종료할 것인지 조건을 잘 구현해야한다

=> 잘 구현할 수록 연산이 줄어듬

 

2. 어떠한 로직으로 진행될 것인지 경우에 따라 점화식(?)을 잘 세워야한다 => 로직과 패턴을 잘 생각해서 구현!!

 

3. 함수에 또다시 들어가는 것이 아니라 복사본을 만든다는 개념 (재귀로 함수가 호출되면 함수가 스택에 쌓인다는 이미지) 

=> 함수의 return 이후를 잘 파악해서 동작하는 순서를 잘알아야한다.

=> 가장 중요하고 이 부분을 망각하면 그때 부터 아주 골치아파지는 것 같다.

=> 그리고 당연한 말일 수도 있지만 예외처리할 때 조건를 특정 변수를 추가하여 처리하는 것도 하나의 팁이다.

=> 함수를 만들 떄 매개변수의 순서도 중요한 것 같다. 나같은 경우에는 디버깅할 때 너무 헷갈렸다 => 가독성 중요!

 

4. 그리고 입력 받는 값이나 사용되는 배열 등은 전역변수로 빼놓는 게 재귀함수를 구현할 때 편하다.

 

5. 순열과 조합의 문제를 풀 떄는 Point가 있다.

=> 순열 : 순서가 있는 조합, 한 번 참고한 시작점은 다신 참고 안한다는 마인드, 시작점을 핸들링하는 변수와 사용 체크 변수 필요

=> 조합 : 순서가 필요없으므로 그냥 진행하면되며 사용 체크 변수 필요(중복방지)

=> 중복 순열 : 순서가 있기 때문에 역시 Start 지점을 핸들링 하되 굳이 사용한 것 체크할 필요가 없음(중복방지 필요 x )

=> 중복 조합 : 그냥 진행하면 되고 중복이기에 사용한 것 체크할 필요가 없음(중복방지 필요 x )

 

---

 

< Code 설명 - N과 M(1) 조합 >

#include <iostream>

using namespace std;

int n, m;
int arr[10];
bool check[10];


void func(int start, int cnt){
	if (cnt == m+1){
		for (int i = 1; i <= m; i++)
			cout << arr[i] << " ";
		cout << "\n";
		return;
	}

	for (int i = start; i <= n; i++){
		if (!check[i]){
			check[i] = true;
			arr[cnt] = i;
			func(i, cnt + 1);
			check[i] = false;
		}
	}
}
int main() {
	cin >> n >> m;
	func(1,1);
	return 0;
}

 

< Code 설명 - N과 M(2) 순열 >

#include <iostream>

using namespace std;

int n, m;
int arr[10];
bool check[10];
void func(int cnt){
	if (cnt == m + 1){
		for (int i = 1; i <= m; i++)
			cout << arr[i] << " ";
		cout << "\n";
		return;
	}

	for (int i = 1; i <= n; i++){
		if (!check[i]){
			check[i] = true;
			arr[cnt] = i;
			func(cnt + 1);
			check[i] = false;
		}
	}
}
int main(){
	cin >> n >> m;
	func(1);
	return 0;
}

 

< Code 설명 - N과 M(3) 중복 조합 >

#include <iostream>

using namespace std;

int arr[11];
bool check[11];
int n, m;

void func(int cnt){
	if (cnt == m + 1){
		for (int i = 1; i <= m; i++)
			cout << arr[i] << " ";
		cout << "\n";
		return;
	}

	for (int i = 1; i <= n; i++){
		arr[cnt] = i;
		func(cnt + 1);
	}
}
int main(){
	cin >> n >> m;
	func(1);
	return 0;
}

 

< Code 설명 - N과 M(4) 중복 순열 >

#include <iostream>

using namespace std;

int n, m;
int arr[11];
bool check[11];

void func(int start, int cnt){
	if (cnt == m + 1){
		for (int i = 1; i <= m; i++)
			cout << arr[i] << " ";
		cout << "\n";
		return;
	}
	for (int i = start; i <= n; i++){
		arr[cnt] = i;
		func(i, cnt + 1);
	}
}
int main() {
	cin >> n >> m;
	func(1, 1);
	return 0;
}

 

 

---

 

 

해당 문제에 관련 기본 설명은 아래의 블로그가 설명을 굉장히 디테일하게 해놓으셨다. 참고하면 이해가 빠를 것 같다.

조합 : https://yabmoons.tistory.com/99

순열 : https://yabmoons.tistory.com/100

중복 조합 : https://yabmoons.tistory.com/122

중복 순열 : https://yabmoons.tistory.com/123?category=838490