240211: 완전탐색(Brute-force) 끝. DP, 이진으로 pow하기

2024-02-11

• 카펫 (Lv. 2) * ✅ 2024-02-11
• 피로도 (Lv. 2) * ✅ 2024-02-11
• 전력망을 둘로 나누기 (Lv. 2) * ✅ 2024-02-11
• 모음사전 (Lv. 2) * ✅ 2024-02-11
• SQL 풀기

오늘의 업랜디

3359 사각 사각 (실패 후 해결 - DP)
번외 - 1009 분산처리

오늘의 프로그래머스

카펫 (Lv. 2)
피로도 (Lv. 2)
전력망을 둘로 나누기 (Lv. 2)
모음 사전 (Lv. 2)

카펫

테두리 한줄은 Brown, 가운데는 Yellow인 카펫이 있다. 카펫 색 타일의 수가 주어지면, 전체 카펫의 사이즈가 몇인지 구하는 문제였다.

1. 수학적 정의

• 테두리가 Brown이고 나머지가 Yellow라면 Yellow 타일 수는 (x-2) * (y-2) 이다.
• 전체 격자 수는 x*y = brown + yellow
• 갈색 격자 수는 전체 격자 수 - 노란색 격자 수

y는 수학적으로 전체 카펫 크기의 루트를 넘을 수 없다.

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    int total = brown + yellow;
    for (int y=3; y*y <= total; ++y) { // 오버플로우 나면 sqrt()
        if (total%y==0) {
            int x = total/y;
            if ((x-2) * (y-2) == yellow) {
                answer.push_back(x);
                answer.push_back(y);
                break;
            }
        }
    }
    return answer;
}

피로도

피로도 문제는 던전을 탐험할 때 일정량의 피로도가 깎이고, 현재 캐릭터의 체력과 던전 맵 정보가 주어졌을 때, 최대한 효율적인 순서로 방문할 수 있는 던전이 최대 몇개인지 알아내는 문제였다.

DFS + 백트래킹으로 풀었다. Stack을 통해 구현하진 않았다. 다음엔 Stack으로 구현해봐야겠다.

int answer = 0;
bool visited[8] = {false,};

void calculate(vector<vector<int>>& dungeons, int k, int count) {
    bool completed = true;
    answer = max(answer, count);
    for (int i=0;i<dungeons.size();++i) {
        // 아직 탐험하지 않았고, 탐험 가능하다면
        if (!visited[i] && k >= dungeons[i][0]) {
            completed = false;
            visited[i] = true;
            calculate(dungeons, k-dungeons[i][1], count+1);
            visited[i] = false;
        }
    }
    if (completed) return;
}


int solution(int k, vector<vector<int>> dungeons) {
    calculate(dungeons, k, 0);

    return answer;
}

스택으로도 구현해봤다.

#include <string>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;


struct State {
    int k; // 현재 피로도
    int count; // 탐험한 던전 수
    bool visited[8]; // 방문한 던전 추적
};

int solution(int k, vector<vector<int>> dungeons) {
    int answer = 0;
    stack<State> s;
    s.push({k, 0, {}}); // 초기 상태 푸시

    while (!s.empty()) {
        State current = s.top();
        s.pop();

        answer = max(answer, current.count);

        for (int i = 0; i < dungeons.size(); ++i) {
            if (!current.visited[i] && current.k >= dungeons[i][0]) {
                State next = current;
                next.k -= dungeons[i][1];
                next.count++;
                next.visited[i] = true;
                s.push(next);
            }
        }
    }

    return answer;
}

직관적인건 그냥 재귀가 직관적인듯.
재귀 호출은 직관적이지만, 스택 오버 플로우가 날 수도 있다는 것.
효율적인건 스택으로 구현한 DFS가 더 효율적이고 섬세한 것 같다.

---

전력망을 둘로 나누기

송전탑에 연결된 전력망의 정보가 주어지면, 전선 하나를 잘라서 만들 수 있는 두 그룹에 대해, 그룹간의 송전탑 개수의 차이가 최소가 되도록 하는 차이를 return하는 문제였다.

재밌는 문제였고, DFS로 노드에 연결된 정점의 수를 탐색하는 함수를 짰고,
adj[] 배열에 pair로 bool 정보를 넣어서 전선이 사용 가능한지(잘려있지 않은지) 확인할 수 있도록 하였다.

