[스터디] - 2회차

초반 개념 관련 내용에서는 따로 정리하기 보다, 기존 정리된 글들이 더욱 좋다고 판단하여 참고하기 좋은 사이트만 첨부하였다.

 

복잡도(Complexity): 시간 복잡도와 공간 복잡도, 그리고 빅오(Big-O) 표기법

복잡도(Complexity): 시간 복잡도와 공간 복잡도, 그리고 빅오(Big-O) 표기법

누적합

누적 합

누적 합

• 누적합
  • 배열이 정적이라는 가정하에서만 사용하도록 주의하자.
  • 배열이 정적이므로 구간의 합 또한 정적이다.
    • 따라서, 차례대로 누적된 합을 구하고 이를 이용해서 구간의 합을 구할 수 있다.
• 다음과 같은 형태를 가진다.

...
prefixSum[1] // 1
prefixSum[2] // (1 + 2)
prefixSum[3] // (1 + 2) + 3
...

// Q. 2~4번째 숫자의 합은?
cout << prefixSum[4] - prefixSum[1] << "\n";

• 코드는 아래와 같다.

// a[ ]가 입력된 숫자라고 가정한다면
for (int i=1; i<=n; i++) {
    prefixSum[i] = prefixSum[i-1] + a[i];
}

• 시작 인덱스를 1부터 하자.
  • 인덱스를 [i - 1]부터 참조하도록 하기 때문에, 1부터 시작하는 것이 마음이 편할 거다.

---

1주차 문제

• 일곱 난쟁이 - BRONZE1

2309번: 일곱 난쟁이

2309번: 일곱 난쟁이

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> v;
int a;

int main() {
    for(int i=0;i<9;i++){
        cin >> a;
        v.push_back(a);
    }

    sort(v.begin(), v.end());

    do {
        int sum = 0;
        for(int i=0; i<7; i++) {
            sum += v[i];
        }
        if(sum == 100) {
            for(int j=0;j<7;j++){
                cout << v[j] << "\n";
            }
            return 0;
        }
    }while(next_permutation(v.begin(), v.end()));
    return 0;
}

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> v;
int a;

void printV() {
    int sum = 0;
    for(int i=0;i<7;i++) {
        sum += v[i];
    }
    if(sum == 100) {
        for(int i=0;i<7;i++){
            cout << v[i] << "\n";
        }
        exit(0);
    }
    return;
}
void makePermutation(int n, int r, int depth) {
    if(r==depth) {
        printV();
        return;
    }

    for(int i=depth; i<n;i++){
        swap(v[i], v[depth]);
        makePermutation(n, r, depth + 1);
        swap(v[i], v[depth]);
    }

    return;
}

int main() {
    for(int i=0;i<9;i++) {
        cin >> a;
        v.push_back(a);
    }

    sort(v.begin(), v.end());

    makePermutation(9, 7, 0);

    return 0;
}

 

• 알파벳 개수 - BRONZE4

10808번: 알파벳 개수

10808번: 알파벳 개수

#include <iostream>
#include <algorithm>

using namespace std;

int arr[26];
string s;

int main() {
    cin >> s;
    for(int i=0;i<s.length();i++){
        arr[s[i] - 'a'] += 1;
    }
    for(int i:arr) {
        cout << i << " ";
    }
    cout << "\n";
    return 0;
}

 

• 트럭 주차 - BRONZE2

2979번: 트럭 주차

2979번: 트럭 주차

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int a, b, c;
int res;
int start, ed;
int arr[101];

int main() {
    cin >> a >> b >> c;
    for(int i=0;i<3;i++){
        cin >> start >> ed;
        for(int j=start;j<ed;j++){
            arr[j]++;
        }
    }
    for(int i=1;i<=100;i++){
        if(arr[i]==1){
            res += a;
        } else if(arr[i]==2){
            res += b * 2;
        } else if(arr[i]==3){
            res += c * 3;
        }
    }
    cout << res << "\n";
    return 0;
}

 

• 팰린드롬인지 확인하기 - BRONZE3

10988번: 팰린드롬인지 확인하기

10988번: 팰린드롬인지 확인하기

#include <iostream>
#include <algorithm>

using namespace std;

string s;

int main() {
    cin >> s;
    for(int i=0;i<s.length()/2;i++){
        if(s[i] != s[s.length()-1-i]){
            cout << "0" << "\n";
            return 0;
        }
    }
    cout << "1" << "\n";
    return 0;
}

 

• 농구 경기 - BRONZE2

1159번: 농구 경기

1159번: 농구 경기

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int len, flag;
int cnt[26];
vector<string> v;
string s;

