기록을

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

중요한 부분은

1. 수식의 길이를 n이라고 했을 때, 넣을 수 있는 괄호의 최대 개수 찾기

2. 수식을 계산하기

두 가지로 나눌 수 있다.

괄호의 최대 개수는 몇 개의 예시를 통해서 규칙을 찾을 수 있다.

계산을 할 때에는, 계산에 필요한 연산자와 피연산자를 구분해서 벡터에 저장해둔 이후에, 계산을 하게 되면, 연산자의 개수는 항상 피연산자의 개수보다 하나 적다는 것을 이용해서 깔끔하게 계산할 수 있다.

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

백준 16637번 괄호 추가하기라는 문제인데, 이 문제를 풀면서 했던 뻘짓을 기록해두려고 한다.

3+8*2 이런 문자열이 있다고 할 때, 결과값을 내도록 구현하려면 어떻게 해야할까?

그냥 str[0] ~ str끝까지 한 문자 한 문자 확인하려고 생각하는 순간 굉장히 피곤해진다.

324 + 232 이런 경우처럼, 한 자리수가 아닌 숫자가 존재할 수 있기 때문이다. 처음에 이렇게 접근했다가, 결과적으로 아래와 같은 뻘짓을 하게 되었다.

위와 같은 뻘짓을 하지 않으려면, 연산자와 피연산자를 분리해서 벡터(배열)에 저장하고 있으면 된다. 연산하기가 훨씬 수월하다.

이렇게 간단하게 계산할 수 있다.

정상적인 수식이라면, 연산자의 개수가 피연산자의 개수보다 하나 적을 것이므로, 깔끔하게 위와 같은 반복문을 만들어낼 수 있다.

먼저 최대 공약수 gcd는 재귀로도 구현할 수 있고, 아래와 같이 반목문으로 구현할 수도 있다.

어느쪽이 큰 수인지 지정해줘야 한다.

이후에 큰수를 작은수로 나누고, 나눈 수를 다음에 나눠질 수로 정한다. 나머지는 다음에 나눌 수가 된다.

0으로 나눌 수는 없기 때문에 루프를 빠져 나간다고 외워도 좋고, 나머지가 0이 되었다는 것은 약수를 찾았다는 뜻이니까 루프를 빠져 나간다고 기억해도 좋겠다.

( ll은 long long 타입을 의미한다)

int gcd(ll a, ll b) {
    if (a < b) swap(a, b); //a를 큰수로
    while (b != 0) {
        ll r = a % b;
        a = b;
        b = r;
    }
    return a;
}

다음으로, gcd를 활용해서 최소 공배수 lcm을 구하는 과정도 간단하게 구현할 수 있다.

ll lcm(ll a, ll b) {
    return (a * b) / gcd(a, b);
}

최소 공배수의 정의대로, 두 수의 곱을 최대 공약수로 나눠주면 된다.

이를 활용해서, 여러개의 숫자의 최소 공배수를 구하는 과정을 보자.

ll finY = Y[0];
    for (int i = 1; i < Y.size(); i++)
        finY = lcm(finY, Y[i]);

finY에 벡터 Y의 원소들의 최소 공배수가 들어가게 된다. 먼저 벡터 Y의 0번째 값으로 finY를 초기화 한다.

그리고 다음 원소와 lcm을 구해서 저장하고, 또 저장한 lcm과 다음 원소의 lcm을 구하는 과정을 반복해주면 된다.

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

자리수가 추가될 때마다 현재 상태의 수가 소수인지 아닌지를 판별해주면 된다.

가령 7331을 만들기 위해서, 처음에 7을 골라서 확인하고, 73을 확인하고, 733을 확인하고 ... 이런 흐름이다.

처음에 2를 고르고, 다음에 21이 나왔을텐데, 21은 소수가 아니기 때문에 21#$!@#는 더이상 확인할 필요가 없는 것이다.

신경써줄 부분은, 소수 판별 함수에서 1은 바로 소수가 아님을 반환하는 것과, 가장 큰 자리의 수가 0이 되지 않도록 해주는 부분이다.

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

A^B mod m을 연산하는 프로그램을 작성하는 문제이다.

수의 범위가 20억까지 가능하기 때문에 long long 타입을 활용한 것 이외에 재귀를 진행할 때도 아이디어가 하나 필요했다.

B가 홀수냐 짝수냐에 따라서 경우를 나눠줬다.

재귀의 base condition은 B가 0일 때 1을 반환하는 것이 된다.

또한 overflow를 방지하기 위해 계산하는 중간중간에 modular 연산을 수행해줄 필요가 있다.

XYmodM = (XmodM * YmodM) mod M 인 것을 이용하면 되겠다.

지수가 홀수인 경우, 계산 이후에 a를 한 번 더 곱해줘야 하고, 이 과정에서 modular 연산을 한번 더 수행해줘야 한다.

#include<iostream>
using namespace std;
typedef long long ll;

ll POW(ll a, ll b, ll m){
    if(b == 0) return 1;
    ll val = POW(a, b/2, m);
    val = val * val % m;
    
    //b가 짝수, 홀수인 경우 나눠서 처리
    if(b % 2 == 0) return val;
    else
        return (val * a) % m;
    
}

int main(void){
    int a, b, m;
    cin >> a >> b >> m;
    cout << POW(a, b, m);
    return 0;
}