백준 문제풀이(파이썬)/백트래킹

팀을 나눠서 각 선수들의 케미(상호간의 능력치)를 구하는 문제다. 문제를 읽어보니 일단 N명의 선수를 받은 뒤 반으로 나누어서 팀을 구하고 각 팀 인원들의 케미를 구하면 되겠구나 싶었다. 팀을 나눌 때는 팀 하나가 정해지면 다른 팀은 바로 결정이 되기 때문에 두 팀을 따로 구할 필요가 없다. 팀을 나누려면 N과 M(1)문제에서 사용한 방법을 응용하면 된다. 백준 15649번 - N과 M(1) 완전 탐색중의 한 방법인 백트래킹 알고리즘에 대한 문제이다. 백트래킹의 특징은 탐색과정 중에 정답이 될 수 없는 조건에 해당되면 가지치기(Pruning)하여 효율을 높일 수 있다는 점이다. DFS와 aodtns.tistory.com 만약 N = 4라고 생각해 보면, A팀은 (0,1), (0,2), (0,3) 의 세 ..

처음에 문제를 보고 숫자도 문자열로 받은 뒤 입력 개수만큼 문자'+','-','x','//'를 받아서 하나씩 빼주면서 정수로 변환해서 계산을 해야겠다고 생각했다. 조금 복잡한 것 같지만 생각보다 그렇게 복잡하지는 않았다. 하지만 문제는 중복되는 순열도 모두 계산을 해야 하는 것이었다. 6개의 숫자를 받는다고 할 때 연산자가 만약 + + + - - 라고 할 때 내 계산을 그저 5! 의 경우를 모두 계산했다. 중복 문제를 해결하지 못했다. 그래도 예제의 출력 값은 제대로 나와서 백준에 제출했을 때 적어도 시간 초과라도 뜨겠구나 싶었지만, 틀렸다고 나왔다. 어느 부분에서 출력의 오류가 있었는지는 잘 모르겠다. ##함수 선언 부분 def calculator(Numbers): global min, max if l..

스도쿠 빈칸을 채우는 문제다. 0이 있는 곳에 1부터 9까지 대입하면서 정답이 되지 않는 수이면 다시 후퇴하는 식으로 코드를 짰다. 일단 0이 있는 곳의 인덱스를 zero에 넣어준다. 그런 뒤 zero에서 하나씩 빼서 정답이 될 수 있는지 확인해준다. isRight는 가로줄, 세로줄, 3X3 정사각형에 확인하려는 숫자가 있으면 False를 반환해준다. 만약 True가 반환이 되면 sudoku배열에 정답을 넣어주고 index를 증가시켜 재귀 함수를 호출하고 다음 zero의 값을 똑같이 비교해준다. ##함수 선언 부분 import sys def SDK(index): if index == len(zero): for i in range(9): for j in range(9): print("%d" % (sudok..

N X N 체스판에서 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. 밑의 그림은 이 문제를 풀 때 어떤 식으로 백트래킹하는 지를 보여준다. 이를 구현하기 위해 N개의 행 or 열과 우상향 대각선과 우하향 대각선을 구현해줄 배열이 필요하다. 각 행 or 열에는 한개의 퀸만 들어갈 수 있기 때문에, 행 or 열 배열은 하나만 선언해주면 된다. 또한 left와 right 배열은 각각 index와 col의 합과 index와 col의 차가 같다는 점을 이용한다. 만약 index와 col의 합이 같으면 같은 우상향 대각선 상에 위치한다는 뜻이므로 퀸이 올 수 없다. ##함수 선언 부분 def Queen(index): global cnt_Queen if index == N: cnt_Queen += 1 return ..

완전 탐색중의 한 방법인 백트래킹 알고리즘에 대한 문제이다. 백트래킹의 특징은 탐색과정 중에 정답이 될 수 없는 조건에 해당되면 가지치기(Pruning)하여 효율을 높일 수 있다는 점이다. DFS와 유사하지만 DFS는 불필요한 경로를 사전에 차단할 수 없기 때문에 경우의 수를 줄이지 못한다. 백트래킹 문제는 트리를 그리면서 풀면 이해가 더 잘 된다. 예제 입력 2의 경우에, 각 숫자(부모 노드)에는 자식노드 1,2,3,4가 있는데, 정답이 아닌 조건(자기 자신 ex) 1 1 , 2 2,..)이면 다시 되돌아가서 진행(가지치기)해준다. 1부터 N까지 돌면서 M만큼 출력을 해줘야 한다. 그러므로 M 만큼의 배열을 선언해서 하나씩 넣어준 뒤 출력하고 다시 빼주는 식으로 코드를 짜면 되겠다. s는 탐색하면서 a..