int main() {
    cin >> len;
    for(int i=0;i<len;i++) {
        cin >> s;
        v.push_back(s);
    }
    sort(v.begin(), v.end());
    for(int i=0;i<len;i++){
        cnt[v[i][0]-'a']++;
    }
    for(int i=0;i<26;i++){
        if(cnt[i] >= 5){
            cout << char(i + 'a');
            flag++;
        }
    }
    if(flag==0){
        cout << "PREDAJA" << "\n";
    }
    return 0;
}

 

• ROT13 - BRONZE1

11655번: ROT13

11655번: ROT13

#include <iostream>
#include <string.h>
#include <algorithm>
#include <vector>

using namespace std;

string s;

int main() {
    getline(cin, s);
    for(int i=0;i<s.length();i++){
        if('a'<=s[i]&&s[i]<='z'){
            if(s[i]+13 > 'z'){
                s[i] -= 13;
            } else {
                s[i] += 13;
            }
        }
        else if('A'<=s[i]&&'Z'>=s[i]) {
            if(s[i]+13 > 'Z'){
                s[i] -= 13;
            } else {
                s[i] += 13;
            }
        }
    }
    cout << s << "\n";
    return 0;
}

 

• 한국이 그리울 땐 서버에 접속하지 - SILVER3
  • 두 번 틀림;
  • 마지막에 cnt, s의 문자열길이 비교를 전혀 고려안했었다.
    • 아래는 내 풀이

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

9996번: 한국이 그리울 땐 서버에 접속하지

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n;
string s, cnt;

vector<string> split(string input, string delimiter) {
    vector<string> ret;

    long long pos = 0;
    string token = "";

    while((pos=input.find(delimiter)) != string::npos) {
        token = input.substr(0, pos);
        ret.push_back(token);
        input.erase(0, pos + delimiter.length());
    }
    ret.push_back(input);
    return ret;
}
int main() {
    cin >> n;
    cin >> s;
    vector<string> a = split(s, "*");
    for(int i=0;i<n;i++){
        int flag = 0;
        long long pos = 0;
        string token = "";
        cin >> cnt;
        if(cnt.length() < a[0].length() + a[1].length()){
            flag = 1;
        }
        if((pos=cnt.find(a[0])) != 0) {
            flag = 1;
        }
        for(int j=0;j<a[1].length();j++){
            if(cnt[cnt.length()-a[1].length()+j] != a[1][j]) {
                flag = 1;
            }
        }
        //cout << "\n";
        //cout << cnt.find(a[0]) << " " << cnt.find(a[1]) << "\n";
        if(flag==1){
            cout << "NE" << "\n";
        } else {
            cout << "DA" << "\n";
        }
    }
    cout << "\n";
    return 0;
}

 

• 수열 - SILVER3

2559번: 수열

2559번: 수열

#include <iostream>
#include <string.h>
#include <algorithm>
#include <vector>

using namespace std;

int N, M, res = -2147483647;
vector<int> v;
int arr[100001];
int cnt[100001];

int main() {
    cin >> N >> M;
    int sum = 0;
    for(int i=0;i<M;i++){
        cin >> cnt[i];
        sum += cnt[i];
    }
    arr[0] = sum;
    for(int i=M;i<=N-1;i++) {
        cin >> cnt[i];
        arr[i-M+1] = arr[i-M] + cnt[i] - cnt[i-M];
    }
    for(int i=0;i<=N-M;i++){
        if(res < arr[i]) {
            res = arr[i];
        }
        //cout << arr[i] << " ";
    }
    //cout << "\n";
    cout << res << "\n";
    return 0;
}

 

• 나는야 포켓몬 마스터 이다솜 - SILVER4
  • 시간복잡도에 유의하자.

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

1620번: 나는야 포켓몬 마스터 이다솜

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

string arr[100001];
map<string, int> m;
string s, cnt;
int N, M;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for(int i = 0; i < N; i++) {
        cin >> cnt;
        arr[i] = cnt;
        m.insert(make_pair(cnt, i)); 
    }

    for(int i=0;i<M;i++){
        cin >> s;
        if(s[0]>='0'&&s[0]<='9'){
            int num = stoi(s);
            cout << arr[num-1] << "\n";
        } else {
            cout << m[s] + 1 << "\n";
        }
    }
    return 0;
}

 

• 패션왕 신해빈 - SILVER3

9375번: 패션왕 신해빈

9375번: 패션왕 신해빈

#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <vector>

using namespace std;

int n, cnt, res;
string a, b;

