[Algorithm/C++] 완전 탐색 (Brute-force Search): 백준 2309번, 프로그래머스 모의고사 문제 풀이

[완전 탐색 알고리즘]은 무엇일까?

'완전 탐색 알고리즘'은 이름에서 알 수 있듯 답을 찾기 위해 모든 상황을 다 계산하여 답을 찾도록 구현하는 알고리즘으로 시간이 가장 오래 걸리는 방법이지만, 가장 정확한 답을 찾을 수 있다. 완전 탐색 알고리즘을 풀 때, 'for 문'을 사용하면 금방 해결의 실마리를 찾아낼 수 있지만 for문을 얼마나 체계적으로, 효과적으로 짜느냐가 중요한 관건이다. 완전 탐색 알고리즘의 시간 복잡도는 for문이 얼마나 중첩되어 있느냐에 따라서 크게 다른데 for문이 x개 중첩되면 시간 복잡도가 n의 x제곱이 되는 만큼 시간 복잡도가 매우 크다.

 

완전 탐색을 사용해야 하는 두 문제를 리뷰해보면서 해당 알고리즘에 대해 파고들어 보자.

 

 

백준 2309번: 난이도 下

문제 설명: 왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다. 아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다. 아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

Link: https://www.acmicpc.net/problem/2309

#include <iostream>
#include <memory>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	vector<int> v;
	int sum = 0;
    
	//1) vector에 아홉 난쟁이 키 입력 받아 저장
	for (int i = 0; i < 9; i++) {
		int n;
		cin >> n;
		sum += n;
		v.push_back(n);
	}

	//2) 이중 for문으로 가짜 난쟁이 키 찾기
	bool find = true;
	for (int i = 0; i < 9; i++) {
		if (find) { //가짜 난쟁이를 찾기 전일 경우에만 실행
			for (int j = 0; j < 9; j++) {
				if (i != j) {
					if ((sum - (v[i] + v[j])) == 100) {//가짜 난쟁이를 찾았을 경우
						v[i] = 0; v[j] = 0;
						find = false;
						break;
					}
				}
			}
		}
		else break;
	}

	sort(v.begin(), v.end()); //키 오름차순으로 정렬

	for (int i = 0; i < 9; i++) { //키 출력
		if (v[i] != 0) {
			cout << v[i] << endl;
		}
	}

	return 0;
}

이중 for문을 사용해서 입력받은 아홉 난쟁이의 키를 7개씩 조합할 수 있는 모든 경우의 수 36개를 훑는다. 이때, if문을 사용해 처음에 구한 모든 아홉 난쟁이의 키 sum에서 v [i], v [j] 두 난쟁이의 키를 뺀 값이 100과 같으면 두 가짜 난쟁이를 찾은 것으로 간주하고 for문에서 빠져나온다(문제에선 모든 경우를 다 순회해 100이 되는 경우가 두 개 이상일 경우 아무거나 한 경우만 출력하라고 했지만 필자는 하나만 찾으면 탈출하도록 코드를 구성했다).

 

 

 

프로그래머스 완전 탐색
연습 문제 모의고사: 난이도 中 

문제 설명: 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.
1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...
1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

Link: https://programmers.co.kr/learn/courses/30/lessons/42840

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> a = { 1,2,3,4,5 }; //5
vector<int> b = { 2,1,2,3,2,4,2,5 }; //8
vector<int> c = { 3,3,1,1,2,2,4,4,5,5 }; //10

vector<int> solution(vector<int> answers) {
    vector<int> answer;
    int A = 0, B = 0, C = 0; // 각각 1,2,3번 학생의 점수
    int max_score;// 점수 최댓값
    
    for (int i = 0; i < answers.size(); i++) { //1) 1,2,3번 학생 점수 채점
        if (answers[i] == a[i % 5]) A++;
        if (answers[i] == b[i % 8]) B++;
        if (answers[i] == c[i % 10]) C++;
    }

	max_score = max(max(A, B), C); //2) max(a,b) 함수 이용해 점수 최댓값 구하기
    
	//3) 가장 잘 본 학생 배열에 담아 return
    if (max_score == A) answer.push_back(1);
    if (max_score == B) answer.push_back(2);
    if (max_score == C) answer.push_back(3);

    return answer;
}

이 문제는 배울 점이 많았다. 나는 처음에 학생 세명 각각 다른 답안지 규칙에 맞게 for문을 따로 작성해서 3개의 for문으로 난잡하게 코드를 구상했었는데, 여러 가지 코드와 비교해보고 리뷰한 결과 위와 같이 각 학생의 답안지는 배열로 정해두고 하나의 for문에서 if문을 사용해 세 학생의 답을 한 번에 채점하는 것이 훨씬 깔끔하고 보기 좋았다. 이 문제를 풀어보면서 완전 탐색 알고리즘은 단순히 그 이름처럼 무식하게 모두 접근하도록 짜는 것이 아니라 안에 논리와 체계를 꼼꼼히 담아내야 한다는 것을 배웠다. 

 

프로그래머스 문제 코드 참조 레퍼런스: https://velog.io/@yuna_song/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%AA%A8%EC%9D%98%EA%B3%A0%EC%82%AC%EC%99%84%EC%A0%84%ED%83%90%EC%83%89