Brute Force Algorithm
순열
2529번: 부등호
: 부등호가 이미 나열되어 있고, 수를 끼워넣는 문제. 최대값과 최소값을 구하는 것이므로, 만약 3자리라면 가장 큰 수는 987에서, 가장 작은 수는 012에서 나올 것이다. 이를 위해 small벡터와 big벡터를 만들었음.
1339번: 단어 수학
: N개의 단어를 수로 바꾼 다음에, 합의 최대값을 구하는 문제. 서로 다른 알파벳이 M개라면, 큰 숫자 M개만 넣어서 조사해보면 된다.
14888번: 연산자 끼워넣기
: 역시 순열을 이용하여 결과값들을 result에 저장하고, minmax_element를 사용하여 최대값, 최소값을 찾아내는 문제이다.
14889번: 스타트와 링크
: 전체 그림이 그려졌던 문제이긴 했지만, 런타임 에러도 났고, 에러를 고친 이후에도 오답이었다.
런타임 에러의 원인은,
- 이차원 벡터를 잘못된 형태로 선언했기 때문이다.
- 일반적인 vector는 다음과 같이 선언한다.
vector <int>v; - 2차원 vector의 선언은 다음과 같이 선언한다.
vector <vector<int>> arr;
vector<vector<int>> a(n, vector<int>(n)); 에러를 고친 이후에도 오답이 나온 이유는,
- cout << res << '\n' 이라고 했어야 하는데 '/n'이라고 입력했기 때문이다.
새롭게 알게된 점은,
- endl과 '\n'의 차이: endl 함수는 개행만 해주는 것이 아니라 내부 버퍼를 비워주는 역할도 함께하기 때문에 매우 느리지만, '\n'은 그렇지 않다는 점에서 시간을 줄일 수 있다.
- vector는 별도의 값을 입력하지 않으면 0으로 초기화된다. 그래서 크기가 n인 벡터의 반은 1로 채웠을 때, 그 뒤의 반은 전부 0으로 초기화되었다.
재귀
6603번: 로또
: 어떻게 구현해야 할지 감이 잘 안 와서 코드를 먼저 보았다. 코드를 보아도 이해가 되지 않는 점이 있었다.
index번째를 선택하든 선택하지 않든 아래의 코드는 실행이 된다. 선택하지 않은 경우에도 아래의 코드가 실행이 되면 안될 것 같은데...
lotto.push_back(a[index]);
solve(a, index + 1, cnt + 1); 1182번을 이해하고 나니, 이 부분도 이해가 된다. index를 선택하는 경우와 선택하지 않는 경우를 모두 호출함으로써, 모든 경우의 수에 대해 확인이 가능해진다!
1182번: 부분수열의 합
: 이번에도 코드를 먼저 보았다.
아래는 부분수열의 개수를 count하는 go함수이다.
void go(int i, int sum){
if(i == n){
if(sum == m){
ans += 1;
}
return;
}
go(i + 1, sum + a[i]);
go(i + 1, sum);
}처음에는 잘 이해가 가지 않았지만, 결국 sum이 m이 되지 않으면 ans는 증가하지 않는 것이고, 선택하는 경우와 선택하지 않는 경우를 매번 호출했기 때문에 모든 경우의 수를 확인하는 것이 가능하다는 것을 알게 되었다.
주의할 점은, 모든 인덱스를 선택하지는 않는 것도 부분수열에 포함되기 때문에 이 때의 sum은 0이 된다. 따라서 입력된 s가 0일 때는 전체 count 개수에서, 모든 인덱스를 선택하지 않은 부분수열의 경우를 하나 빼주어야 한다.
14225번: 부분수열의 합
: 이번에도 마찬가지로 모든 부분수열을 다 구해야 한다.
따라서 아래의 코드처럼 인덱스를 선택하는 경우와 선택하지 않는 경우, 총 두 번 호출을 해야한다.
go(i + 1, sum + a[i]);
go(i + 1, sum); 14888번: 연산자 끼워넣기
: 재귀함수를 사용해서 푸는 것을 알고 있었기 때문에, 나 나름대로 풀어보았지만 결과는 틀림😂 최소값, 최대값을 구하는 과정에서 정답 코드에서는 vector를 사용했다. 그러니까 연산 결과가 나올때마다 vector에 집어 넣고, 마지막에 최소/최대를 뽑아내는 것이었다.
최소, 최대 값을 리턴해야하므로 calc함수는 아래와 같이 생겼다.
pair<int, int> calc(vector<int>) &a, int index, int cur, int plus, int minus, int mul, int div){
vector<pair<int, int>> res;
...
auto ans = res[0];
for(auto p: res){
if(ans.first < p.first){
ans.first = p.first;
}
if(ans.second > p.second){
ans.second = p.second;
}
return ans;
}최대, 최소값을 리턴하는 main함수는 아래와 같이 생겼다.
...
auto p = calc(a, 1, a[0], plus, minus, mul, div);
cout << p.first << '\n';
cout << p.second << '\n';
...새롭게 알게된 점,
- auto 키워드는 선언된 변수의 초기화 식을 사용하여 해당 형식을 추론하도록 컴파일러에 지시한다. 즉, auto 키워드를 사용하면 초깃값의 형식에 맞춰 선언하는 인스턴스(변수)의 형식이 '자동'으로 결정된다. 이것을 타입 추론(type inference)이라고 한다.
- Pair 클래스란, 두 객체를 하나의 객체로 취급할 수 있게 묶어주는 클래스, 데이터 '쌍"을 표현할 때 사용!
- pair <type1, type2> p: 사용할 데이터 타입 1, 2를 넣고 그 타입의 pair 클래스인 p를 만든다.
- p.first는 p의 첫번째 인자를 반환해줌
- p.second는 p의 두번째 인자를 반환해줌
- make_pair(변수1, 변수2)는 변수1과 변수2가 들어간 pair를 만들어줌
15658번: 연산자 끼워넣기(2)
: 14888번(연산자 끼워넣기) 문제와의 차이점은, N개의 수로 이루어진 수열과 N-1개 이상의 연산자가 있다는 것인데, 그렇다하더라도 이 문제는 14888번의 코드를 통해 해결할 수 있다. 왜냐하면 어차피 index가 n이 되면 함수는 종료될 것이기 때문에 별도의 코드를 추가하지 않아도 된다.
