[프로그래머스] 카펫 / 완전 탐색(Brute-force Search)

💭 문제 이해 갈색 타일의 개수와 노란색 타일의 개수가 입력으로 주어질 때, 전체 카펫의 가로 길이와 세로 길이를 구하는 문제이다. 수식으로 정리해본다면, 1. 가로를 테두리를 포함해서 \(x+2\) 로 표현하고, 세로는 테두리를 포함하여 \(y+2\) 로 표현한다. 2. 위 수식을 기준으로 전체 칸 수는 \((x+2)(y+2) = brown + yellow\) 로 표현할 수 있다. 3. 노란 부분은 \(xy = yellow\) 로 표현할 수 있다. 4. 전체 칸 수를 나타내는 수식을 전개하면 \(xy+2x+2y+4=brown+xy\) 가 되고, 이를 정리하면 \(x+y = \frac{brown-4}{2}\) 라는 관계가 성립된다. 즉, \(y = \frac{brown-4}{2}-x\) 관계를 만족하며 ..

→2021.03.18

[프로그래머스] 소수 찾기 / 완전 탐색(Brute-force Search)

💭 문제 이해 한 자리의 숫자들이 나열된 문자열을 조합해서 만들 수 있는 소수의 갯수를 구하는 문제이다. 파이썬의 기본 모듈인 itertools.permutations를 이용하여 모든 경우를 구하고, 소수 판별은 숫자 범위가 0~9로 적으므로 2~n-1까지 나눠보면서 직접 찾아냈다. 구현 언어: Python from itertools import permutations # 소수 판별 함수 def is_prime_number(num: int) -> bool: if num < 2: return False for i in range(2, num): if num % i == 0: return False return True def solution(numbers): answer = set() # 중복되지 않는 모..

→2021.03.17

[BOJ] 백준 1182 부분수열의 합 / 완전 탐색(Brute-force Search)

💣 문제 이해 N개 (20개 이하) 의 정수로 이루어진 수열이 입력으로 주어지고 그 수열 내에서 원소 개수가 양수인 부분수열 중 합이 S 인 수열의 개수를 구하라는 문제이다. 문제를 풀면서 DFS, 백트래킹이 생각났고, 실제 다른 블로거 분들도 그렇게 풀이를 하는 경우도 있었다. DFS와 백트래킹 문제풀이를 할 때, 그 방식으로도 풀어보기로 하고, 이번에도 또한 완전 탐색(Brute-force Search) 방식을 사용하기로 했다. (이름은 그렇고 암튼 재귀호출함..) 💭 풀이 과정 작성 언어: C++ #include int num[25] = {0,}; int inpCnt = 0, inpSum = 0, answer = 0; void count(int pIndex, int pSum){ pSum += num..

→2020.02.26

[BOJ] 백준 1018 체스판 다시 칠하기 / 완전 탐색(Brute-force Search)

💣 문제 이해 1. 입력받을 체스판은 8*8 이상의 크기를 가진다. 2. 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우 두 종류의 판으로 만들고자 한다. 3. 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 4. 8*8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠하려고 한다. 이때, 8*8 크기는 체스판 내 어디서든 고를 수 있다. 5. 다시 칠해야 하는 칸의 최소 개수를 찾아야 한다. 완전 탐색(Brute-force Search) 방식을 사용했다. 💭 풀이 과정 먼저 흰색 칸으로 시작하는 8*8 체스판과 검정색 칸으로 시작하는 8*8 체스판을 string 배열로 만들어두었다. 소스코드 진행 방식은 다음과 같다. 입..

→2020.02.25

[BOJ] 백준 2503 숫자 야구 / 완전 탐색(Brute-force Search)

💣 문제 이해 영수는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 마음속으로 생각한다. (예: 324) 민혁이는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 영수에게 묻는다. (예: 123) 민혁이가 말한 세 자리 수에 있는 숫자들 중 하나가 영수의 세 자리 수의 동일한 자리에 위치하면 스트라이크 한 번으로 센다. 숫자가 영수의 세 자리 수에 있긴 하나 다른 자리에 위치하면 볼 한 번으로 센다. 민혁이의 물음들과 각각의 물음에 대한 영수의 답이 입력으로 주어질 때 영수가 생각하고 있을 가능성이 있는 답의 총 개수를 출력하는 프로그램을 작성하시오. 문제에 제시된 다음과 같은 조건들을 정리하면 다음과 같다. 1. 영수와 민혁이가 생각한 수는 세 자리 수이고, 각 자리 수는..

→2020.02.24

[BOJ] 백준 3085 사탕 게임 / 완전 탐색(Brute-force Search)

* 예외 처리를 잘하자 💣 문제 이해 1. 행으로 인접한 두 칸을 고르고 교환한다(swap) 2. 행과 열에서 가장 길게 연속해있는 사탕개수를 찾는다. 3. 열로 인접한 두 칸을 고르고 교환한다(swap) 4. 행과 열에서 가장 길게 연속해있는 사탕개수를 찾는다. 보통 컴퓨터가 1초에 약 1억번의 연산을 한다. 이 문제에서 배열의 최대 크기라고 해봐야 50*50 이므로 단순하게 모든 경우를 하나하나 따져보아도 50*50*(50*50+50*50) = 12,500,000 이므로 완전 탐색(Brute-force Search) 방식을 사용하기로 했다. 💭 풀이 과정 작성 언어: C++ #include #include using namespace std; int num = 0; char arr[60][60] = ..

→2020.02.19