본문 바로가기

Algorithm(CodeTree, Python)/Backtracking18

[코드트리] 외판원 순회 Python # n 입력 n = int(input()) # costs costs = [ list(map(int, input().split())) for _ in range(n) ] # 함수들 # get_min_cost(curr_path) def get_min_cost(curr_path): # curr_loc, curr_cost curr_loc, curr_cost = 0, 0 for next_loc in curr_path: # 비용이 0인게 있으면 if not costs[curr_loc][next_loc]: # 최대비용 처리 return sys.maxsize # 비용을 내고 curr_cost += costs[curr_loc][next_loc] # 움직여주기 curr_loc = next_loc # 마지막 비용이 0이면 .. 2023. 2. 7.
[코드트리] 수들의 합 최대화하기 Python # n 입력 n = int(input()) # grid 입력 grid = [ list(map(int, input().split())) for _ in range(n) ] # 함수들 # get_max_sum(curr_comb) def get_max_sum(curr_comb): # curr_sum curr_sum = 0 for i in range(n): curr_sum += grid[i][curr_comb[i]] # 반환 return curr_sum # simulate(curr_idx) def simulate(curr_idx): # 전역 변수 선언 global max_sum # 종료조건 if curr_idx == n: # max_sum update max_sum = max(max_sum, get_max_su.. 2023. 2. 7.
[코드트리] 수들 중 최솟값 최대화하기 Python # n 입력 n = int(input()) # grid 입력 grid = [ list(map(int, input().split())) for _ in range(n) ] # 함수들 # get_max_min(curr_comb) def get_max_min(curr_comb): # curr_min curr_min = 10001 # grid의 각 행을 돌면서 for i in range(n): # curr_min update curr_min = min(curr_min, grid[i][curr_comb[i]]) # 반환 return curr_min # simulate(curr_idx) def simulate(curr_idx): # 전역 변수 선언 global max_min # 종료조건 if curr_idx == .. 2023. 2. 7.
[코드트리] 거꾸로 순열 Python # n 입력 n = int(input()) # 함수들 # print_comb() def print_comb(): for num in comb: print(num, end=' ') print() # make_comb(curr_idx) def make_comb(curr_idx): # 종료 조건 if curr_idx == n: print_comb() return # 넣어 주기 for i in range(n, 0, -1): if visited[i]: continue comb.append(i) visited[i] = True make_comb(curr_idx + 1) comb.pop() visited[i] = False # 설계 # comb, visited comb, visited = [], [False for .. 2023. 2. 7.
[코드트리] 크기가 n인 순열 Python # n 입력 n = int(input()) # 함수들 # print_ans() def print_ans(): for num in combs: print(num, end=' ') print() # make_comb(curr_idx) def make_comb(curr_idx): # 종료조건 if curr_idx == n: print_ans() return # 넣어주기 for i in range(1, n+1): # 방문한 곳이면 if visited[i]: continue combs.append(i) visited[i] = True make_comb(curr_idx + 1) combs.pop() visited[i] = False # 설계 # combs, visited combs, visited = [], [Fa.. 2023. 2. 7.
[코드트리] 2n개 중에 n개의 숫자를 적절하게 고르기 Python # n, m 입력 n, m = map(int, input().split()) # points points = [ tuple(map(int, input().split())) for _ in range(n) ] # calc(curr_comb) def calc(curr_comb): # max_dist max_dist = 0 for i in range(m-1): for j in range(i+1, m): # x1, y1, x2, y2 unpacking x1, y1 = curr_comb[i] x2, y2 = curr_comb[j] # curr_dist curr_dist = (x1 - x2) ** 2 + (y1 - y2) ** 2 # max_dist update max_dist = max(max_dist, curr.. 2023. 2. 3.
[코드트리] 2n개 중에 n개의 숫자를 적절하게 고르기 Python # n 입력 n = int(input()) # num_list num_list = list(map(int, input().split())) # 함수들 # calc(g_1, g_2) def calc(g_1, g_2): # sum_1, sum_2 sum_1, sum_2 = sum(g_1), sum(g_2) # 반환 return abs(sum_1 - sum_2) # simulate(curr_idx, cnt) def simulate(curr_idx, cnt): # 전역 변수 선언 global min_diff # 종료조건 # 끝에 닿고 if curr_idx == 2*n: # 원하는 만큼의 숫자를 썼으면 if cnt == n: # min_diff update min_diff = min(min_diff, calc(g.. 2023. 2. 2.
[코드트리] xor 결과 최대 만들기 Python # n, m 입력 n, m = map(int, input().split()) # num_list num_list = list(map(int, input().split())) # 함수들 # calc(curr_comb) def calc(curr_comb): # curr_result curr_result = 0 # 계산 시작 for num in curr_comb: curr_result = curr_result ^ num # 반환 return curr_result # simulate(curr_idx, cnt) def simulate(curr_idx, cnt): # 전역 변수 선언 global max_num # 종료 조건 # 끝까지 닿고, if curr_idx == n: # 다 썼으면, if cnt == m: #.. 2023. 2. 2.
[코드트리] 단순한 동전 챙기기 Python # n 입력 n = int(input()) # grid 입력 grid = [ input() for _ in range(n) ] # 함수들 # get_min_dist(curr_comb) def get_min_dist(curr_comb): # num_1, num_2, num_3 num_1, num_2, num_3 = curr_comb[0], curr_comb[1], curr_comb[2] # grid를 돌면서 for i in range(n): for j in range(n): # 'S'를 찾으면, if grid[i][j] == 'S': # sx, sy 기록 sx, sy = i, j # 'E'를 찾으면, elif grid[i][j] == 'E': # ex, ey 기록 ex, ey = i, j # num_1을 .. 2023. 2. 1.
[코드트리] n개 중에 m개 뽑기 Python # n, m n, m = map(int, input().split()) # 함수들 # print_ans() def print_ans(): for a in ans: print(a, end=' ') print() # make_comb(curr_idx) def make_comb(curr_idx): # 종료조건 if curr_idx == m+1: print_ans() return # 숫자 넣어주기 for i in range(1, n+1): # 오름차순으로 만들기 if curr_idx >= 2 and ans[-1] >= i: continue else: ans.append(i) make_comb(curr_idx + 1) ans.pop() # 설계 # ans ans = [] # make_comb make_comb(1) 2023. 2. 1.
[코드트리] 1차원 윷놀이 Python # n, m, k 입력 n, m, k = map(int, input().split()) # jump_list jump_list = list(map(int, input().split())) # calc(cubb_comb) def calc(curr_comb): # horses horses = [0, 0, 0, 0] # 이동시키기 for i in range(n): horses[comb[i]] += jump_list[i] # curr_point curr_point = 0 # 전부 이동시킨 말들을 확인 for horse in horses: # 도착했으면 if horse >= m-1: # curr_point 올려주기 curr_point += 1 # 반환 return curr_point # make_comb(curr.. 2023. 1. 31.
[코드트리] 최소 점프 횟수 Python # n 입력 n = int(input()) # num_list 입력 num_list = list(map(int, input().split())) # 함수들 # is_possible(curr_idxs) def is_possible(curr_idxs): # 첫번째 안밟았으면 if curr_idxs[0] != 0: # 실패 return False # 중간에 끊겼는지 확인 for i in range(len(curr_idxs) - 1): # 다음 인덱스로 이동할 수 없으면 if curr_idxs[i] + num_list[curr_idxs[i]] < curr_idxs[i+1]: # 실패 return False # 마지막 점프가 닿지 않으면 if curr_idxs[-1] + num_list[curr_idxs[-1]].. 2023. 1. 31.
[코드트리] 특정 조건에 맞게 k개 중에 1개를 n번 뽑기 Python # k, n 입력 k, n = map(int, input().split()) # 함수들 # print_comb() def print_comb(): for num in comb: print(num, end=' ') print() # make_comb(curr_idx) def make_comb(curr_idx): # 종료조건 if curr_idx == n + 1: # 출력 print_comb() return # 숫자 넣어주기 for i in range(1, k+1): # 3번째 자리 이상에서, 앞에 두개랑 같으면 if curr_idx >= 3 and comb[-2] == i and comb[-1] == i: # skip continue # 이외에는 else: comb.append(i) make_comb(cu.. 2023. 1. 30.
[코드트리] 알파벳과 사칙연산 Python # 식 입력 a = input() # 함수들 # get_num(curr_a) def get_num(curr_a): # ans ans = curr_a[0] for i in range(len(curr_a)): # -를 만나면 if curr_a[i] == '-': # ans update ans = ans - curr_a[i+1] # +를 만나면 elif curr_a[i] == '+': # ans update ans = ans + curr_a[i+1] # *를 만나면 elif curr_a[i] == '*': # ans update ans = ans * curr_a[i+1] # 반환 return ans # calc(curr_alphabets) def calc(curr_alphabets): # curr_a curr.. 2023. 1. 29.
[코드트리] 겹치지 않게 선분 고르기 Python # n 입력 n = int(input()) # segment segment = [] # 선분 입력 for _ in range(n): segment.append(tuple(map(int, input().split()))) # is_duplicated(curr_segment_idx) def is_duplicated(curr_segment_idx): # linear linear = [ 0 for _ in range(1001) ] # 표시해주기 for idx in curr_segment_idx: # unpacking sx, ex = segment[idx] for i in range(sx, ex + 1): linear[i] += 1 # linear을 돌면서 for i in range(1001): # 겹치는게 발견.. 2023. 1. 28.
[코드트리] 아름다운 수 Python # n 입력 n = int(input()) # is_beautiful(curr_num_list) def is_beautiful(curr_num_list): # curr_cnt curr_cnt = 1 # curr_num_list를 돌면서 for i in range(n-1): # 다음 수와 같으면 if curr_num_list[i] == curr_num_list[i+1]: # curr_cnt 올려줌 curr_cnt += 1 # 다음 수와 다르면 elif curr_num_list[i] != curr_num_list[i+1]: # curr_cnt를 현재 수로 나눴을 때 나누어 떨어지지 않으면 if curr_cnt % curr_num_list[i]: # 실패 return False # curr_cnt 초기화 cu.. 2023. 1. 28.
[코드트리] 강력한 폭발 Python 폭탄이파괴시킨영역이 폭탄일경우를생각해야한다. # n 입력 n = int(input()) # grid 입력 grid = [ list(map(int, input().split())) for _ in range(n) ] # 함수들 # in_range(x, y) def in_range(x, y): return 0 2023. 1. 27.
[코드트리] k개 중에 1개를 n번 뽑기 Python # k, n 입력 k, n = map(int, input().split()) # 함수들 # print_ans() def print_ans(): for num in ans_list: print(num, end=' ') print() # choose(curr_idx) def choose(curr_idx): # 종료조건 if curr_idx == n + 1: # 출력 print_ans() return # 넣어주기 for i in range(1, k+1): # 넣고 ans_list.append(i) # 다음자리로 choose(curr_idx + 1) # 빼주기 ans_list.pop() # 설계 # ans_list ans_list = [] # choose choose(1) 2023. 1. 27.

티스토리툴바