2023.01.03 (화) 실버1
백준 2일차..
어제는 1일차니까 자신감도 올릴 겸 브론즈 풀어주다가 갑자기 맛을 봤다.,.
정신을 못차렸다 ,, 2학년 이후로 알고리즘에는 손도 안대서 감도 안잡혔다
이게 무슨!! 처음에 아무생각없이 노가다를 뛰려고 했는데 경우의 수 구하고 나니 말이 안된다는걸 깨달았다
알고리즘 분류
브루트포스 알고리즘
== 완전 탐색 알고리즘
- 그냥 가능한 모든 경우의 수를 싹 다 해보고 해를 리턴하는 알고리즘이다.
- 깊이 우선 탐색 (DFS), 너비 우선 탐색 (BFS)
백트래킹
DFS를 하는 도중에 더 이상 탐색할 필요가 없는 노드를 빼고 탐색한다
경우의 수는 일반적으로 DFS를 쓰면 답이 나온단다.DFS vs 백트래킹
DFS : 모든 경우의 수를 찾아야 할 때
백트래킹 : 필요한 경우의 수만 찾을 때그냥 무작정 DFS를 갖다박으면 낭비가 된다.
둘 다 먼소리야..했다.... 반성중 ㅠㅠ
코드
#include <iostream>
#include <vector>
using namespace std;
int N;
int arr[12];
int operators[4];
int min_output = 1000000000;
int max_output = -1000000000;
void GetResult(int num, int idx)
{
if (idx == N - 1)
{
if (num >= max_output) {
max_output = num;
}
if (num <= min_output) {
min_output = num;
}
}
for (int i = 0; i < 4; ++i) {
if (operators[i] > 0) {
operators[i]--;
switch (i) {
case 0:
GetResult(num + arr[idx + 1], idx + 1);
break;
case 1:
GetResult(num - arr[idx + 1], idx + 1);
break;
case 2:
GetResult(num * arr[idx + 1], idx + 1);
break;
case 3:
GetResult(num / arr[idx+1], idx + 1);
break;
}
operators[i]++;
}
}
}
int main()
{
cin >> N;
for (int i = 0; i < N; ++i) {
cin >> arr[i];
}
for (int i = 0; i < 4; ++i) {
cin >> operators[i];
}
GetResult(arr[0], 0);
cout << max_output << endl;
cout << min_output << endl;
}풀이
이 문제에서는 연산자 operators가 들어갈 N-1개의 공간들이 깊이값이 된다.
재귀함수 GetResult를 통해 깊이 우선 탐색 (DFS)를 진행한다.
제일 쉽고 명확한 예시3번으로 예를 들면,
요런 상황이다.
빨간색 네모들에 operators가 들어가야 한다.
중복인 경우는 셀 필요가 없으니 백트래킹해야 한다!
구해야 할 경우의 수는 저 빨간 네모들에 입력받은 연산자들(operators 배열)이 어떤 순서로 들어갈지?
일단 예시에서 +가 2개다.
같은 연산자가 중복되는 경우가 있으니 operators 배열의 각 원소들의 크기가 0보다 크면
들어갈 수 있는 걸로 치고, 한 번 그 연산자를 이번 경우의 수에 썼으면 --하는 방식으로 해보자.
순서대로 1 부터 차례대로 연산을 해줄거다.
문제에서 연산자 우선순위 관계없이 앞에서부터 해준다고 했으므로 문제가 조금 더 쉬워진 것 같당
그래서 재귀를 돌리기 시작한다.
1 에 대한 연산자는 첫 번째 빨간색 네모.
걔가 들어갈 수 있는 경우의 수는 일단 4개. 근데 이제 operators[i]가 0보다 클 때만.
그래서 일단 for문 돌려준다. 아니면 걍 넘어가면 되니까!
그래서 첫 빨간네모에 들어갈 연산자가 정해지면 재귀함수를 호출한다.
연산자에 따라 각 연산을 진행한 다음에.
그래서 +갈 수 있으니까 1 + 2 (두 번째 인덱스)
한 다음에 그 결과값인 3에 대해서 인덱스 1과 하는거다.
가다보면 끝까지 가겠지? 그러면 결과가 나온다. (num)
그래서 결과 나올때마다 최대, 최소 비교해준다.
그렇게 계속 돌림.
for문 내에서 재귀 막,,,돌려
그래서 함수가 끝나기 시작하면 언젠가 다시 원문으로 돌아오잖아
그래서 위에서 --하고 밑에서 ++한거임
깊이 기준으로 계속 돌려줘야 하니까.
그렇게 하지 않으면 제대로 돌아가지가 않는다.
나는 이 부분에 대한 이해가 어려워서 엄청 애먹었다... 바보라서그랭
회고
DFS에 대한 이해가 많이 부족했고,
일단 문제를 보고 알고리즘을 떠올리는게 아예 안된다.
아예 감이 안잡혀서 서치해버렸다.
근데 진짜 아예.. 전혀 생각도 못했다.
그래서 차라리 이렇게 공부하는 것도 괜찮은 것 같다.
2일차니까.. 이렇게 하루 하루 알고리즘 공부해나가면 되겠지..?
수민아힘내..
