💡 완전 탐색(Exhaustive Search)이란? - 알고리즘에서 사용되는 기법 중 하나로 ‘모든 가능한 경우의 수를 탐색’하여 ‘최적의 결과를 찾는 방법’을 의미합니다.
알고리즘 종류
설명
부르트 포스
‘모든 경우의 수를 탐색’하면서 원하는 결과를 얻는 알고리즘을 의미합니다. ex) 좌물쇠를 푸는 방법과 같이 모든 경우를 대입하면서 비밀번호를 찾아가는 방법이 있습니다.
비트마스크
‘모든 경우의 수’를 이진수료 표현하고 ‘비트 연산’을 통해 원하는 결과를 빠르게 얻는 알고리즘을 의미합니다.
백트래킹
결과를 얻기 위해 진행하는 도중에 ‘막히게 되면’ 그 지점으로 다시 돌아가서 ‘다른 경로를 탐색’하는 방식을 의미합니다. 결국 모든 가능한 경우의 수를 탐색하여 해결책을 찾습니다.
순열 탐색
‘순열’을 이용하여 모든 경우의 수를 탐색하는 방법입니다. 순열은 서로 다른 n개 중에서 r개를 선택하여 나열하는 방법을 의미합니다
재귀함수
자기 자신을 호출하여 모든 가능한 경우의 수를 체크하면서 최적의 해답을 얻는 방식을 의미합니다.
DFS/BFS
1. 깊이 우선 탐색(DFS: Depth-First Search) - 루트 노드에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법을 의미합니다.
2. 너비 우선 탐색(Breadth-First Search: BFS) - 루트 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법을 의미합니다.
1. 문제 - 브루트 포스 : 최소 직사각형
💡 문제 설명
- 명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다. 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 합니다. 이러한 요건을 만족하는 지갑을 만들기 위해 디자인팀은 모든 명함의 가로길이와 세로 길이를 조사했습니다. 아래 표는 4가지 명함의 가로길이와 세로 길이를 나타냅니다.
<하단의 표 1을 참고합니다> - 가장 긴 가로 길이와 세로 길이가 각각 80, 70이기 때문에 80(가로) x 70(세로) 크기의 지갑을 만들면 모든 명함들을 수납할 수 있습니다. 하지만 2번 명함을 가로로 눕혀 수납한다면 80(가로) x 50(세로) 크기의 지갑으로 모든 명함들을 수납할 수 있습니다. 이때의 지갑 크기는 4000(=80 x 50)입니다.
- 모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 sizes가 매개변수로 주어집니다. 모든 명함을 수납할 수 있는 가장 작은 지갑을 만들 때, 지갑의 크기를 return 하도록 solution 함수를 완성해 주세요.
💡 제한사항
- sizes의 길이는 1 이상 10,000 이하입니다. - sizes의 원소는 [w, h] 형식입니다. - w는 명함의 가로 길이를 나타냅니다. - h는 명함의 세로 길이를 나타냅니다. - w와 h는 1 이상 1,000 이하인 자연수입니다.
💡 해당 문제의 요점은 ‘브루트 포스’ 알고리즘을 통해 ‘카드의 사이즈를 구하기 위해서 모든 경우의 수를 다 확인’하여서 결과를 찾는다는 점입니다.
[STEP1] 2차원 배열을 1차원 배열로 분해하여 순회합니다(* 카드의 모든 경우의 수를 순회합니다)
[STEP2] 카드의 가로와 세로의 길이 중 ‘최대값’을 구하고 이전 카드의 너비와 비교하여 ‘최대값’을 구합니다.
[STEP3] 카드의 가로와 세로의 길이 중 ‘최소값’을 구하고 이전 카드의 높이와 비교하여 ‘최대값’을 구합니다.
[STEP4] 최종적으로 계산된 너비와 높이값을 구하여 최종 카드 사이즈를 구한다.
/**
* [완전탐색-1 : 브루트 포스] 13. 최소 직사각형
* 조건에 만족하는 모든 경우를 탐색하여 원하는 결과를 얻는 브루트 포스를 이용한 문제
*
* @return ResponseEntity
* @link ...
* @since 2023.07.23
*/
@GetMapping("/exhausSearch1")
public ResponseEntity<apiresponse> question13() {
int answer = 0;
int[][] size = {{60, 50}, {30, 70}, {60, 30}, {80, 40}};
int width = 0; // 총 계산된 카드의 너비
int height = 0; // 총 계싼된 카드의 높이
// [STEP1] 2차원 배열을 1차원 배열로 순회합니다. (* 카드의 모든 경우를 순회합니다.)
for (int[] card : size) {
int cardItemWidth = card[0]; // n번 명함의 가로 길이
int cardItemHeight = card[1]; // n번 명함의 세로 길이
// [STEP2] 카드의 기로와 세로의 길이 중 최대 값과 이전 카드 사이즈를 비교하여 최종 너비값을 구합니다.
width = Math.max(width, Math.max(cardItemWidth, cardItemHeight));
// [STEP3] 카드의 가로와 세로의 길이 총 최소 값과 이전에 카드 사이즈를 비교하여 최종 높이값을 구합니다.
height = Math.max(height, Math.min(cardItemWidth, cardItemHeight));
}
// [STEP4] 최종적으로 계산된 너비와 높이 값을 곱하여 결과값을 구합니다.
answer = width * height;
ApiResponse ar = ApiResponse
.builder()
.result(answer)
.resultCode(SUCCESS_CODE)
.resultMsg(SUCCESS_MSG).build();
return new ResponseEntity<>(ar, HttpStatus.OK);
}
</apiresponse
2. 문제 - 부르트 포스 : 모의고사
💡 문제 설명
- 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.
💡 해당 문제의 요점은 ‘브루트 포스’ 알고리즘을 통해 ‘수포자의 패턴’을 통해 결과를 얻기 위해 모든 경우의 수를 다 확인’하여서 결과를 찾는다는 점입니다.
[STEP1] 수포자들의 문제를 찍는 패턴 정의합니다.
[STEP2] 문제 배열을 순회하면서 각각의 값을 Counting 합니다. (* 모든 경우의 수를 순회합니다)
[STEP3] 구성한 리스트의 최대값을 구합니다.
[STEP4] 최대값인 사용자를 구합니다.
[STEP5] 최종 배열로 구성합니다.(List to Array[])
/**
* 14. [완전탐색-2 : 브루트 포스] 14. 모의고사
*
* @return ResponseEntity
* @link ...
* @since 2023.07.23
*/
@GetMapping("/exhausSearch2")
public ResponseEntity<apiresponse> question14() {
// int[] answers = new int[]{1, 3, 2, 4, 2};
int[] answers = new int[]{1, 2, 3, 4, 5};
List personScoreList = Arrays.asList(0, 0, 0);
// [STEP1] 수포자들의 문제를 찍는 패턴 정의
int[] person1Pattern = new int[]{1, 2, 3, 4, 5};
int[] person2Pattern = new int[]{2, 1, 2, 3, 2, 4, 2, 5};
int[] person3Pattern = new int[]{3, 3, 1, 1, 2, 2, 4, 4, 5, 5};
// [STEP2] 문제 배열을 순회하면서 각각의 값을 Counting 합니다. (* 모든 경우의 수를 순회합니다)
for (int i = 0; i < answers.length; i++) {
if (answers[i] == person1Pattern[i % 5]) personScoreList.set(0, personScoreList.get(0) + 1);
if (answers[i] == person2Pattern[i % 8]) personScoreList.set(1, personScoreList.get(1) + 1);
if (answers[i] == person3Pattern[i % 10]) personScoreList.set(2, personScoreList.get(2) + 1);
}
// [STEP3] 구성한 리스트의 최대값을 구합니다.
int max = Collections.max(personScoreList);
// [STEP4] 최대값인 사용자를 구합니다.
List maxPersonList = new ArrayList<>();
for (int i = 0; i < personScoreList.size(); i++) {
if (max == personScoreList.get(i)) maxPersonList.add(i + 1);
}
// [STEP5] 최종 배열로 구성합니다.(List to Array[])
int[] answer = maxPersonList.stream().mapToInt(i -> i).toArray();
ApiResponse ar = ApiResponse
.builder()
.result(answer)
.resultCode(SUCCESS_CODE)
.resultMsg(SUCCESS_MSG).build();
return new ResponseEntity<>(ar, HttpStatus.OK);
}
</apiresponse
3. 문제 - 비트 마스크 : [1차] 비밀지도
💡 문제 설명
- 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 "공백"(" ") 또는 "벽"("#") 두 종류로 이루어져 있다. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 "지도 1"과 "지도 2"라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다."지도 1"과 "지도 2"는 각각 정수 배열로 암호화되어 있다. 암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1, 공백 부분을 0으로 부호화했을 때 얻어지는 이진수에 해당하는 값의 배열이다.
<하단의 사진 확인>
네오가 프로도의 비상금을 손에 넣을 수 있도록, 비밀지도의 암호를 해독하는 작업을 도와줄 프로그램을 작성하라.
[문제 설명] 하단의 사진
💡 입력 형식
- 입력으로 지도의 한 변 크기 n과 2개의 정수 배열 arr1, arr2가 들어온다.
1. 1 ≦ n ≦ 16
2. arr1, arr2는 길이 n인 정수 배열로 주어진다.
3. 정수 배열의 각 원소 x를 이진수로 변환했을 때의 길이는 n 이하이다. 즉, 0 ≦ x ≦ 2n - 1을 만족한다.
- Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.
<아래의 사진 참고>
Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다. Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.
💡 제한사항
- 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다. 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.
💡 해당 문제의 요점은 ‘브루트 포스’ 알고리즘을 통해 역순으로 배열을 순회하면서 모든 경우의 수를 다 확인하여 결과를 찾는다는 점입니다.
[STEP1] 갈색 격자와 노란 격자를 합하여 전체의 개수를 구합니다.
[STEP2] 그 합의 제곱근부터 1이 될 때까지 반복 수행합니다. (브루트 포스)
[STEP3] 반복 수행을 하면서 그 중 합의 약수인 경우를 찾습니다.
[STEP4] 약수 중 합에서 가로의 길이를 나누어서 세로(j)의 길이를 계산합니다.
[STEP5] 가로(i)와 세로(j)의 길이를 이용하여 노란색 타일의 개수가 맞는지 확인하고, 맞을 경우에는 해당 크기를 반환합니다.
/**
* 16. [완전탐색 -4 : 브루트 포스] 카펫
*
* @return ResponseEntity
* @link ...
* @since 2023.07.24
*/
@GetMapping("/exhausSearch4")
public ResponseEntity<apiresponse> question16() {
int[] answer = new int[2];
int brown = 8;
int yellow = 1;
// [STEP1] 갈색 격자와 노란 격자를 합하여 전체의 개수를 구합니다.
int sum = brown + yellow;
// [STEP2] 그 합의 제곱근부터 1이 될 때까지 반복 수행합니다. (브루트 포스)
for (int i = (int) Math.sqrt(sum); i >= 1; i--) {
// [STEP3] 그 중 합의 약수인 경우를 찾습니다.
if (sum % i == 0) {
// [STEP4] 약수 중 합에서 가로의 길이를 나누어서 세로의 길이를 계산합니다.
int j = sum / i;
// [STEP5] 가로와 세로의 길이를 이용하여 노란색 타일의 개수가 맞는지 확인하고, 맞을 경우에는 해당 크기를 반환합니다.
if ((i - 2) * (j - 2) == yellow) {
answer = new int[]{j, i};
}
}
}
ApiResponse ar = ApiResponse
.builder()
.result(answer)
.resultCode(SUCCESS_CODE)
.resultMsg(SUCCESS_MSG).build();
return new ResponseEntity<>(ar, HttpStatus.OK);
}
💡 [참고] 좀 더 다양한 알고리즘에 대해 알고 싶으시면 아래의 글을 참고하시면 도움이 됩니다.