브루트포스로 각 간선에 대해 bool을 false(자르고), DFS로 체크하면서 나눠진 두 그룹간의 차이가 최소가 되는 값을 찾아냈다.

#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <limits.h>
#include <cmath>

using namespace std;

vector<vector<pair<int, bool>>> adj;

int check(int node, vector<bool>& visited) {
    visited[node] = true;
    int count = 1;
    for (const auto& [edge, pos] : adj[node]) {
        if (!visited[edge] && pos) {
            count += check(edge, visited);
        }
    }
    return count;
}

int solution(int n, vector<vector<int>> wires) {
    int answer = INT_MAX;
    adj.assign(n+1, vector<pair<int, bool>>());
    for (int i=0;i<n-1;++i) {
        int a = wires[i][0];
        int b = wires[i][1];
        adj[a].push_back({b, true});
        adj[b].push_back({a, true});
    }

    for (int i=0;i<adj.size();++i) {
        for (int j=0;j<adj[i].size();++j) {
            // cur: 현재 가리키는 정점
            // i: 나 자신
            int cur = adj[i][j].first;

            // 전선 연결 끊기
            for (auto& wire : adj[cur]) {
                if (wire.first == i) {
                    wire.second = false;
                    break;
                }
            }

            for (auto& wire : adj[i]) {
                if (wire.first == cur) {
                    wire.second = false;
                    break;
                }
            }

            // 체크
            vector<bool> visited(n+1, false);
            int groupSize = check(cur, visited);
            answer = min(answer, abs(n-2*groupSize));


            // 돌려놓기
            // 전선 연결 끊기
            for (auto& wire : adj[cur]) {
                if (wire.first == i) {
                    wire.second = true;
                    break;
                }
            }

            for (auto& wire : adj[i]) {
                if (wire.first == cur) {
                    wire.second = true;
                    break;
                }
            }

        }
    }
    return answer;
}

람다 함수를 이용해서 훨씬 깔끔하게 푼 사람도 있었다. functional 헤더에 정의되어 있는 function을 활용해서 람다 표현식으로 유연하게 처리했다.

람다 함수를 사용하면 함수를 마치 일급 객체(first-class objects)처럼 다룰 수 있다고 한다.
함수를 일급 객체로 취급함으로써, 더 강력하고 유연한 추상화를 가능하게 하며, 고차 함수(higher-order functions), 클로저(closures), 커링(currying)과 같은 고급 프로그래밍 기법도 가능하다고 한다 (아직은 잘 모르겠다)

