본문 바로가기
반응형

완전탐색10

04. Brute-force Search(2) Brute Force and Exhaustive Search 01. Brute Force A straightforward approach to solving a problem, usually directly based on the problem’s statement and definitions of the concepts involved “just do it!” the brute-force strategy is the one that is easiest to apply Examples: Computing 𝒂^𝒏(𝒂>𝟎, 𝒏 a nonnegative integer) : multiplying 1 by 𝑎 𝑛 times Computing 𝒏! The consecutive integer checking algo.. 2021. 11. 16.
03. Brute-force Search(1) 완전 탐색. 모든 경우를 다 생각하는 것입니다. 수학을 배울 때 끔찍한 기억이 떠오르는군요. 분명히 뭔 이야기를 하는지는 알겠는데 간단하게 풀자니 자신이 없어서 모든 경우를 다 고려해서 문제를 풀었던 기억 말입니다. 물론 완전탐색으로 원하는 시간 안에 다 풀리진 않습니다. 우리가 시간복잡도라는 것을 고안한 이유죠. https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 위의 문제가 좋은 예시가 될 수 있겠네요. 입력값이 최대 10만이죠. 모든 구간에 시도하면 1.. 2021. 11. 2.
02.08. 부분수열의 합[Brute-force Search][백준 1182] https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net Algorithm classification : Brute-force Search, Back tracking 02.08.1. Problem Write a program to find the number of cases in which the sum of all the elements of a subsequence among positive subsequences.. 2021. 11. 1.
02.07. 체스판 다시 칠하기[Brute-force Search][백준 1018] https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net Algorithm classification : Brute-force Search 02.07.1. Problem Jimin found an M×N board divided into MN unit squares in his mansion. Some squares are painted black, others are painted white. Jimin wants to cut this boar.. 2021. 11. 1.
02.06. 숫자 야구[Brute-force Search][백준 2503] https://www.acmicpc.net/problem/2503 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net Algorithm classification : Brute-force Search 02.06.1. Problem 정보문화진흥원 정보 영재 동아리에서 동아리 활동을 하던 영수와 민혁이는 쉬는 시간을 틈타 숫자야구 게임을 하기로 했다. 영수는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 마음속으로 생각한다. (예: 324) 민혁이는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세.. 2021. 11. 1.
02.05. 유레카 이론[Brute-force Search][백준 10448] https://www.acmicpc.net/problem/10448 10448번: 유레카 이론 프로그램은 표준입력을 사용한다. 테스트케이스의 개수는 입력의 첫 번째 줄에 주어진다. 각 테스트케이스는 한 줄에 자연수 K (3 ≤ K ≤ 1,000)가 하나씩 포함되어있는 T개의 라인으로 구성되어 www.acmicpc.net Algorithm classification : Brute-force Search, Math 02.05.1. Problem 삼각수 Tn(n ≥ 1)는 [그림]에서와 같이 기하학적으로 일정한 모양의 규칙을 갖는 점들의 모음으로 표현될 수 있다. 자연수 n에 대해 n ≥ 1의 삼각수Tn는 명백한 공식이 있다. Tn = 1 + 2 + 3 + ... + n = n(n+1)/2 1796년, 가우스.. 2021. 11. 1.
반응형