백준 - 15655번 N과 M (6) python 문제풀이 [Hellfer]

https://www.acmicpc.net/problem/15655

15655번: N과 M (6)

🔷 알고리즘 분류 - 백트래킹, 난이도 - 실버 3

 

백트래킹(Backtracking) 알고리즘은 결정해야 하는 여러 개의 선택지가 있고, 이 중에서 최적의 해결책을 찾아내야 하는 문제들에 대해 사용됩니다. 이 알고리즘은 모든 가능한 경로를 탐색하되, 어떤 경로가 해결책으로 이어질 것 같지 않으면 그 경로를 더 이상 탐색하지 않고 다른 경로를 탐색하는 방식으로 동작합니다.

이런 방식을 통해 불필요한 계산을 줄이고 탐색의 효율성을 높일 수 있습니다. 이를 위해 백트래킹 알고리즘은 주로 재귀 함수를 이용해 구현되며, 일반적으로 DFS(깊이 우선 탐색) 방식을 사용합니다.

예를 들어, 스도쿠 문제를 백트래킹으로 해결한다고 가정해 봅시다. 스도쿠 문제는 빈칸을 1부터 9까지의 숫자로 채우는 문제인데, 이때 각 행, 각 열, 그리고 3x3 크기의 작은 사각형에 1부터 9까지의 숫자가 중복 없이 들어가야 합니다.

백트래킹을 이용하면 빈 칸에 1부터 9까지 숫자를 하나씩 넣어보면서 진행합니다. 만약 어떤 숫자를 넣었을 때 규칙에 어긋나게 된다면, 그 숫자를 빼고 다음 숫자를 넣어보는 과정을 반복합니다. 이렇게 해서 모든 빈칸을 규칙에 맞게 채울 수 있으면 문제의 해결책을 찾은 것이고, 그렇지 않다면 다른 경로를 탐색합니다.

백트래킹 알고리즘은 이렇게 가능한 모든 경로를 체계적으로 탐색하되, 해결책이 될 수 없다는 것이 밝혀진 즉시 그 경로는 포기하고 다른 경로를 탐색하는 방식을 사용합니다. 이를 통해 불필요한 계산을 줄이고, 효율적으로 문제를 해결할 수 있습니다.

 

🔶첫 번째 풀이 - 재귀(def backtracking)를 이용한 풀이

def backtracking(n, m, result, start):
    if len(result) == m:  # 만약 result의 길이가 m과 같다면(즉, m개의 원소를 모두 골랐다면)
        print(' '.join(map(str, result)))  # result를 공백으로 구분하여 출력
        return

    for i in range(start, len(x)):  # start부터 n까지의 각 원소에 대하여
        result.append(x[i])  # result에 x[i]를 추가
        backtracking(n, m, result, i+1)  # 재귀적으로 탐색, 시작 인덱스를 1 증가시킴
        result.pop()  # result에서 마지막 원소를 제거(백트래킹)

n, m = map(int, input().split())  # n과 m을 입력 받음
x = list(map(int, input().split()))  # 수열 x를 입력 받음
x = sorted(x)  # x를 오름차순으로 정렬
result = []  # 선택된 원소를 저장할 리스트 초기화
backtracking(n, m, result, 0)  # 백트래킹 시작

 

🔶두 번째 풀이 - 파이썬의 내장 모듈인 itertools의 combinations 함수 이용

- itertools 라이브러리의 combinations 함수를 사용하여 같은 문제를 풀 수 있습니다.

combinations 함수를 이용해 수열 x에서 m개의 원소를 고르는 모든 조합을 생성하고, 이를 공백으로 구분하여 출력합니다.

 

from itertools import combinations  # combinations 함수 호출

n, m = map(int, input().split())  # n과 m을 입력 받음
x = list(map(int, input().split()))  # 수열 x를 입력 받음
x = sorted(x)  # x를 오름차순으로 정렬

for i in combinations(x, m):  # x에서 m개의 원소를 고르는 모든 조합에 대하여
    print(' '.join(map(str, i)))  # 조합을 공백으로 구분하여 출력

🔶 초보자를 위한 코드풀이

- print(' '. join(map(str, result)))

 

result = [1, 2, 3, 4, 5]

# map 함수를 이용해 결과 리스트의 모든 원소를 문자열로 변환
result_as_str = map(str, result)

# join 함수를 이용해 결과 리스트의 모든 원소를 공백으로 연결
result_joined = ' '.join(result_as_str)

print(result_joined)  # 출력: 1 2 3 4 5

 

 

위 풀이 중 참고하여 알고리즘 공부에 도움 되셨으면 좋겠습니다.

 

🤗파이팅입니다~ 여러분!!🤗