본문 바로가기

알고리즘/브루트포스

(8)

[백준] 2309번 일곱 난쟁이 java [브루트포스][엄탱] 문제 링크 https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 문제 설명 백설공주는 일곱 난쟁이와 같이 사는데, 어디 갔다 오니 두 명이 추가되어 아홉 난쟁이가 되었다. 여기서 진짜 일곱 난쟁이를 찾는 문제다. 단, 진짜 일곱 난쟁이 키의 합은 100이다. 해설 단순하게 아홉 난쟁이 키에서 두명을 뺐을 경우 키의 합이 100이 되는 경우를 찾아서 일곱 명의 키를 출력하면 된다. 여기서 두명의 난쟁이를 찾을 때 브루트포스 알고리즘을 사용하면 된다. 코드 im..

[자바]백준 3085번 사탕게임[브루트포스][엄탱] 문제 링크 https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 문제 설명 해당 문제는 아래와 같은데 잘 이해가 안 되었다. N x N 크기의 보드에 사탕을 채워 놓았고 사탕의 4가지 색상 중 어느 것이든 놓일 수 있다. 이때, 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다. 사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오. 여기서 파란색으로 칠한..

[자바]백준 1476번 날짜 계산[브루트포스][엄탱] 문제 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19) 우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1년이 지날 때마다, 세 수는 모두 1씩 증가한다. 만약, 어떤 수가 범위를 넘어가는 경우에는 1이 된다. 예를 들어, 15년은 15 15 15로 나타낼 수 있다. 하지만, 1년이 지나서 16년이 되면 16 16 16이 아니라 1 16 16이 된다. ..

[자바]백준 1018번 체스판 다시 칠하기[브루트포스][엄탱] 문제 링크 https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제 풀이 간단하게 설명해서 W와 B가 칠해져 있는 M x N 크기의 보드에서 8 x 8 크기로 잘라서 체스판을 만들려고 한다. 체스판은 W와 B가 교차해야 하는데 M x N 크기의 보드에서 8 x 8을 잘랐을 때 W와 B가 교차하는 체스판을 만들기 위해서 W 혹은 B를 다시 칠해야 하는 정사각형 개수의 최솟값을 구하는 문제이다. 예를 들어서, 9x9 크기의 보드에서는 8x8 크..

[자바]백준 7568번 덩치[브루트포스][엄탱] 문제 링크 https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 문제 설명 몸무게와 키가 주어지는 N명 집단에서 각 사람마다 등치의 등수를 출력하면 된다. 단, 몸무게와 키 둘 다 커야지만 등치가 큰 것이며 등수가 높은 것이다(1에 가까울수록 높다) 해설 해당 문제는 알고리즘 분류가 브루트포스이며, 최대 50명 이기 때문에 이중 for문을 사용해도 최대 경우의 수가 2500번 이기 때문에 완전탐색을 사용해도 좋을 것 같다. 완전탐색을 한..

[자바]백준 2231번 분해합[브루트포스][엄탱] 문제 링크 https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 해설 해당 문제는 브루트포스 알고리즘으로 분류 되어 있다. 또한, 주어진 자연수의 범위가 최대 1,000,000 이고 자리수는 최대 7번 이기 때문에 최악의 경우의 수는 7,000,000 이다. 물론, 주어진 수가 1,000,000이면 당연히 1,000,000이 답이 될 수 없어서 최악의 경우의 수가 7,000,000보다 작다 하지만 브루트포스 알고리즘은 무..

[자바]백준 2798번 블랙잭 [브루트포스][엄탱] 문제 링크 https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 문제 설명 블랙잭은 기준 점수를 21에 가깝게 최대한 카드의 합을 크게 만드는 게임이다. 이 문제에서는 블랙잭의 기준 점수를 랜덤 하게 주고 주어진 수들에서 3장을 뽑아 기준 점수에 가깝게 최대한의 카드의 합을 구하는 문제이다. 해설 해당 문제는 알고리즘 분류가 브루트포스 알고리즘으로 되어 있다. 또한, 입력에서 보면 카드의 개수가 100 이하여서 완전탐..

브루트 포스 알고리즘[엄탱] 브루트 포스(brute force) 브루트 포스란? 브루트 포스의 사전적 의미를 보면brute은 “무식한, 짐승 같은, 난폭한”이라는 뜻이고, brute force는 “무식한 힘, 난폭한 힘, 폭력”이라는 뜻을 갖고 있습니다. 브루트 포스 알고리즘은 사전적 의미에서 느낄 수 있듯이 난폭하게, 무식하게 탐색하는 알고리즘이며, 전체 탐색 알고리즘입니다. 브루트 포스의 종류 전체 탐색에는 기본적으로 3가지 방법이 존재합니다. 순차 탐색 - 선형 구조를 순차적으로 탐색 DFS(깊이 우선 탐색) - 비선형구조를 점점 더 깊게 깊이를 우선적으로 탐색하는 방법 BFS(너비 우선 탐색) - 비선형구조를 너비를 기준으로 탐색하는 방법 추가적으로 브루트 포스 알고리즘에서 조금 더 발전된 알고리즘이 탐색을 진행하면서 조건에..

이전 1 다음

티스토리툴바