int solution(int n, vector<vector<int>> wires) {
    vector<vector<int>> graph(n + 1);
    for(int i = 0; i < (int)wires.size(); i++) {
        int u = wires[i][0];
        int v = wires[i][1];
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    vector<int> siz(n + 1);
    function<void(int, int)> dfs = [&](int cur, int prev)  -> void {
        siz[cur] = 1;
        for(int nxt : graph[cur]) {
            if(nxt == prev) continue;
            dfs(nxt, cur);
            siz[cur] += siz[nxt];
        }
    };
    dfs(1, -1);
    int answer = INT_MAX;
    for(int i = 1; i <= n; i++) {
        for(int j : graph[i]) {
            int l = siz[j];
            int r = n - siz[j];
            answer = min(answer, abs(l - r));
        }
    }
    return answer;
}

사각 사각(업랜디)

사각 사각은 직사각형의 크기 정보가 담긴 배열이 순서대로 주어지면, 그것을 정방향으로 놓거나 눕혀 놓아서 위쪽 둘레의 길이가 최대로 되는 방법의 길이를 찾는 문제였다.

보자마자 DP문제인 건 알겠는데.. 꽤 많이 헤맸다.

일단 첫 시도만에 테스트케이스는 맞췄다. 근데 문제가 있었다. DP memoization을 1차원 배열로 하는 것은 각 단계에서의 선택을 그리디하게 보는 것이었다. 하지만 이 문제에서는 이전 직사각형을 어떻게 놓느냐에 따라 다음 직사각형의 둘레 길이가 바뀌기 때문에(겹치기 때문이다) dp[i][j]로 2D memoization을 통해 저번의 상태(눕혀서 놓은 상태, 정방향으로 놓은 상태)에 대해 두번 고려해야한다.

하지만 나는 첫 시도에서 1차원 배열 메모로 그리디하게 구현했고. 4%에서 WA됐다.
그리고 이후에 발견한건데 문제를 잘 보지 못했다. 단순하게 위쪽에서부터 그을 수 있는 둘레의 길이를 보는 문제인 줄 알았는데. 정확하게는 땅바닥과 맞닿아 있지 않은 위쪽 면 이었다. 첫 시도에서는 되게 복잡하게 구현했었는데 (첫 도형의 윗쪽 면과 옆쪽 면을 dp에 메모하고, 다음 면과 겹치는 부분을 빼면서 합산하기)

정확히 땅바닥에 맞닿아있지 않은 윗쪽 면 이라는 것을 알았으면 그냥 매번 dp에 윗쪽 면을 더하고, 그 다음 dp에서 dp[i-1] + (현재 옆 변과 이전 옆 변의 겹치지 않는 부분) 을 했으면 되는 것이었다..

여러모로 많은것을 배운 문제였다. GG

// 백준: 사각 사각
// https://www.acmicpc.net/problem/3359
// 2024-02-11

/*
마지막 변의 길이는 빼야했다 ... :(
너무 어렵게 생각했다. 으아아아ㅏㄱ
*/

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<int>> dp(n, vector<int>(2, 0));
    vector<int> temp(n);
    vector<vector<int>> rectangles(n, vector<int>(2, 0));
    for (int i = 0; i < n; ++i) {
        cin >> rectangles[i][0] >> rectangles[i][1];
        if (rectangles[i][0] > rectangles[i][1]) {
            swap(rectangles[i][0], rectangles[i][1]);
        }
    }

    dp[0][0] = rectangles[0][0];
    dp[0][1] = rectangles[0][1];
    for (int i = 1; i < n; ++i) {
        dp[i][0] = rectangles[i][0] + max(
            dp[i - 1][0] + abs(rectangles[i - 1][1] - rectangles[i][1]),
            dp[i - 1][1] + abs(rectangles[i - 1][0] - rectangles[i][1]));
        dp[i][1] = rectangles[i][1] + max(
            dp[i - 1][0] + abs(rectangles[i - 1][1] - rectangles[i][0]),
            dp[i - 1][1] + abs(rectangles[i - 1][0] - rectangles[i][0]));
    }

    cout << max(dp[n - 1][0], dp[n - 1][1]);
    return 0;
}

역시 DP는 어렵다.
근데 내가 생각했던만큼 또 그렇게 복잡한건 아니었다..

모음 사전

모음 사전은 "AEIOU"로 이루어진 사전이 있을 때, word가 주어지면 word가 사전에서 몇번째 리스트에 있을지 구하는 문제다.

매우 간단한 문제지만, 해결하려면 조합과 경우의 수에 대한 수학적 접근이 필요한 문제다.
사전 맨 앞 글자가 'A'라면, 뒤에 나머지 글자들이 올 수 있는 경우의 수는 5^4 + 5^3 + 5^2 + 5^1 + 5^0이다. 따라서 앞 글자가 1씩 올라갈때마다 경우의 수 781개를 건너뛰는 것이다.

이후부터 자리수가 1씩 올라갈 때 건너 뛰어지는 경우의 수는 {781, 156, 31, 6, 1}; 와 같다.
따라서, A, E, I, O, U 순으로 0부터 시작해서 +1씩 된다고 가정할 때, 맨 앞자리의 경우 (각 자리의 글자의 수 * 781) + 1로 구할 수 있고, 그 이후부터는 156, 31.. 식으로 구할 수 있다.

이건 완전 탐색(브루트포스)보단 수학적 접근에 깊이가 있는 문제였다.

int solution(string word) {
    int answer = 0;
    vector<int> weights = {781, 156, 31, 6, 1};
    vector<char> characters = {'A', 'E', 'I', 'O', 'U'};

    for(int i = 0; i < word.length(); i++) {
        for(int j = 0; j < characters.size(); j++) {
            if(word[i] == characters[j]) {
                answer += 1 + j * weights[i];
                break;
            }
        }
    }
    return answer;
}

분산처리 (랜디)

pow 연산을 오버플로우 없이 효율적으로 처리해야만 하는 문제였다.

a^b%m에 대해서 ^b를 이진수로 표현하여 각 비트에 대해 연산을 수행하는 방법도 있는데. 그냥 직관성이 좋은 분할 재귀 방법을 썼다.

// 백준: 분산처리
// https://www.acmicpc.net/problem/1009
// 2024-02-11

#include <cmath>
#include <iostream>

