본문 바로가기

Algorithm/Brute Force

 (122)
(C++) - 백준(BOJ) 17825번 : 주사위 윷놀이 www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 처음에는 시작 칸에 말 4개가 있다. 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 www.acmicpc.net brute force로 푼 문제였습니다. 풀이방법 1. 먼저 윷판을 만듭니다. 각 위치를 파란색 글씨로 넣어 보았습니다. 해당 위치에는 6개의 정보가 들어있는 2차원 배열로 표현합니다. 정보는 배열의 한 인덱스(위치) => {해당 위치의 점수, 주사위 1이 나왔을 때 다음위치, 2가 나왔을때, 3... , 4... , 5... }가 됩니다. 2. 4개의 말의 위치정보를 비트로 표현합니다. 한 턴당 비트 2개로 ..
(C++) - 프로그래머스(고득점 kit - 완전탐색) : 까펫 programmers.co.kr/learn/courses/30/lessons/42842 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 programmers.co.kr brute force문제였습니다. 풀이방법 다음 공식이 성립합니다. yellow = (answer.first - 2) * (answer.second - 2) brown = answer.first * answer.second - yellow yellow에 대입한다면 brown = answer.first * answer.second - (answer.first - 2) * (..
(C++) - 프로그래머스(고득점 kit - 완전탐색) : 소수 찾기 programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr dfs를 이용한 완전탐색 문제였습니다. 풀이방법 1. num.size()만큼 있는 종이 조각들을 1개부터 ~ num.size()까지 뽑아봅니다. 조합으로 뽑는게 아닌 순서가 상관있는 순열로 뽑으므로 내가 뽑았던 index를 check하기 위한 배열이 필요합니다. 2. 정해진 개수만큼 뽑았다면 해당 수의 소수여부를 판별합니다. 이때 뽑은 수가 이미 판별된 수라면 ..
(C++) - 백준(BOJ) 2659번 : 십자카드 문제 www.acmicpc.net/problem/2659 2659번: 십자카드 문제 입력은 한 줄로 이루어지며, 이 한 줄은 카드의 네 모서리에 씌여있는 1 이상 9 이하의 숫자 4개가 시계 방향으로 입력된다. 각 숫자 사이에는 빈칸이 하나 있다. www.acmicpc.net 모든 경우의 수를 확인하는 brute force문제였습니다. 풀이방법 1. 1111부터 9999까지의 모든 숫자카드를 확인합니다. 2. 한 숫자카드의 시계수를 구합니다. dqeue을 이용해 4개의 경우로 시계수를 만든 후 가장 작은 시계수를 반환합니다. 3. 한 시계수가 이전 시계수들보타 크다면 ans++ 후 값을 그 시계수로 갱신해줍니다. 4. 만약 현재 시계수가 입력받은 십자카드로부터 나온 시계수와 같다면 답을 출력하고 loop를 탈..
(C++) - 백준(BOJ) 14889번 : 스타트와 링크 답 www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net backtracking을 이용한 문제였습니다. 풀이방법 1. backtracking을 이용해 n/2인원을 뽑습니다. 이 때 뽑히지 않은 인원을 상대편 팀으로 생각하면 됩니다. 2. n/2인원을 뽑았다면 시너지를 계산합니다. Code #include using namespace std; int n; int team[20][20]; int check[20]; int ans = 0x7f7f7f7f; int getSynergy(vector..
(C++) - 백준(BOJ) 2304번 : 창고 다각형 답 www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 풀이 및 구현방법을 생각하기 어려웠던 brute force문제였습니다. 풀이방법 빛을 왼편에서 쬐었을 때와 오른편에서 쬐었을 때 빛이 부딪힌 후 그림자와 빛이 비춰지는 모습이 어떻게 구성이 되는가에 대한 생각에서 착안했습니다. 1. 1번으로 빛을 쪼였다고 가정해봅시다. 이 때 가장 긴 가운데 (높이가 10짜리) 봉은 갈색 빛이 그 오른편 기둥들의 꼭대기를 비출 수 없도록 하고 있습니다. 2. 2..
(C++) - 백준(BOJ) 1145번 : 적어도 대부분의 배수 답 www.acmicpc.net/problem/1145 1145번: 적어도 대부분의 배수 첫째 줄에 다섯 개의 자연수가 주어진다. 100보다 작거나 같은 자연수이고, 서로 다른 수이다. www.acmicpc.net brute force문제였습니다. 풀이방법 나누어 떨어지는 숫자의 개수가 3개 이상이 될 때까지 수를 1씩 증가시킵니다. Code #include using namespace std; int num[5]; int ans = 1; int getCnt(int n){ int cnt = 0; for(int i = 0; i > num[i]..
(C++) - 백준(BOJ) 2160번 : 그림 비교 답 www.acmicpc.net/problem/2160 2160번: 그림 비교 N(2≤N≤50)개의 그림이 있다. 각각의 그림은 5×7의 크기이고, 두 가지 색으로 되어 있다. 이때 두 가지의 색을 각각 ‘X’와 ‘.’으로 표현하기로 하자. 이러한 그림들이 주어졌을 때, 가장 비슷 www.acmicpc.net 구현해 brute force하는 문제였습니다. 풀이방법 1. 모든 그림 쌍에 대해 다른 정도를 비교해 계속 그림 정보를 갱신해줍니다. 2. 답이 한 개이므로 다른 정도 같은 여러 그림의 쌍을 생각할 필요가 없습니다. Code #include using namespace std; int n; vector picture; int minPic[2]; int minPivot = 0x7f7f7f7f; int g..

티스토리툴바