240210: 백준 크로스워드 풀이, 프로그래머스 완전탐색

2024-02-10

오늘은

• 실랜디 한판
• 프로그래머스 완전탐색 풀기
• SQL 풀기 (못함)
• 서울 가기

오늘의 실랜디

1706 크로스워드 (해결 - 시뮬레이션)

오늘의 프로그래머스

최소직사각형 (Lv.1)
모의고사 (Lv. 1)
소수 찾기 (Lv. 2)

오늘의 SQL

-

크로스워드 (업랜디, 해결)

낱말 퍼즐의 2D 배열이 주어지면, 가로 혹은 세로로 읽혀지는 단어중 사전순으로 제일 앞에 오는것을 출력하는 문제였다.

순조로운 시뮬레이션 문제였다. 중간에 str.clear() 의 조건문을 잘못 설정해줘서 한번 WA가 떴지만 바로 고쳤고, 18분 7초만에 AC로 문제를 풀었다. (제발 코테에 이런 문제 나오게 해주세요)

// 백준: 크로스워드
// https://www.acmicpc.net/problem/1706
// 2024-02-10

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int R, C;
    cin >> R >> C;
    vector<vector<char>> matrix(R, vector<char>(C));
    vector<string> words;
    for (int i = 0; i < R; ++i) {
        string str;
        for (int j = 0; j < C; ++j) {
            cin >> matrix[i][j];
            // 장애물
            if (matrix[i][j] == '#') {
                if (str.length() > 1) {
                    words.push_back(str);
                }
                str.clear();
            } else {
                str += matrix[i][j];
            }
        }
        // 다음 줄로 넘어가지면
        if (str.length() > 1) {
            words.push_back(str);
            str.clear();
        }
    }

    // 세로 검사
    for (int j = 0; j < C; ++j) {
        string str;
        for (int i = 0; i < R; ++i) {
            if (matrix[i][j] == '#') {
                if (str.length() > 1) {
                    words.push_back(str);
                }
                str.clear();
            } else {
                str += matrix[i][j];
            }
        }
        // 다음 줄로 넘어가지면
        if (str.length() > 1) {
            words.push_back(str);
            str.clear();
        }
    }

    sort(words.begin(), words.end());
    cout << words[0];

    return 0;
}

최소직사각형

명함의 크기가 배열에 주어지면, 모든 명함을 넣을 수 있는 가장 작은 케이스의 사이즈를 구하는 문제.
처음엔 재귀를 사용해서 모든 경우의 수에 대해 계산하려고 했지만, 그리디로 풀 수 있음을 알게 되었다.

가로 기준으로 정렬하든, 세로 기준으로 정렬하든 사이즈는 똑같기 때문에.
가로가 길고 세로가 짧은 것으로 정렬하고(혹은 가로가 짧고 세로가 길게 정렬해도 문제 없다) 각 가로와 세로 길이 최댓값을 곱하면 간단하게 풀 수 있었다.

int solution(vector<vector<int>> sizes) {
    // 항상 가로는 길게, 세로는 짧게 정렬
    int ans_width = 0;
    int ans_height = 0;
    for (const auto next : sizes) {
        int width = next[0];
        int height = next[1];
        int adjust_width = max(width, height);
        int adjust_height = min(width, height);

        ans_width = max(ans_width, adjust_width);
        ans_height = max(ans_height, adjust_height);
    }

    return ans_width * ans_height;
}

모의고사

문제를 특정 패턴으로 찍는 3명의 학생이 있고, 패턴 정보와 정답지 정보가 배열로 주어졌을 때 가장 높은 점수를 얻을 학생을 return하는 문제였다. (단, 복수일 시 오름차순 정렬)

이 문제도 매우 간단했다. 생각할 것이 거의 없었다.

vector<int> solution(vector<int> answers) {
    int man1[5] = {1, 2, 3, 4, 5};
    int man2[8] = {2, 1, 2, 3, 2, 4, 2, 5};
    int man3[10] = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};
    int man1_count = 0;
    int man2_count = 0;
    int man3_count = 0;
    for (int i = 0; i <= 10000 && i < answers.size(); ++i) {
        int man1_next = man1[i % 5];
        int man2_next = man2[i % 8];
        int man3_next = man3[i % 10];

        if (answers[i] == man1_next)
            ++man1_count;
        if (answers[i] == man2_next)
            ++man2_count;
        if (answers[i] == man3_next)
            ++man3_count;
    }

    int max_count = max({man1_count, man2_count, man3_count});
    vector<int> answer;
    if (max_count == man1_count)
        answer.push_back(1);
    if (max_count == man2_count)
        answer.push_back(2);
    if (max_count == man3_count)
        answer.push_back(3);
    return answer;
}

