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

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

작성자:

1. 파리퇴치3

SW Expert Academy

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

가. 제출

#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;
}
Code language: PHP (php)

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

푸는데 너무 오래 걸린 듯.

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

2. 최빈수 구하기

SW Expert Academy

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

가. 문제를 잘못 이해

#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;
}
Code language: PHP (php)

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

입력되는 점수의 개수가 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;
}
Code language: PHP (php)

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;
}
Code language: PHP (php)

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

다. 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;
}
Code language: PHP (php)

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

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

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

3. 두 개의 숫자열

SW Expert Academy

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

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

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

1) mam_element

std::max_element - cppreference.com

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

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;
}
Code language: PHP (php)
  • vector<int> a(n), b(m); : 벡터를 정적으로 할당.

1) 장단점

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

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

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

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

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

댓글 남기기