3 - 완전탐색
1. 최소직사각형
https://school.programmers.co.kr/learn/courses/30/lessons/86491?language=cpp
구현
- 직사각형이 주어지고, 커버할 수 있는 최소크기의 지갑을 구현.
- 큰 것끼리 모아두고, 작은 것끼리 모아둔다.
그리고 각각의 가장 최대값을 구하고 곱한다.
문제점
1. 아이디어만 떠오르면 쉽다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<vector<int>> sizes) {
int answer = 0;
vector<int> v_max;
vector<int> v_min;
for(int i=0;i<sizes.size();i++)
{
if(sizes[i][0] > sizes[i][1])
{
v_max.push_back(sizes[i][0]);
v_min.push_back(sizes[i][1]);
}
else
{
v_max.push_back(sizes[i][1]);
v_min.push_back(sizes[i][0]);
}
}
sort(v_max.begin(), v_max.end());
sort(v_min.begin(), v_min.end());
answer = v_max[v_max.size()-1] * v_min[v_min.size()-1];
return answer;
}2. 모의고사 찍기
https://school.programmers.co.kr/learn/courses/30/lessons/42840?language=cpp
구현
- 아무리봐도 허술하게 하드코딩한 것 같다.
- https://minsoftk.tistory.com/58 풀이 참고
문제점
1. vector의 값을 초기화하는 법 (그냥 { } 사용)
#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
vector<int> solution(vector<int> answers) {
vector<int> answer;
vector<int> v1 = {1,2,3,4,5};
vector<int> v2 = {2,1,2,3,2,4,2,5};
vector<int> v3 = {3,3,1,1,2,2,4,4,5,5};
queue<int> q1;
queue<int> q2;
queue<int> q3;
for(int i : v1)
{
q1.push(i);
}
for(int i : v2)
{
q2.push(i);
}
for(int i : v3)
{
q3.push(i);
}
int result1=0, result2=0, result3=0;
for(int i=0; i<answers.size();i++)
{
if(q1.front()==answers[i])
{
result1++;
}
if(q2.front()==answers[i])
{
result2++;
}
if(q3.front()==answers[i])
{
result3++;
}
q1.push(q1.front());
q2.push(q2.front());
q3.push(q3.front());
q1.pop();
q2.pop();
q3.pop();
}
int max_result = max(result3, max(result1, result2));
if(max_result==result1)
{
answer.push_back(1);
}
if(max_result==result2)
{
answer.push_back(2);
}
if(max_result==result3)
{
answer.push_back(3);
}
return answer;
}3. 소수 찾기
https://school.programmers.co.kr/learn/courses/30/lessons/42839?language=cpp
구현
- 71 이런게 입력으로 주어지면, 1 7 17 71 등
해당 각 수의 조합으로 만들 수 있는 모든 수 중에서
소수의 개수를 출력하면 된다.- 문제가 총 3개로 나뉜다.
에라토스테네스의 체 구현 / 수의 조합 DFS로 구현 / 최종 값 출력 구현
문제점
1. 에라토스테네스 구현이 미숙했다.
2. DFS로 어떻게 수를 조합할지 고민했다.
소문제들이 합쳐져서 하나의 문제가 되니 복잡해졌다.
3. int형 set에 결과를 담았는데, stoi를 사용했다.
4. set의 특정 원소에 접근하지 못해서
che라는 에라토스테네스 알고리즘에 최대값 777777777을 넣을 수 밖에 없었다.
어쨌든 최대를 넣어도 돌아가야하는 문제이기 때문에 상관X
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include <set>
using namespace std;
string t_numbers;
char arr[8];
bool visited[8];
set<int> results;
void DFS(int n)
{
if(n>=1 && n<=t_numbers.size())
{
string s;
for(int i=0;i<n;i++)
{
s+=arr[i];
}
results.insert(stoi(s));
}
{
for(int i=0; i<t_numbers.size();i++)
{
if(!visited[i])
{
visited[i] = 1;
arr[n] = t_numbers[i];
DFS(n+1);
visited[i] = 0;
}
}
}
}
vector<bool> che(int n)
{
vector<bool> isPrime(n+1, true);
isPrime[0] = isPrime[1] = false;
for(int i=2; i*i <= n; i++)
{
if(isPrime[i])
{
for(int j= i*i; j<=n;j+=i)
{
isPrime[j] = false;
}
}
}
return isPrime;
}
int solution(string numbers) {
int answer = 0;
t_numbers = numbers;
/*
vector<int> num;
for(int i=0;i<numbers.size();i++)
{
num.push_back(numbers[i]-'0');
}
sort(num.begin(), num.end());
*/
DFS(0);
for(auto i : results)
{
cout << i << " ";
}
vector<bool> sosu = che(777777777);
for(auto i : results)
{
if(sosu[i])
{
answer++;
}
}
return answer;
}4. 카펫
https://school.programmers.co.kr/learn/courses/30/lessons/42842?language=cpp
구현
- 노란색과 갈색으로 구성된 카펫, 각 개수만 주어진다.
- 노란색이 될 수 있는 경우의 수를 나눗셈을 통해서 가로 세로를 구한다.
- 해당 값에 +2를 하면 갈색의 가로 세로가 된다.
단 1줄만 감싸고 있다고 했기 때문.
문제점
1. 다 구해놓고 +2한 값을 push_back하지 않았다.
2. <= yellow의 범위로 나눗셈을 해야만 했다.
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
vector<int> solution(int brown, int yellow) {
vector<int> answer;
for(int i=1;i<=yellow;i++)
{
if(yellow%i==0)
{
int mok = yellow/i;
if((mok+2)*(i+2) - yellow ==brown)
{
answer.push_back(mok+2);
answer.push_back(i+2);
return answer;
}
}
}
return answer;
}5. 피로도
구현
- 던전을 돌 수 있는 필요도의 제한값과, 필요도 소모량이 적혀있다.
- 최대한 많이 도는게 목적..
- 방문하는 것이기 때문에 DFS로 구현하면 된다.
- 방문하고 아니면 돌아와야하니까 백트래킹까지 사용한다.
문제점
1. 피로도를 따로 전역변수처럼 하려고 했는데,
각 DFS 경우에 따른 피로도를 저장할 수 없었다.
따라서 DFS의 매개변수로 만들어 전달했다.
그냥 DFS에 매개변수로 넣는게 제일 속편한 듯..
#include <string>
#include <vector>
#include <iostream>
using namespace std;
bool visited[9];
int answer = -1;
vector<vector<int>> t_dungeons;
void DFS(int n, int HP)
{
if(n>answer)
{
answer = n;
}
{
for(int i=0;i<t_dungeons.size();i++)
{
if(!visited[i])
{
//cout << i;
if(t_dungeons[i][0] <= HP)
{
visited[i] = 1;
DFS(n+1, HP - t_dungeons[i][1]);
visited[i] = 0;
}
}
}
}
}
int solution(int k, vector<vector<int>> dungeons) {
t_dungeons = dungeons;
DFS(0, k);
return answer;
}6. 모음사전
https://school.programmers.co.kr/learn/courses/30/lessons/84512?language=cpp
구현
- DFS를 응용한 정석이라고 볼 수 있는 문제
- 모음으로 문자열을 만들었을 때, 사전순으로 몇번째인지 출력.
문제점
- 없
#include <string>
#include <vector>
#include <set>
#include <iostream>
using namespace std;
set<string> words; // set을 사용하여 중복을 방지
int visited[6]; // int로 방문 여러번 표시 (다만 5개 이상 제한)
char arr[6]; // 입력값 담음
char mo[6] = {'A', 'E', 'I', 'O', 'U'}; // 입력할 단어 편하게 사용하려고.
void DFS(int n)
{
if(n>=1 && n<=5) // 개수가 조건에 맞으면 다 넣는다.
{
string s;
for(int i=0;i<n;i++)
{
s+=arr[i]; // 문자열을 만들고,
}
words.insert(s); //set에 추가
if(n==5) // 5개면 return을 시켜야 함. 아니면 for문을 돈다.
{
return;
}
}
// else문을 지움으로써, 길이 1부터도 자유롭게 추가할 수 있게 됨.
{
for(int i=0;i<5;i++) // 모음 5개
{
if(visited[i]<=4) // 각 모음은 5개까지만 쓸 수 있다.
{
visited[i]++;
arr[n] = mo[i]; // 입력을 넣음
DFS(n+1);
visited[i]--;
}
}
}
}
int solution(string word) {
int answer = 0;
DFS(0);
for(auto a : words) // 돌다가 word를 찾으면 멈춤.
{
answer++;
if(a==word)
{
break;
}
}
return answer;
}4 - 정렬
1. 가장 큰 수
구현
- 벡터의 정렬을 위한 cmp함수 잘보기
- 숫자를 담은 string은 그냥 비교할 수 없다.
사전순으로 10 < 2 이기 때문.- 따라서 a+b > b+a를 통해서
210 > 102
2가 더 큰 값임을 알아낸다.. (굳이 비교함수 없이도 됨 = 아래의 예제를 참고)
이 예제말고 30과 3에서303 > 330은 아니므로,
3이 30보다 더 큰 값이 된다. (이 문제에서 요구하는 값)
#include <string>
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
bool visited[1001];
bool cmp(string a, string b) {
return a + b > b + a;
}
string solution(vector<int> numbers) {
string answer = "";
vector<string> s_numbers;
for(auto i:numbers)
{
s_numbers.push_back(to_string(i));
}
sort(s_numbers.begin(), s_numbers.end(), cmp);
if(s_numbers[0]=="0")
{
return "0";
}
for(auto num : s_numbers)
{
answer += num;
}
// for(auto i : s_numbers)
// {
// cout << i << " ";
// }
return answer;
}
Time Waits for No One