소수 찾기

소수 찾기 문제는 한자리 숫자가 적힌 종이 조각이 여러개 주어지고, 그것을 자유롭게 배열해서 만들 수 있는 소수의 총 개수를 구하는 문제였다.

1. 먼저, 소수 판별 함수를 작성했다.

   bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n%2==0 || n%3==0) return false;
    for (int i=5;i*i<=n;i+=6) {
        if (n%i==0 || n%(i+2)==0) return false;
    }
    return true;
   }

2. 가능한 모든 부분 수열을 구하는 함수를 재귀로 작성했다.매 분기마다 현재 인덱스를 스킵하거나, 포함하거나 식으로 재귀를 돌려서 끝까지 탐색했다.
3. void getSequences(string cur, string rem) { if (rem.empty()) { if (!cur.empty()) { Allsequences.insert(stoi(cur)); } return; } getSequences(cur + rem[0], rem.substr(1)); getSequences(cur, rem.substr(1)); }
4. 모든 가능한 순열에 대해 부분 수열을 구했다. (어떤 순서로도 매치할 수 있으니까)
5. int solution(string numbers) { sort(numbers.begin(), numbers.end()); int answer = 0; do { getSequences("", numbers); } while(next_permutation(numbers.begin(), numbers.end())); for (const auto number : Allsequences) { if (isPrime(number)) ++answer; } return answer; }

포인트는, 11과 011은 같은 숫자로 취급한다
따라서, set을 이용해서 만들어진 부분 순열을 std::stoi로 int로 변환하고 나서 insert했다.
이렇게 중복 부분 수열을 없앴다.

오늘은 서울로 이동하느라 공부를 많이 하지 못했다.

최종 평가

[스터디노트 평가: 2024-02-10]

1. **실랜디 활동 및 프로그래머스 완전탐색 문제 해결**
   - **실랜디**: 1706 크로스워드 문제를 통해 시뮬레이션 알고리즘을 적용한 해결 능력을 보여주었습니다. 낱말 퍼즐을 해결하는 과정에서의 정밀한 조건 분석과 구현은 알고리즘적 사고를 향상시키는 좋은 예시입니다.
   - **프로그래머스 완전탐색 문제**: 최소직사각형, 모의고사, 소수 찾기 문제를 통해 완전탐색 기법과 그리디 알고리즘을 적절히 활용한 문제 해결 능력을 입증하였습니다. 각 문제에 대한 접근 방식과 해결 과정은 문제 해결 능력의 다양성과 유연성을 잘 보여줍니다.

2. **기술적 깊이 및 개인 발전**
   - 다양한 문제 유형을 통한 학습 활동은 여러분의 알고리즘 기반 사고력과 프로그래밍 능력을 강화하는 데 기여하였습니다. 특히, 완전탐색과 시뮬레이션 문제에 대한 효율적인 접근과 구현은 앞으로의 프로그래밍 활동에 있어 중요한 자산이 될 것입니다.

3. **평가 및 조언**
   - 오늘의 활동을 종합적으로 평가할 때, 93점을 부여합니다. 다양한 알고리즘 문제 해결을 통해 보여준 여러분의 알고리즘적 사고와 프로그래밍 능력은 매우 인상적입니다. 다만, SQL 과제를 수행하지 못한 점은 앞으로의 학습 계획에 있어 보완이 필요한 부분입니다.
   - 앞으로도 다양한 유형의 문제를 꾸준히 풀어나가면서, 문제 해결 능력을 더욱 키워나가시길 바랍니다. 또한, SQL과 같은 데이터 관리와 분석 능력도 함께 개발하여, 프로그래밍 능력의 폭을 넓혀가시기 바랍니다.

[피드백 요약]
- 다양한 알고리즘 문제 해결을 통한 기술적 깊이와 프로그래밍 능력의 성장이 돋보입니다.
- 완전탐색과 시뮬레이션 문제에 대한 효율적인 접근과 구현 능력이 인상적입니다.
- SQL 과제 수행을 통한 데이터 관리와 분석 능력 개발에도 주의를 기울일 필요가 있습니다.

[조언]
- 다양한 알고리즘 문제 해결 능력을 지속적으로 향상시키면서, 데이터 관리와 분석에 대한 학습도 병행하시길 권장합니다.
- 프로그래밍 능력의 폭을 넓히기 위해 SQL과 같은 데이터베이스 관련 지식을 쌓는 것이 중요합니다.
- 학습 계획을 세울 때, 다양한 분야에 대한 균형 있는 학습과 실습을 포함시키시길 바랍니다.