[알고리즘] 단계적으로 문제 풀기

1. 파리퇴치3

 

SW Expert Academy

 

가. 제출

#include<iostream>
#include<algorithm>

using namespace std;

int n, m;
int a[15][15];
int dy[2][4] = {{1, -1, -1, 1}, {1, 0, -1, 0}};
int dx[2][4] = {{1, 1, -1, -1}, {0, 1, 0, -1}};

int sum(int y, int x){
    int sum[2];
    for(int i = 0; i <2; i++){
         sum[i] = a[y][x];
        for(int j = 1; j<m; j++){
            for(int dir = 0; dir < 4; dir++){
                int ny = y + (dy[i][dir] * j);
                int nx = x + (dx[i][dir] * j);
                bool underflow = (ny < 0) || (nx < 0);
                bool overflow = (ny >= n) || (nx >= n);
                if(underflow || overflow) continue;
                sum[i] += a[ny][nx];
            }
        }
    }
    return max(sum[0], sum[1]);
}

int main(int argc, char** argv)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int test_case;
    int T;

    cin>>T;

    for(test_case = 1; test_case <= T; ++test_case)
    {
        int ret = 0; int input = 0;
        cin >> n >> m;

        for(int i = 0; i<n; i++){
            for(int j = 0; j<n; j++){
                cin >> input;
                a[i][j] = input;
            }
        }

        for(int y = 0;  y<n; y++)
            for(int x = 0; x<n; x++)
                ret = max(ret, sum(y, x));

        cout << "#" << test_case << " " << ret << "\n";
    }
    return 0;
}

중복되는 코드를 최소화하려고 노력해 보았다.

 

푸는데 너무 오래 걸린 듯.

 

단계적으로 풀어내는 방법을 고민해 봐야겠다.

 

---

2. 최빈수 구하기

 

SW Expert Academy

 

가. 문제를 잘못 이해

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

using namespace std;

vector<int> split(string input, string deli){
    vector<int> ret;
    auto pos = 0;
    string token= "";
    while((pos = input.find(deli)) != string::npos){
        token = input.substr(0, pos);
        ret.push_back(atoi(token.c_str()));
        input.erase(0, pos+deli.length());
    }
    ret.push_back(atoi(input.c_str()));
    return ret;
}

int main(int argc, char** argv)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int test_case;
    int T;
    string input;
    int cnt[100];

    cin>>T;

    for(test_case = 1; test_case <= T; ++test_case)
    {
        string bufferflush = "";
        cin >> bufferflush;
        getline(cin, bufferflush);
        getline(cin, input);

        cout << "bufferflush : " << bufferflush << " input : " << input << "\n";

        /*
        vector<int> vec = split(input, " ");
        fill(&cnt[0], &cnt[0] + 100, 0);

        for(int i : vec){
            cnt[i]++;
        }

        cout << "#" << test_case << " " << *max_element(cnt, cnt + 100) << "\n";
        */
    }
    return 0;
}

알고리즘 문제를 너무 오랜만에 풀어서 문제를 잘못 이해했다.

 

입력되는 점수의 개수가 1000개로 고정되어 있다는 것을 놓쳤다.

 

위의 코드는 허튼짓의 결과물이다.

 

---

나. 배열의 크기를 잘못 설정함.

#include<iostream>
#include<algorithm>

using namespace std;

int main(int argc, char** argv)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int test_case;
    int T;

    cin>>T;

    for(test_case = 1; test_case <= T; ++test_case)
    {
        string bufferflush = "";
        int input;
        int ret = 0;
        int cnt[100]; fill(cnt, cnt + 100, 0);

        cin >> bufferflush;
        for(int i = 0; i <1000; i++){
            cin >> input;
            cnt[input]++;
        }

        for(int i = 0; i<100; i++){
            if(cnt[ret] < cnt[i])
                ret = i;
        }

        cout << "#" << test_case << " " << ret << "\n";
    }
    return 0;
}

0점에서 100점까지면 cnt 배열의 크기는 100이 아니라 101이 되어야 한다.

 

---

다. 최빈수가 여러 개일 경우

#include<iostream>
#include<algorithm>

using namespace std;

int main(int argc, char** argv)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int test_case;
    int T;

    cin>>T;

    for(test_case = 1; test_case <= T; ++test_case)
    {
        string bufferflush = "";
        int input;
        int ret = 0;
        int cnt[101]; fill(cnt, cnt + 101, 0);

        cin >> bufferflush;
        for(int i = 0; i <1000; i++){
            cin >> input;
            cnt[input]++;
        }

        for(int i = 0; i<101; i++){
            if(cnt[ret] < cnt[i])
                ret = i;
        }

        cout << "#" << test_case << " " << ret << "\n";
    }
    return 0;
}

문제에서 “동일한 빈도의 점수가 있다면 큰 점수를 출력한다”는 조건을 놓쳤다.

 

---

다. PASS

#include<iostream>
#include<algorithm>

using namespace std;

int main(int argc, char** argv)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int test_case;
    int T;

    cin>>T;

    for(test_case = 1; test_case <= T; ++test_case)
    {
        string bufferflush = "";
        int input;
        int ret = 0;
        int cnt[101]; fill(cnt, cnt + 101, 0);

        cin >> bufferflush;
        for(int i = 0; i <1000; i++){
            cin >> input;
            cnt[input]++;
        }

        for(int i = 0; i<101; i++){
            if(cnt[ret] < cnt[i])
                ret = i;
               else if(cnt[ret] == cnt[i])
                ret = max(ret, i);
        }

        cout << "#" << test_case << " " << ret << "\n";
    }
    return 0;
}

문제를 잘못 읽어서 많이 틀렸다.

 