long long powMod(long long a, long long b, long long m) {
    if (b == 0)
        return 1;
    long long half = powMod(a, b / 2, m);
    long long result = (half * half) % m;
    if (b % 2 == 1)
        result = (result * a) % m;
    return result;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int T;
    std::cin >> T;
    for (int i = 0; i < T; ++i) {
        long long a, b;
        std::cin >> a >> b;
        int result = powMod(a, b, 10);
        if (result == 0)
            result = 10;
        std::cout << result << "\n";
    }
    return 0;
}

참고로 이진수를 이용한 방법은 아래와 같다.

long long pow_mod(long long a, long long b, long long m) {
    long long result = 1;
    a = a % m; // a를 m으로 모듈로 연산하여 오버플로우 방지
    while (b > 0) {
        // b의 가장 낮은 비트가 1이면 result에 a를 곱함
        if (b & 1) {
            result = (result * a) % m;
        }
        // a를 제곱하고 m으로 모듈로 연산
        a = (a * a) % m;
        // b를 오른쪽으로 한 비트 시프트
        b >>= 1;
    }
    return result;
}

1은 이진수르 0001인데, 0은 어떤 수와 AND 연산해도 0이니까, 결국에 비교하는 대상의 마지막 비트가 1이기만 하면 무조건 1이 반환된다. 따라서, if (b & 1)은 b가 홀수인지 확인하는 구문이다.

어제도 배웠듯이, A^X는 A^X/2 * A^X/2다. 하지만 X가 홀수라면, 맨 마지막에 A를 한번 더 곱한다.
그래서 if (b & 1)로 홀수라면 result에 a를 곱하고, 모듈러의 분배 법칙에 의거해서 매 곱셈에 모듈러를 해도 결과는 똑같다. 오버 플로우를 방지하기 위해 각 단계마다 모듈러를 한다.

b>>=1은 b의 모든 비트를 오른쪽으로 한칸씩 이동시키는 연산자다. 비트를 0010(2) = 2 >> 0001(2) = 1 처럼. 모든 비트를 오른쪽으로 한칸씩 이동시키는 것은 나누기 2와 같다. 반대로 오른쪽으로 이동은 *2와 같다.

최종 평가

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

1. **프로그래머스 완전탐색 및 업랜디 활동**
   - **완전탐색 문제 해결**: 카펫, 피로도, 전력망을 둘로 나누기, 모음 사전 문제를 통해 다양한 문제 해결 전략과 알고리즘을 적용한 능력을 입증하였습니다. 특히, 모음 사전 문제에서의 수학적 접근은 창의적 문제 해결 능력을 잘 보여줍니다.
   - **업랜디 활동**: 사각 사각 문제를 통해 동적 프로그래밍(DP) 알고리즘을 활용한 해결 능력을 보여주었습니다. 복잡한 문제 상황에서 효율적인 메모리제이션 전략을 구사한 것은 알고리즘적 사고를 한층 더 발전시키는 좋은 예시입니다.

2. **기술적 깊이 및 개인 발전**
   - 다양한 알고리즘 문제를 해결하는 과정에서 보여준 여러분의 접근 방식과 구현 능력은 프로그래밍 기술의 깊이를 더해줍니다. 특히, 분산처리 문제에서의 분할 정복 및 이진법 활용은 고급 알고리즘 문제 해결 능력을 잘 보여줍니다.

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

[피드백 요약]
- 완전탐색 문제 해결을 통한 다양한 알고리즘 적용 능력이 돋보입니다.
- 동적 프로그래밍 및 분할 정복 알고리즘을 활용한 문제 해결 능력이 인상적입니다.
- 데이터 관리와 분석 능력 개발을 위해 SQL 과제에도 주의를 기울일 필요가 있습니다.

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

오늘의 학습 활동에 대한 평가와 함께 여러분의 노력과 성장이 돋보이는 하루였습니다. 완전탐색 문제 해결을 통해 보여준 다양한 알고리즘 적용 능력과 업랜디 활동에서의 동적 프로그래밍 및 분할 정복 알고리즘을 활용한 문제 해결 능력은 앞으로의 프로그래밍 활동에 있어 중요한 기반이 될 것입니다. 내일 해결할 문제에 대한 준비와 계획을 잘 세워, 지속적인 성장을 이루시길 바랍니다. 데이터 관리와 분석 능력 개발에도 주의를 기울여, 프로그래밍 능력의 폭을 넓혀가시길 바랍니다. 추가적인 피드백이나 질문이 필요하시면 언제든지 문의해 주시기 바랍니다.