알고리즘매일매일

https://www.acmicpc.net/problem/14888

주어진 N개의 숫자의 위치는 변하지 않고 숫자 사이의 연산자의 위치만 바꿔서 계산 결과의 최솟값과 최댓값을 출력하는 문제이다.

solve함수에서 index번째에서 사용할 수 있는 연산자를 사용하는 모든 경우를 구해준다.

연산자를 선택할 때마다 해당 연산자를 사용해서 계산한 값을 넘겨준다.

사용한 연산자는 처음 입력받은 사용할 수 있는 개수에서 -1을 해주고 탐색에서 돌아온 경우 다시 +1을 해준다.

이 부분을 안 해줘서 계속 최솟값과 최댓값이 같은 값으로 나왔었다...

N-1 개의 모든 연산자를 결정해준 경우 최종 계산된 값을 ans 벡터에 추가해준다.

마지막으로 ans 벡터를 정렬해주면 맨 앞에 위치한 값이 최솟값이고 맨 마지막에 위치한 값이 최댓값이 된다.

https://www.acmicpc.net/problem/6603

K개 중 6개를 고르는 문제이다. 고르는 개수가 정해져 있기 때문에 넥퍼뮤를 사용해도 좋지만 조합을 이용해서 구했다.

먼저 k개만큼 배열에 입력받고, 이 배열에서 6개를 고르는 모든 경우를 구해준다.

숫자를 고를때마다 lotto 벡터에 넣어주고 6개의 숫자를 고른 경우 lotto 벡터에 있는 값들을 모두 출력해주고 return

k개의 숫자를 사용할지 안 할지 모두 정한 경우(index 가 k를 넘어간 경우)에도 더 이상 고를 숫자가 없으므로 return 해준다.

https://www.acmicpc.net/problem/10971

앞에서 next_permutation을 사용해서 풀었는데 dfs를 사용해서도 풀어봤다.

개인적으로 아직 넥퍼뮤가 익숙하지 않아서 dfs로 푸는 게 더 풀기 쉬웠다.

dfs를 사용할때는 방문 표시를 잘해주면 된다.

현재 도시를 방문하는 경우 check배열을 true값으로 바꿔주고 현재 도시를 선택하는 경우를 모두 해준 경우(탐색에서 돌아온 경우)

방문 표시를 지워준다(false 값으로 바꿔준다)

자세한 설명은 아래 코드를 참고!

https://www.acmicpc.net/problem/10971

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP)라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나라고 문제 설명에 나와있다.

실제로 학교 알고리즘 수업에서도 배운 기억이 있다.

이 문제에서는 n의 범위가 (2 ≤ N ≤ 10) 이므로 다음 순열을 이용해서 모든 경로를 구해볼 수 있다.

모든 경로에서의 비용을 계산해서 최솟값을 구해준다.

다음 순열은 d 벡터를 만들어서 사용한다.

d벡터에는 n만큼의 수가 들어있다. 예를 들어, n 이 4이면 d에는 0, 1, 2, 3의 값이 들어 있고 각각은 도시를 의미한다.

이 d 벡터의 모든 순열을 구해줘서 모든 경로를 구할 수 있다.

즉, d 벡터의 값이 도시의 번호와 마찬가지이므로 d벡터의 값을 w배열의 index로 사용하면 된다.

https://www.acmicpc.net/problem/10974

N의 범위가 (1 ≤ N ≤ 8) 이므로 다음 순열을 구해서 모든 순열을 구할 수 있다.

java에서는 next permutaion함수를 직접 구현해줬어야 했는데

c++은 라이브러리가 있어서 좋다...ㅠㅠ

그냥 next_permutation을 써주면 된다...!!

next_permutation을 사용할 때는 do while로 사용해줘야 한다. 무조건 한 번은 실행되어야 하기 때문.

그리고 넥퍼뮤 돌릴 자료구조는 벡터를 사용한다.

넥퍼뮤 while문이 돌아갈 때마다 현재 배열을 순차적으로 출력해주면 끝!

https://www.acmicpc.net/problem/9095

DP로 푸는 문제이긴 하지만 n이 11보다 작은 양수이기 때문에 완전 탐색으로도 풀어줄 수 있다.

방법의 수를 구하는 문제이므로, 1, 2, 3을 더한 경우를 모두 구해서 더한 값이 n이 될 때마다 ans 값을 증가시키고 return

n값을 넘어가버려도 return 해준다.

https://www.acmicpc.net/problem/6588

문제에서 n의 범위는 (6 ≤ n ≤ 1000000)이다.

골드바흐의 추측은 10의 18 제곱까지는 증명되었다고 하므로

두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에 "Goldbach's conjecture is wrong."을 출력하라고 문제에 나와있지만

안 해줘도 될 것 같다.

소수는 에라토스테네스의 체를 이용해서 n의 범위만큼 미리 구해서 배열에 저장한다.

n이 두 소수 p와 q로 이루어져 있다고 했을 때,

p + q = n

n - p = q

이므로 n에서 소수를 뺀 값이 소수이면 답을 바로 출력한다.

참고로 c++에서

ios_base::sync_with_stdio(false);

cin.tie(nullptr);

를 써주면 입출력 속도를 높일 수 있다고 한다.

대신에 printf, scnaf 등은 사용하면 안 된다.

#include <iostream>
using namespace std;
const int MAX = 1000000;
int prime[MAX];
int cnt;
bool check[MAX+1];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //소수를 구해준다.
    for(int i=2; i*i<=MAX; i++) {
    	//이미 소수가 아닌걸로 체크되어 있는 경우
        if(check[i] == true) continue;

		//위의 조건에 걸리지 않았다면 소수이므로 소수 배열에 추가
        prime[cnt++] = i;
        
        //현재 소수의 배수들은 소수가 아니므로 체크해준다.
        for(int j=i+i; j<=MAX; j+=i) {
            check[j] = true;
        }

    }

    while(true) {
        int n;
        cin >> n;
        if(n == 0) break;
        for(int i=1; i<cnt; i++) {
            if(check[n-prime[i]] == false) {
                cout << n << " = " << prime[i] << " + " << n-prime[i] <<  "\n";
                break;

            }
        }
    }

    return 0;
}

https://www.acmicpc.net/problem/2609

최대공약수는 유클리드 호제법을 사용한 gcd 함수를 사용한다.

gcd 함수는 아래 코드와 같이 구현하면 된다.

최소공배수는 a와 b를 곱한 값에 최대공약수로 나누어주면 구할 수 있다.

#include &ltiostream&gt
using namespace std;

//최대공약수를 구하는 함수
int gcd(int a, int b) {
    if(b== 0) return a;
    else return gcd(b, a%b);
}

int main() {
    int a, b;
    cin >> a >> b;
    
    int g = gcd(a,b);
    cout << g << '\n' << a*b/g << '\n';
    
    return 0;
}