99클럽 코테 스터디 9일차 TIL C++ 단방향 그래프

오늘의 학습 키워드

문제 1: 그래프 (Graph)

https://school.programmers.co.kr/learn/courses/30/lessons/77486#qna

공부한 내용 본인의 언어로 정리하기

문제 1: 그래프 (Graph)

 

(1) 단방향 그래프
단방향 그래프는 노드 간의 연결이 한 방향으로만 이루어지는 구조로, 이 문제에서는 판매자와 그들의 소개자 간의 관계를 나타내는 데 사용되었습니다. 각 판매자는 자신의 소개자에게 수익의 일부를 분배해야 하므로, 이러한 관계를 효과적으로 모델링할 수 있습니다.

 

(2) 잘못된 최적화 시도: 판매자별로 수익을 모두 더해서 한번에 수익 분배 시도
수수료는 버림처리하므로, <1> 수익을 합산해서 구한 수수료와 <2> 각 수익에서 구한 수수료의 합이 다르다는 것을 간과했습니다.
예를 들어서, A는 B의 소개로 조직에 들어왔으며(A의 부모는 B), 5, 5, 5, 10 씩 4번에 걸쳐 수익을 냈다고 해봅시다.

• <1> 수익을 합산해서 구한 수수료는 (5 + 5 + 5 + 10) / 10 = 2.5로 2입니다.
• <2> 각 수익에서 구한 수수료의 합산은 (0 + 0 + 0 + 1) = 1입니다.

따라서 판매자별로 수익을 합산해서 한번만 탐색하려는 시도(<1>)는, 문제의 답(<2>)과는 다른 결과를 가져올 수 있습니다.

 

(3) 최적화 시도: 나누어야 할 수익이 0보다 작을 때 탐색을 멈추어야 합니다.
재귀 탐색을 멈추는 조건을 추가하여, 수익이 0일 때 더 이상 탐색하지 않도록 했습니다. 이 조건은 간단해 보이지만, 구현할 때 세심한 주의가 필요했습니다. 자원을 효율적으로 사용하려면 예외 처리를 꼼꼼하게 확인하는 연습이 필요합니다.

 

(4) map의 순회
C++에서 map을 순회하는 방법은 아래 두 가지 방법이 대표적입니다.

• <1> 반복자 (Iterator)를 사용한 순회

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main() {
    map<string, int> myMap;
    myMap["apple"] = 3;
    myMap["banana"] = 5;
    myMap["orange"] = 2;

    // 반복자를 사용한 순회
    for (auto it = myMap.begin(); it != myMap.end(); ++it) {
        cout << it->first << ": " << it->second << endl;
    }

    return 0;
}

 

• <2> 범위 기반 for 루프 : C++11 이상에서 사용.

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main() {
    map<string, int> myMap;
    myMap["apple"] = 3;
    myMap["banana"] = 5;
    myMap["orange"] = 2;

    // 범위 기반 for 루프를 사용한 순회
    for (const auto& pair : myMap) {
        cout << pair.first << ": " << pair.second << endl;
    }

    return 0;
}

 

(4) 전체 풀이
이 문제는 Python으로도 풀어본 경험이 있었습니다. (2021.12.22 - [코딩테스트/python] - 프로그래머스_python_다단계 칫솔 판매)하지만 오랜만에 코드를 보니 같은 실수를 반복하고 있었습니다.

#include <string>
#include <vector>
#include <map>
#include <stack>

using namespace std;

map<string, string> m_parent;
map<string, int> m_income;
string m_root = "-";

void distributeIncome(string child, int income) {
    if (income == 0) return; // 수익이 0인 경우에는 종료 >> 이 부분이 있어야만 시간 조건을 모두 통과할 수 있음.

    // 10%를 부모에게 분배
    int parentIncome = income / 10;
    int childIncome = income - parentIncome; // 90%는 자식이 가져감

    m_income[child] += childIncome; // 자식에게 90% 추가

    string parent = m_parent[child];
    if (parent == m_root) return;
    distributeIncome(parent, parentIncome); // 부모에게 10% 분배
}

vector<int> solution(
    vector<string> enroll, 
    vector<string> referral, 
    vector<string> seller, 
    vector<int> amount
) {
    // 부모-자식 관계 설정
    for (int i = 0; i < enroll.size(); i++) {
        m_parent[enroll[i]] = referral[i];
    }

    // 판매자 수익 계산
    for (int i = 0; i < seller.size(); i++) {
        string currentSeller = seller[i];
        int saleAmount = amount[i] * 100; // 판매 금액을 100배로 변환
        distributeIncome(currentSeller, saleAmount); // 각 판매자에 대해 수익 분배
    }

    // 결과 생성
    vector<int> answer;
    for (string str : enroll) {
        answer.push_back(m_income[str]); // 각 판매자의 최종 수익 추가
    }

    return answer;
}

오늘의 회고

이번 학습을 통해 그래프의 개념을 이해하고, 재귀를 활용한 문제 해결 방법을 다시금 확인했습니다. 특히, 중복 판매자에 대한 수익 분배 로직을 설계할 때 발생할 수 있는 오류를 경험하며, 문제를 해결하기 위해 필요한 조건을 세심하게 고려해야 한다는 점을 깨달았습니다.