int main() {
    cin >> n;
    for(int i=0;i<n;i++){
        vector<pair<int, string> > v;
        res = 1;

        cin >> cnt;
        for(int j=0;j<cnt;j++){
            int flag = 0;
            cin >> a >> b;
            for(int k=0;k<v.size();k++){
                if(v[k].second == b) {
                    flag = 1;
                    v[k].first++;
                }
            }
            if(flag==0){
                v.push_back(make_pair(1, b));
            }
        }
        for(int j=0;j<v.size();j++){
            res *= (v[j].first + 1);
        }
        res--;
        cout << res << "\n";
    }
    return 0;
}

 

• 팰린드롬 만들기 - SILVER3
  • 시간초과가 난 코드도 같이 첨부했다.

1213번: 팰린드롬 만들기

1213번: 팰린드롬 만들기

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

string s, res;
char idx;
int arr[26];
int flag;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> s;
    for(char a : s) {
        arr[a-'A']++;
    }
    for(int i=25;i>=0;i--){
        if(arr[i]%2==1){
            flag++; idx = char(i+'A');  
            arr[i]--;
            if(flag==2){
                cout << "I'm Sorry Hansoo" <<"\n";
                return 0;
            }
        }
        for(int j=0;j<arr[i];j+=2){
            res = char(i+'A') + res + char(i + 'A');
        }
    }
    if(flag==1){
        res.insert(res.begin()+res.length()/2, idx);
    } 
    cout << res << "\n";
    return 0;
}
// int main() {
//     ios::sync_with_stdio(false);
//     cin.tie(0);
//     cout.tie(0);
//     cin >> s;
//     sort(s.begin(), s.end());
//     do {
//         int flag = 0;
//         for(int i = 0;i<s.length()/2;i++){
//             if(s[i] != s[s.length()-1-i]){
//                 flag = 1;
//                 break;
//             }
//         }
//         if(flag == 0){
//             for(char a:s) cout << a;
//             cout << "\n";
//             return 0;
//         }
//     }while(next_permutation(s.begin(), s.end()));
//     cout << "I'm Sorry Hansoo" << "\n";
//     return 0;
// }

 

• 주몽 - SILVER4

1940번: 주몽

1940번: 주몽

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N, M, cnt, res;
vector<int> v;

int main() {
    cin >> N;
    cin >> M;
    for(int i=0;i<N;i++){
        cin >> cnt;
        v.push_back(cnt);
    }
    sort(v.begin(), v.end());
    int left = 0, right = v.size() - 1;
    while(left < right) {
        if(v[left] + v[right] == M) {
            res++;
            left++;
            right--;
        } else if(v[left] + v[right] < M) {
            left++;
        } else if(v[left] + v[right] > M) {
            right--;
        }
    }    
    cout << res << "\n";
    return 0;
}

 

• 좋은 단어 - SILVER4

3986번: 좋은 단어

3986번: 좋은 단어

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

string s;
int N, res;

int main() {
    cin >> N;
    for(int i=0;i<N;i++){
        stack<char> cnt;
        stack<char> fd;
        cin >> s;
        for(int j=s.length()-1;j>=0;j--){
            cnt.push(s[j]);
        }
        fd.push(cnt.top());
        cnt.pop();
        while(!cnt.empty()) {
            if(fd.empty()){
                fd.push(cnt.top());
                cnt.pop();
            }
            else if(cnt.top() == fd.top()) {
                fd.pop();
                cnt.pop();
            } else if(cnt.top() != fd.top()){
                fd.push(cnt.top());
                cnt.pop();
            }
        }
        if(fd.empty()){
            res++;
        }
    }
    cout << res << "\n";
    return 0;
}

 

• 곱셈 - SILVER1
  • 모듈러 연산 : (a * b) % c = ((a%c)*(b%c))%c
  • 제곱 공식 : a^(n+m) = a^n * a^m

1629번: 곱셈

1629번: 곱셈

#define ll long long 
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

ll a, b, c, res;

ll makeRes(ll a, ll b, ll c) {
    // 종료 조건
    if(b == 1) {
        return (a % c);
    }
    ll cur = makeRes(a, b/2, c);
    if(b % 2 == 0) {
        res = cur * cur % c;
    } else {
        res = cur * cur % c * a % c;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> a >> b >> c;
    makeRes(a, b, c);
    if(b==1) {
        res = a % c;
    }
    cout << res << "\n";
    return 0;
}

 

• 1 - SILVER3
  • x % n = (x % n) % n

4375번: 1

4375번: 1

#define ll long long 
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

ll cnt;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    while(cin >> cnt) {
        ll comp = 1;
        ll len = 1;
        while(1) {
            ll check = comp % cnt;
            if(check == 0) {
                cout << len << "\n";
                break;
            } else {
                len++;
                comp = comp * 10 + 1;
                comp = (comp % cnt) % cnt;
            }
        }
    }
    return 0;
}