문제링크 : https://www.acmicpc.net/problem/15663


아이디어

  • 인덱스를 가지고 순열을 구하되
  • 값이 중복되면 안됨
  • 순열이므로 중복값 체크한 후,
  • 재귀함수 내에서 이전값을 가지고 있다가, 같은값일경우 넘어감

시간복잡도 계산

  • O(10^M) : 10e8 > 가능

자료구조

  • 백트래킹 리스트 : vector
    • 최대값 : 8 > INT 가능
  • bool chk[10] : 중복값 체크

코드(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int N,M;
vector<int> v;
int nums[10];
bool chk[10];
 
void dfs() {
    if(v.size() == M) {
        // vector 안에 인덱스 저장
        for(int x : v) cout << nums[x] << ' ';
        cout << '\n';
        return;
    }
    
    int pre = -1;
    for(int i=0; i<N; i++) {
        // 이전값과 중복되면 건너뜀
        if(chk[i]) continue;
        if(pre == nums[i]) continue;
        chk[i] = 1;
        pre = nums[i];
        v.push_back(i);
        
        dfs();
        
        chk[i] = 0;
        v.pop_back();
    }
    
}
 
int main() {
    fill(chk, chk+10, 0);
    cin >> N >> M;
    for(int i=0; i<N; i++) cin >> nums[i];
    sort(nums, nums+N);
    dfs();
    return 0;
}
 
cs

문제유형

  • 백트래킹 - 순열, 조합
    • 순열 : 재귀함수 내에서 순회할때 이전 중복값 체크
    • 조합 : 리스트 마지막 다음부터 순회
    • 값 중복되지 않도록 : 재귀함수 내 before 사용해서, 이전이랑 값 같을경우 넘김

비슷한 문제

'알고리즘 > 백준' 카테고리의 다른 글

백준 9663 N-Queen  (0) 2021.03.16
백준 2293 동전 1  (0) 2021.03.16
백준 15652 N과 M (4)  (0) 2021.03.15
백준 15651 N과 M (3)  (0) 2021.03.15
백준 15650 N과 M (2)  (0) 2021.03.15

문제링크 : https://www.acmicpc.net/problem/15652


아이디어

  • 중복이 가능한 조합
  • 기존 조합방법 : 리스트의 마지막값 다음부터 순회하며 백트래킹
  • 중복이 가능하므로, 마지막값 부터 순회하면서 수행

시간복잡도 계산

  • O(10^M) : 1e8 > 가능

자료구조

  • 백트래킹 리스트 : vector
    • 최대값 10 > INT 가능

코드(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <vector>
 
using namespace std;
 
vector<int> v;
int N,M;
 
void dfs() {
    if(v.size() == M) {
        for(int x : v) cout << x << ' ';
        cout << '\n';
        return;
    }
    
    int last = 1;
    if(!v.empty()) last = v.back();
 
    for(int i=last; i<=N; i++) {
        v.push_back(i);
        dfs();
        v.pop_back();
    }
}
 
int main() {
    cin >> N >> M;
    dfs();
    return 0;
}
 
cs

문제유형

  • 백트래킹 - 순열, 조합
    • 순열 : 재귀함수 내에서 순회할때 이전 중복값 체크
    • 조합 : 리스트 마지막 다음부터 순회
    • 값 중복되지 않도록 : 재귀함수 내 before 사용해서, 이전이랑 값 같을경우 넘김

비슷한 문제

'알고리즘 > 백준' 카테고리의 다른 글

백준 2293 동전 1  (0) 2021.03.16
백준 15663 N과 M (9)  (0) 2021.03.15
백준 15651 N과 M (3)  (0) 2021.03.15
백준 15650 N과 M (2)  (0) 2021.03.15
백준 15649 N과 M (1)  (0) 2021.03.15

문제링크 : https://www.acmicpc.net/problem/15651


아이디어

  • 백트래킹 - 순열,조합
    • 중복 순열이기 때문에, 중복값 체크해줄 필요없음
    • 순열처럼 풀되 중복값 체크해주지 않으면 됨

시간복잡도 계산

  • 10^M : 1e7 > 가능

자료구조

  • 백트래킹 리스트 : vector
    • 최대값 7 > INT 가능

코드(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <vector>
 
using namespace std;
 
int N,M;
vector<int> v;
 
void dfs() {
    if(v.size() == M) {
        for(int x : v) cout << x << ' ';
        cout << '\n';
        return;
    }
    
    for(int i=1; i<=N; i++) {
        v.push_back(i);
        dfs();
        v.pop_back();
    }
}
 
int main() {
    cin >> N >> M;
    dfs();
    return 0;
}
 
cs

문제유형

  • 백트래킹 - 순열, 조합
    • 순열 : 재귀함수 내에서 순회할때 이전 중복값 체크
    • 조합 : 리스트 마지막 다음부터 순회
    • 값 중복되지 않도록 : 재귀함수 내 before 사용해서, 이전이랑 값 같을경우 넘김

비슷한 문제

'알고리즘 > 백준' 카테고리의 다른 글

백준 15663 N과 M (9)  (0) 2021.03.15
백준 15652 N과 M (4)  (0) 2021.03.15
백준 15650 N과 M (2)  (0) 2021.03.15
백준 15649 N과 M (1)  (0) 2021.03.15
백준 2579 계단 오르기  (0) 2021.03.14

+ Recent posts

티스토리툴바