9663번: N-Queen (백트래킹)
www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net # N-Queen # https://www.acmicpc.net/problem/9663 (백트래킹) # N이 4일때 [[1, 3, 0, 2], [2, 0, 3, 1]] 2개 경우가 있다 def check(a, row, col): for r, c in enumerate(a): if col == c or abs(col - c) == abs(row - r): return False return True def recursive(ro..
3-3. [그래프 탐색] 백트래킹
1. N Queen 문제 def check(a, row, col): for r, c in enumerate(a): if col == c or abs(col - c) == abs(row - r): return False return True def recursive(row, a): global result if row == 4: result.append(a[:]) return for col in [0, 1, 2, 3]: if check(a, row, col): # 가지치기 (이전 퀀의 위치에 따라 탐색 제외) a.append(col) recursive(row + 1, a) a.pop() result = [] recursive(0, []) print(result) # [[1, 3, 0, 2], [2, 0, ..
1781번: 컵라면 (탐욕)
www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net # 컵라면 # https://www.acmicpc.net/problem/1781 (탐욕) import sys import heapq # problems: [(1, 6), (1, 7), (2, 4), (2, 5), (3, 2), (3, 1), (6, 1)] def run(N, problems): problems.sort(key=lambda x: x[0]) # ((데드라인 순서로 선택해서)) 문제를 푼다 solved = [..
1092번: 배 (탐욕)
www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net # 배 # https://www.acmicpc.net/problem/1092 (탐욕) # boxes : [8, 8, 4, 2, 2] # cranes : [ 6, 9, 8 ] # crane_queue: [[4, 2], [8, 2], [8]] def run(cranes, boxes): boxes.sort(reverse=True) # ((큰 박스 순서대로 선택해서)) 처리한다 crane_queue =..
