인프런 워밍업 클럽 4기 CS 전공지식 3주차 미션

2025-06-15T05:44:39.260Z

H_dong

컴퓨터 구조

다운로드 링크

문제 1. STOREB(1001) 명령어를 만들어보세요.,

(OPcode는 1001이고 operand가 가리키는 RAM주소에 현재 레지스터B의 데이터 저장하는 기능)

문제 2. A와 B를 비교해서 A와 B가 같으면 0, A가 더 크면 1, B가 더 크면 2를 출력 레지스터에 출력하는 어셈블리어를 작성해보세요.

자료구조와 알고리즘

문제

여러분은 문서 압축 프로그램을 개발해야 합니다. '허프만 코딩'이라는 압축 알고리즘을 사용하여, 아래와 같은 결과가 나오도록 구현해보세요. (필요하다면 사용된 자료구조를 수정해도 좋습니다.)

✅ 허프만 코딩이란?

문자의 빈도수에 따라 가변 길이의 이진 코드를 부여하여
전체 데이터를 무손실 압축하는 알고리즘

✅ 핵심 개념

자주 나오는 문자 → 짧은 코드,
드물게 나오는 문자 → 긴 코드
트리 기반 구조로, 모든 문자는 prefix-free한 이진 코드로 인코딩됨

✅ 작동 원리 (요약)
1. 각 문자의 등장 횟수(빈도)를 센다
2. 가장 빈도 낮은 두 문자부터 묶어서 이진 트리로 만든다
3. 루트까지 도달하는 경로를 따라:
  - 왼쪽 자식 = 0
  - 오른쪽 자식 = 1
4. 모든 문자는 이진 문자열(코드)을 갖게 된다

huffmanCompress.cpp

#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string>
#include <cctype>
using namespace std;

class HuffmanNode {
public:
    char ch;
    int freq;
    HuffmanNode* left;
    HuffmanNode* right;
    bool isLeaf;

    HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr), isLeaf(true) {}
    HuffmanNode(HuffmanNode* l, HuffmanNode* r)
        : ch(0), freq(l->freq + r->freq), left(l), right(r), isLeaf(false) {}
};

struct Compare {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        if (a->freq == b->freq) {
            // 둘 다 리프 노드일 경우 문자 기준 비교
            if (a->isLeaf && b->isLeaf) return a->ch > b->ch;
            // 리프 노드가 아닌 경우엔 리프 노드를 우선
            return b->isLeaf;
        }
        return a->freq > b->freq;
    }
};

void buildCode(HuffmanNode* node, const string& code, unordered_map<char, string>& codeMap) {
    if (!node) return;
    if (!node->left && !node->right) {
        codeMap[node->ch] = code;
    }
    buildCode(node->left, code + "0", codeMap);
    buildCode(node->right, code + "1", codeMap);
}

vector<pair<char, string>> huffmanCompress(const string& str) {
    unordered_map<char, int> freqMap;
    for (char ch : str) freqMap[ch]++;

    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
    for (auto& [ch, freq] : freqMap) {
        pq.push(new HuffmanNode(ch, freq));
    }

    while (pq.size() > 1) {
        HuffmanNode* left = pq.top(); pq.pop();
        HuffmanNode* right = pq.top(); pq.pop();
        pq.push(new HuffmanNode(left, right));
    }

    HuffmanNode* root = pq.top();
    unordered_map<char, string> codeMap;
    buildCode(root, "", codeMap);

    vector<pair<char, string>> result;
    for (auto& [ch, code] : codeMap) {
        result.emplace_back(ch, code);
    }

    sort(result.begin(), result.end(), [](const pair<char, string>& a, const pair<char, string>& b) {
        return a.first < b.first;
        });

    return result;
}

출력 결과

int main() 
{
    string str = "Lorem ipsum dolor sit amet consectetur adipiscing elit. Consectetur adipiscing elit quisque faucibus ex sapien vitae. Ex sapien vitae pellentesque sem placerat in id. Placerat in id cursus mi pretium tellus duis. Pretium tellus duis convallis tempus leo eu aenean.";

    vector<pair<char, string>> result = huffmanCompress(str);

    for (const auto& [ch, code] : result) {
        cout << "[ '" << ch << "', '" << code << "' ]" << endl;
    }
    return 0;
}

답변 0