다른 자바나 파이썬 할때는 쉽게 느꼈던 백트래킹이 C로 해보니까 갑자기 막막했었다!!
그래서 처음 문제인 15649를 풀이를 보고 이해하고 나머지 3문제 풀이를 완료했다
맨 처음 문제가 제일 어려운거 인거 같다..
백트래킹의 기본은 두가지라고 생각한다
1. 몇번 돌지 정해서 마지막 돌았을때 원하는 결과를 return해버리기!
2. 아직 마지막 까지 안 돌았다면 해야하는 행동을 하면서 깊이 들어가기
15649 문제와 풀이 그리고 코드
15649 문제와 풀이
기본적으로 하나의 수열안에서 숫자가 중복되면 안된다는 기준이 있다!
n은 1-n까지 숫자를 의미하고
m은 수열의 길이를 의미한다!
n과 m에 4 2 를 치면 아래처럼 결과값이 나와야함
1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3
m만큼 깊이까지 들어가면 result배열에 저장한 수열을 출력해주자! 라는 형식으로 풀었다
15649 코드
#include<stdio.h>
int n,m;
int result[1000]; // 수열을 저정할 배열,
int check[10]; // 중복을 점검할 배열 1-n까지 들어가는데 1 1 이 들어가는 경우 방지!
void dfs(int depth) {
if(depth ==m ) { // 깊이가 m까지 왔다면 result 배열에 담은 순열을 출력해야함!
for(int i=0; i<m; i++) {
printf("%d ", result[i]);
}
printf("\n");
return; // 항상 마지막에는 종료해줘야함!!
}
for(int i=1; i<=n; i++) {
if(check[i] == 0) { // 아직 중복되지 않았다면 -> result결과에 넣어주기!
result[depth] = i; // depth가 배열의 깊이고 i가 값이다!
check[i] = 1; // dfs로 다시 재귀해야해서 현재 값을 이미 사용했다고 체크함
dfs(depth+1); // 배열 깊이가 +1이 됨!
check[i] = 0; // dfs에 사용이 끝났으니까 다시 값 사용 안했다고 나타내기!
}
}
}
int main() {
scanf("%d %d", &n, &m);
dfs(0); // 현재 순열의 깊이 -> 아직 아무것도 안했어서 0이다!
return 0;
}15650 문제와 풀이 그리고 코드
15650 문제와 풀이
기본적으로 하나의 수열안에서 숫자가 중복되면 안된다는 기준이 있다!
그리고 오름차순 출력!! 전에 문제는 그냥 순서 상관없었다!
n은 1-n까지 숫자를 의미하고
m은 수열의 길이를 의미한다!
n과 m에 4 2 를 치면 아래처럼 결과값이 나와야함
1 2
1 3
1 4
2 3
2 4
3 4
나머지는 다 같지만, 오름차순 출력이니까 int cut이라는 변수를 인자로 사용해서
저장된 값보다 높은 수인지 매번 확인해주기!
15650 코드
#include<stdio.h>
int n,m;
int result[1000];
int check[10];
int dfs(int depth, int cut) {
if(depth ==m ) { // 깊이가 m까지 왔다면 result 배열에 담은 순열을 출력해야함!
for(int i=0; i<m; i++) {
printf("%d ", result[i]);
}
printf("\n");
return; // 항상 마지막에는 종료해줘야함!!
}
for(int i =1; i<=n; i++) {
if(check[i] ==0 && cut < i ) { // cut보다 i가 커야 더 큰숫자가 계속 들어가므로 오름차순이 된다!
result[depth] = i;
check[i] = 1;
dfs(depth+1, i); // cut을 i로 해줘서 뒤에 오는 숫자들이 i보다 커야함!
check[i] = 0;
}
}
}
int main() {
scanf("%d %d", &n.&m);
dfs(0,0); // depth, cut을 인자로 줌!
return 0;
}15651 문제와 풀이 그리고 코드
15651 문제와 풀이
기본적으로 하나의 수열안에서 숫자가 중복되도 상관없다!
n과 m에 4 2 를 치면 아래처럼 결과값이 나와야함
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4
이건 지금까지 check배열을 사용해서 중복을 검사했는데 그럴필요가 없다!
15651 코드
#include<stdio.h>
int n,m;
int result[1000];
int dfs(int depth) {
if(depth ==m ) { // 깊이가 m까지 왔다면 result 배열에 담은 순열을 출력해야함!
for(int i=0; i<m; i++) {
printf("%d ", result[i]);
}
printf("\n");
return; // 항상 마지막에는 종료해줘야함!!
}
for(int i =1; i<=n; i++) {
result[depth] = i;
dfs(depth+1); // 그냥 중복 상관없으니까 넣어도 됨!
}
}
int main() {
scanf("%d %d", &n.&m);
dfs(0); // depth, cut을 인자로 줌!
return 0;
}15652 문제와 풀이 그리고 코드
15652 문제와 풀이
기본적으로 하나의 수열안에서 숫자가 중복되도 상관없다!
대신 비 내림차순으로 즉 중복이 허용된 오름차순으로 순열을 출력해야한다!
n과 m에 4 2 를 치면 아래처럼 결과값이 나와야함
1 1
1 2
1 3
1 4
2 2
2 3
2 4
3 3
3 4
4 4
15652 코드
#include<stdio.h>
int n,m;
int result[1000];
int dfs(int depth, int cut) {
if(depth ==m ) { // 깊이가 m까지 왔다면 result 배열에 담은 순열을 출력해야함!
for(int i=0; i<m; i++) {
printf("%d ", result[i]);
}
printf("\n");
return; // 항상 마지막에는 종료해줘야함!!
}
for(int i =1; i<=n; i++) {
if(cut <= i) { // 중복가능이어서 cut <= i로 해줬다!!
result[depth] = i;
dfs(depth+1, i); //
}
}
}
int main() {
scanf("%d %d", &n.&m);
dfs(0,0); // depth, cut을 인자로 줌!
return 0;
}피드백
사실 중복체크를 check배열로 한다는 것과 오름차순을 구할때 int cut 변수를 사용해서 하면
각자 역할로 직관적으로 풀 수 있어서 이해가 빨랐다.
아직 알고리즘 풀이 실력은 부족하니까 더 연습하자!
