경작 4일차 bruteforce (2)

한정화·2023년 1월 31일

23년 겨울 코딩농장 경작일지

목록 보기

4/24

230131 화

오늘은 2일차에 풀던 알고리즘 스터디 bruteforce 문제들을 이어서 풀어보겠다.
#가보자고

1. 백준 15650번 N과 M (2)

스터디에서 내주신 bruteforce 문제 중에 제일 간단하고 정답률도 높은(74%) 문제인데 왜 나만 못 풀었는지 모르겠다. brute force를 거의 안 풀어봐서 그런가? 하여튼 오늘은 반드시 끝장내주겠어. 지금은 2시 32분이므로 3시까지 끝내보겠다. ..3시 10분까지는 인정해줄게.

<문제>
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
고른 수열은 오름차순이어야 한다.

<입력>
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

<출력>
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.

실화냐 3시 10분까지 풀라고 했는데 3시 30분이다. c++로 풀다가 너무 귀찮아서 파이썬으로 갈아탔더니 파이썬 다 까먹어서 리스트 함수 찾는데 모든 시간을 썼다.. 그냥 처음부터 c++로 할 걸..ㅋㅋ

내 풀이 :

def function(num):
    l = len(answer)
    if(l==m):
        for k in answer:
            print(k, end=' ')
        print()
        return
####         
    else:
        for i in range(num, n+1):
            if not visited[i-1] :
                visited[i-1] = True
                answer.append(i)
                function(i+1)
                visited[i-1] = False
                answer.pop()

n, m = map(int, input("").split())
visited = [False for _ in range(n)]
answer = []
function(1)

c++로도 다시 바꿔보았다.

#include <iostream>
using namespace std;
bool Visited[8] = {false, };
int answer[8];
int n, m;

void function(int num, int current){
    if(current==m){
        for (int i=0;i<m;i++){
            cout<<answer[i]<<' ';
        }cout<<'\n';
        return;
    }
    
    else{
        for(int i=num;i<n+1;i++){
            if (!Visited[i-1]){
                Visited[i-1]= true;
                answer[current] = i;
                function(i+1, current+1);
                Visited[i-1] = false;
            }
        }
    }
}

int main(){
    cin>>n>>m;
    
    function(1, 0);
}

만들 순열의 첫 번째 원소를 1부터 시작해서 방문하지 않은 점에 대하여(!visited) 만든 수열의 원소 개수가 m이 될 때까지 방문하여 모든 가능한 경우를 출력한다. 방문한 점은 제외하고 그 다음 원소로 넘어간 다는 점에서 불가능한 경우는 가지치기하는 백트래킹 알고리즘이라고 할 수 있다.