백트래킹

[python] 백준 - 1174. 줄어드는 숫자

🤔문제 해결 못풀다가 문제 유형에 백트래킹이 있길래 힌트를 얻어 백트래킹으로 구현해봤다. 아이디어는 현재 숫자의 끝자리보다 낮은 숫자들을 뒤에 추가하는 재귀함수를 만들었다. 현재 764이면 7640 => 끝 7641 => 76410 => 끝 7642 => 76420 => 76421 => 764210 => 끝 마지막에 sort만 해주면 빠른 시간 내에 모든 경우의 수를 순서대로 다 얻을 수 있다. 가끔 안풀리면 다른 사람의 코드를 참고하기 전에 유형으로 힌트를 얻어보자😀 💻소스 코드 N = int(input()) # 백트래킹을 이용한 문제 풀이 def bt(cur): answer.append(int(cur)) for j in range(0, int(cur[-1])): # 현재 숫자의 끝자리보다 낮은 숫자들..

[python] 백준 - 14889. 스타트와 링크

🤔문제 해결 S3 | 브루트포스, 백트래킹 재귀 함수를 이용하여 A팀을 구한다. 전체 멤버의 절반이 될 때까지 팀을 구성 set으로 구한다. ( 교집합을 사용해서 B팀을 구하기 위해 ) 두 팀을 구했으면 각 팀의 모든 조합을 테이블에서 값을 계산해서 구해준다 이번에는 콤비네이션 모듈을 사용했다. 테이블의 값을 모두 더해주고 두 팀의 총합을 빼준뒤 절대값을 씌워서 차이를 구한다. 최소값으로 답을 갱신해준다. 💨 팀을 구할 때 콤비네이션을 쓰지 않은 이유는 콤비네이션은 모든 경우의 수를 구하기 때문 전체 회원 [0, 1, 2, 3] 일 때 A 팀이 0,1 B팀이 1,2 인 경우와 A 팀이 2,3 B팀이 0,1 인 경우의 답은 같지만 콤비네이션은 이 두가지 경우를 구하므로 비효율적 💻소스 코드 from ite..

[python] 프로그래머스 - N-Queen

🤔문제 해결 Lv3 | 백트래킹, DFS 규칙은 체스말의 좌우, 위아래, 대각선 모두 겹치지 않게 하는 것이다! 하지만 모든 규칙을 하나하나 체크하면 효율성 마지막에서 시간초과가 발생한다! 위아래 규칙: visited 리스트를 만들어서 세로(열) 한칸에 하나씩만 들어갈 수 있게 한다. 좌우 규칙: 한번 말을 놓으면 무조건 다음 행으로 넘어간다. 대각선 규칙: 말을 놓을 준비를 하고, 그 자리의 왼쪽 위대각선과, 오른쪽 위대각선에 말이 있는지 체크! 마지막 행까지 말을 둘 수 있으면 성공! 💨 💻소스 코드 def solution(n): answer = 0 chess = [[0] * n for _ in range(n)] # 체스판 visited = [0] * (n + 1) # 세로칸 방문 체크 # 조건에 일..