문제를 잘못 읽은 이유는 입력, 출력, 핵심 로직 3가지를 한 번에 생각하려고 하니 집중력이 크게 떨어진다.

 

앞으로 문제를 풀 때는 입력, 출력, 핵심 로직을 분리해야겠다.

 

 

---

3. 두 개의 숫자열

 

SW Expert Academy

 

문제의 조건을 놓치지 않고 집중력을 높이기 위해서 입력, 출력, 핵심 로직을 분리하기로 했다.

 

main에서 입력을, doit(함수명 짓기 너무 어렵;;)에서 출력을, makeVec에서 핵심 로직을 담당했다.

 

앞으로는 이와 같은 구조 생각하며 문제를 풀 것 같다.

 

---

가. 배열로 풀어보기

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

using namespace std;

int a[20], b[20];
int n, m;

vector<int> makeVec(int big[20], int small[20], int sLen){
    vector<int> ret;
    int gap = abs(n-m);
    for(int i = 0; i <=  gap; i++){
        int sum = 0;
        for(int j = 0; j < sLen; j++){
            sum += small[j] * big[j+i];
        }
        ret.push_back(sum);
    }
    return ret;
}

int doit(){
    vector<int> vec;

    if(n>m)
        vec = makeVec(a, b, m);
    else
        vec = makeVec(b, a, n);

    return *max_element(vec.begin(), vec.end());
}

int main(int argc, char** argv)
{
    int test_case;
    int T;

    cin>>T;

    for(test_case = 1; test_case <= T; ++test_case)
    {
        int ret = 0;
        cin >> n >> m;

        fill(&a[0], &a[0] + 20, 0);
        fill(&b[0], &b[0] + 20, 0);

        for(int i = 0; i<n; i++)
            cin >> a[i];
        for(int i = 0; i<m; i++)
            cin >> b[i];

        ret = doit();

        cout << "#" << test_case << " " << ret << "\n";
    }
    return 0;
}

• return *max_element(vec.begin(), vec.end());
  : vector의 element 중 가장 큰 값의 iterator를 반환한다.
  : 헤더 파일은 <algorithm>이다.
• 지금 보니 makeVec()에서 n, m의 크기를 비교하면 int sLen을 전달하지 않아도 될지도?

 

1) mam_element

std::max_element - cppreference.com

ForwardIt max_element( ForwardIt first, ForwardIt last );
ForwardIt max_element( ForwardIt first, ForwardIt last, Compare comp );

[first, last) 범위의 가장 큰 element를 찾는다.

 

vector, array, list, set, map, stack, queue 등에서 사용할 수 있다.

 

다만 set, map, stack, queue에선 다루는데 주의할 점이 존재하기 때문에 우선 vector, array, list만 사용해 보자.

 

2) min_element

std::min_element - cppreference.com

min_element도 있다.

 

---

나. vector로 풀어보기

 

가끔 배열의 크기와 같이 배열의 정보를 전달하는 것이 생각보다 까다로운 경우가 많았다.

 

또 로컬에 선언된 배열은 stack 메모리에 저장되는데 stack 메모리는 용량이 적어서 용량을 넘어서기도 한다.

 

그동안은 배열과 배열의 크기를 담은 변수를 전역으로 선언해서 해결했었다. (뻣뻣하다?)

 

이번에는 vector로 유연하게? 풀어보았다.

 

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

using namespace std;

const int MAX_SIZE = 20;

vector<int> calculateMaxSum(const vector<int>& larger, const vector<int>& smaller) {
    vector<int> sums;
    int gap = larger.size() - smaller.size();

    for (int i = 0; i <= gap; i++) {
        int sum = 0;
        for (size_t j = 0; j < smaller.size(); j++) {
            sum += smaller[j] * larger[j + i];
        }
        sums.push_back(sum);
    }

    return sums;
}

int findMaxSum(vector<int>& a, vector<int>& b) {
    vector<int> vec;

    if (a.size() > b.size()) 
        vec = calculateMaxSum(a, b);
    else 
        vec = calculateMaxSum(b, a);

    return *max_element(vec.begin(), vec.end());
}

int main() {
    int T;
    cin >> T;

    for (int test_case = 1; test_case <= T; ++test_case) {
        int n, m;
        cin >> n >> m;

        vector<int> a(n), b(m);

        for (int& ai : a) cin >> ai;
        for (int& bi : b) cin >> bi;

        cout << "#" << test_case << " " << findMaxSum(a, b) << "\n";
    }

    return 0;
}

• vector<int> a(n), b(m); : 벡터를 정적으로 할당.

 

1) 장단점

1. 동적 크기 조절: 벡터의 크기는 실행 시간에 조절될 수 있으며, 요소를 추가하거나 제거하는 것이 간단하다.
2. 메모리 관리: 벡터는 자동으로 메모리를 할당하고 해제한다. 따라서 수동 메모리 관리의 오류를 줄일 수 있다.
3. 배열과 유사한 성능: 벡터는 배열처럼 연속된 메모리를 사용하여 요소에 대한 빠른 접근을 제공한다.
4. 표준 라이브러리와의 통합: C++ 표준 라이브러리의 많은 기능들이 std::vector와 호환된다.
5. 안전성과 편의성: 벡터는 .at() 메서드를 통해 범위 검사 접근을 제공하며, 반복자, 범위 기반 for 루프 등을 지원한다.
6. …

 

위와 같은 장점들이 있다고 한다.

 

하지만 가장 크게 체감되는 장점은 “의식의 흐름대로 코드를 짜기 쉽다”인 것 같다.

 

하지만 매개변수로 복잡한 vector<int>& a을 입력하는 것은 생각보다 힘들었다.

 

몇 번 번갈아 사용해 보면서 더 편한 방식으로 풀어야겠다.

 

---