본문 바로가기
728x90

백트래킹

백준 문제풀이 2023. 2. 8. [백준][파이썬] 14889 스타트와 링크 1.문제 분석 각 팀의 시너지 차이가 최소가 되도록 팀을 나누는 문제 백트래킹 활용 문제 2. 기본 아이디어 스타트 팀에 팀원을 배정하고 나머지 인원을 링크팀으로 배정한다. 차이를 계산한 후 다시 dfs를 진행한다. 3.문제 풀이 코드로 구현 def calcul(): # 시너지 계산 함수 global ans start_p, link_p = 0, 0 for i in range(n): if i not in s_team: l_team.append(i) for i in range(n//2 - 1): for j in range(i+1, n//2): start_p += player[s_team[i]][s_team[j]] + player[s_team[j]][s_team[i]] link_p += player[l_tea..
백준 문제풀이 2023. 2. 8. [백준][파이썬] 14888 연산자 끼워넣기 1.문제 분석 N개의 숫자 사이에 N-1개의 연산자를 넣어 최대, 최소 연산값을 만드는 문제 주어진 수의 순서는 바꿀 수 없고, 나눗셈은 몫만 취한다. 연산 규칙을 무시하고 앞에서부터 계산한다. 백트래킹 활용 문제 2. 기본 아이디어 연산자를 입력받아 각각의 연산자마다 탐색을 진행한다. 1부터 n까지, 탐색을 끝마치면 최대, 최솟값을 저장한다. 3.문제 풀이 코드로 구현 n = int(input()) lst = list(map(int, input().split())) add, sub, multi, div = map(int, input().split()) max_sum = -1000000000 min_sum = 1000000000 def backTracking(cnt, ans): global max_sum..
백준 문제풀이 2023. 1. 28. [백준][파이썬] 2580 스도쿠 1.문제 분석 스도쿠 판의 빈칸을 채우는 문제 가로, 세로, 사각형 모두 체크해야 한다. 2. 기본 아이디어 가로, 세로, 사각형을 체크할 함수를 구현한다. 빈 스도쿠 칸은 따로 리스트를 통해 빼둔다. 3.문제 풀이 빈칸의 좌표를 blank리스트에 따로 빼두었다. 이 빈칸의 좌표에 1~9까지의 숫자를 대입하며 가능성을 체크한다. def width(x, n): # x좌표 확인 for i in range(9): if (n == sudoku[x][i]): return False return True def height(y, n): # y좌표 확인 for i in range(9): if (n == sudoku[i][y]): return False return True def rectangle(x, y, n): ..
[백준][파이썬] 9663 N-Queen
백준 문제풀이 2023. 1. 27. [백준][파이썬] 9663 N-Queen 1.문제 분석 백트래킹 문제 N*N칸의 체스판에 N개의 퀸이 서로 공격하지 못하도록 한다. 2. 기본 아이디어 퀸은 한 행에 하나만 존재한다. ( N x N 칸에 N개의 퀸을 놓기 때문) 한 행에 퀸을 놓았다면 열, 대각선만 확인해주면 된다. 3.문제 풀이 2차원 배열을 통해 문제를 풀어야겠다고 생각했으나, 코드가 너무 복잡해졌다. 도무지 감이 안잡혀 구글링을 했고, 1차원 리스트로 표현할 수 있는 방법이 있다는 것을 알았다. 그리고 고민하던 중에 굳이 체스판을 입체적으로 생각하지 않아도 된다는 것을 알았다. (요즘 체스에 취미가 생긴 것이 한몫했다.) 체스판의 숫자와 알파벳을 1차원 리스트의 인덱스와 값이라고 생각하면 편리했다. 그러니까 chess[0] = 1 이라고 하면 윗 그림에서 흑 나이트 즉, ..
백준 문제풀이 2023. 1. 13. [백준][파이썬] 15652 N과 M (4) 1.문제 분석 중복을 포함한 비내림차순 수열을 출력하는 문제 백트래킹을 사용하는 문제 2. 기본 아이디어 매개변수로 num을 받아와 for문이 num부터 시작하도록 한다. 3.문제 풀이 i의 증가를 통해 재귀시마다 for문의 시작값을 증가시켜 비내림차순의 수열을 출력한다. n, m = map(int, input().split()) lst = [] def BackTracking(num): if len(lst) == m: print(" ".join(map(str, lst))) return for i in range(num, n + 1): # num을 i로 지정해 오름차순으로 출력한다. lst.append(i) # i not in lst를 사용하지 않아 중복을 허용한다. BackTracking(i) lst.p..
백준 문제풀이 2023. 1. 13. [백준][파이썬] 15651 N과 M (3) 1.문제 분석 1부터 n까지의 자연수 중 중복을 포함하여 m개의 수를 고른다. 백트래킹을 사용하는 문제 2. 기본 아이디어 N과 M (1)번 문제에서 if not i in lst 구문 대신 len(lst) != m 구문을 넣는다. 3.문제 풀이 len(lst) != m 구문은 리스트의 길이가 m이 되기 전까지 재귀를 반복한다. 따라서 리스트의 길이가 m이 되었을 때 중복 상관없이 출력할 수 있게 된다. n, m = map(int, input().split()) lst = [] def BackTracking(): if len(lst) == m: print(" ".join(map(str, lst))) for i in range(1, n + 1): if len(lst) != m: lst.append(i) Ba..
백준 문제풀이 2023. 1. 13. [백준][파이썬] 15650 N과 M (2) 1.문제 분석 숫자의 중복 없이 오름차순 수열만 출력하는 문제 백트래킹을 사용하는 문제 2. 기본 아이디어 N 과 M (1)번 문제에서 오름차순 수열만 가져오도록 코드를 수정한다. 3.문제 풀이 오름차순을 출력하는 방법으로 실제 오름차순 리스트와 비교하는 문장을 추가했다. n, m = map(int, input().split()) lst = [] def BackTracking(): if len(lst) == m: lst_sorted = sorted(lst) # 리스트와 그 리스트의 오름차순 리스트가 동일한지 비교 if(lst == lst_sorted): print(" ".join(map(str, lst))) for i in range(1, n + 1): if i not in lst: lst.append(..
백준 문제풀이 2023. 1. 12. [백준][파이썬] 15649 N과 M (1) 1.문제 분석 백트래킹을 사용하는 문제 조건에 맞게, 중복 없이 수를 나열해야 한다. 1 ~ n 범위의 자연수 m개를 중복없이 골라야 한다. 2. 기본 아이디어 백트래킹 함수를 구현한다. 조건문과 재귀를 이용한다. 3.문제 풀이 우선 백트래킹이란 무엇일까? https://walk-cat-dev.tistory.com/56 - 이 곳에 간단하게 정리해 놓았다. 파이썬 코드 n, m = map(int, input().split()) lst = [] def backTracking(): if len(lst) == m: # 조건에 맞으면 출력 print(' '. join(map(str, lst))) for i in range(1, n+1): if i not in lst: # 중복 제거 lst.append(i) ba..
[알고리즘] 백트래킹 (BackTracking)
Computer Science/Algorithms 2023. 1. 12. [알고리즘] 백트래킹 (BackTracking) 백트래킹이란? 재귀적으로 문제를 풀어나가는 알고리즘 특정 조건에 위배되면 가지치기를 함 ( 특정 노드를 제외하는 것 ) DFS를 사용하는 알고리즘 중에 백트래킹이 있다. ( DFS는 최적의 경로를 반환한다.) 백트래킹과 DFS의 차이점 DFS는 가능한 모든 경로를 탐색하므로, 가지치기를 하지 않는다. 백트래킹은 현재의 경로가 불필요하다면 다시 되돌아간다. DFS에서 조건문과 재귀를 통해 코드를 구현하면 백트래킹을 구현할 수 있다. 백트래킹의 구현, 예제 결론적으로 백트래킹은 DFS를 수행하고, 유망한 노드인지를 판단한 뒤 하위 노드로 이동하는 형식이다. 백트래킹을 이용한 문제 백준 - N과 M (1) https://walk-cat-dev.tistory.com/57
728x90

티스토리툴바