MeetInTheMiddle

Algorithm/Baekjoon Online Judge
[Java] 백준 1799 (비숍) Gold 2
Problem : https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net Approach 백트랙킹(Backtracking) 문제이다. 시간제한 10초이고, 체스판의 크기가 n x n 이라고 하여, N-Queens 문제와 같이 백트랙킹을 시도하면 시간초과가 날 것이다. N-Queens 에서는 임의의 행에 퀸을 하나 놓았다면, 그 행의 다른 열에 대해서는 검사를 하지 않았기에 가능하였다. 하지만, 여기서는 체스판의 요소가 모두 1이고(모든 곳에 비숍을 놓을 수 있..
→2021.04.17
Algorithm/Baekjoon Online Judge
[java] 백준 1450 (냅색문제) Gold 1
Problem : https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수이고, C는 10^9보다 작거나 같은 음이아닌 정수이고. 둘째 줄에 물건의 무게가 주어진다. 무게도 10^9보다 작거나 같은 자연수이다. www.acmicpc.net Approach meet in the middle 알고리즘을 적용하여 각각을 완전탐색 후 이진탐색을 수행하는 문제이다. meet in the middle 알고리즘을 간단하게 말하면 주어진 범위를 반으로 나누어 각각 처리하는 알고리즘이다. 문제에서 주어진 N이 최대 30이므로 완전탐색을 수행하려면 2^30번의 연산이 필요하다. 2^30은 대략 10억이지만, 절반인 2^15은 ..
→2021.01.27

• 이전
• 1
• 다음