CS 전공지식 스터디 3기 [1주차] 자료구조와 알고리즘 미션

Q1. 여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다. 이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.

A1.

학생의 정보는 이름, 학번, 성적 등의 필드를 포함하므로, 효율적인 검색과 관리를 위해 해시테이블을 사용하는 것이 적절합니다.

그 이유는 학생은 학번이라는 고유 ID를 갖고 있기 때문에, 학번을 키로 사용한다면, 시간복잡도가 평균 O(1)이 되므로 빠른 탐색이 가능해집니다.

Q2. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.

A2.

주문은 FIFO(First-In-First-Out) 방식으로 처리되어야 하므로 큐(Queue)를 사용하는 것이 적절합니다.

이유는 스택과 다르게 큐는 먼저 들어온 데이터가 먼저 처리되는 구조이기 때문입니다.

주문 처리 과정도 먼저 들어온 주문이 먼저 처리되어야 하는 구조이기 때문에 큐 자료구조를 사용해야 한다고 생각합니다.

Q3. 우리가 구현한 스택은 0번 인덱스, 즉 입구쪽으로 데이터가 삽입되고 나오는 구조입니다. 반대로 마지막 인덱스, 즉 출구쪽으로 데이터가 삽입되고 나오는 구조로 코드를 변경해주세요.

A3.

기존코드

#include <iostream>
#include <vector>

class Stack {
private:
    std::vector<int> data;
public:
    void push(int value) {
        data.insert(data.begin(), value); // 0번 인덱스에서 삽입
    }
    
    void pop() {
        if (!data.empty()) {
            data.erase(data.begin()); // 0번 인덱스에서 삭제
        }
    }

    int top() {
        return data.front();
    }
};

변경된 스택 코드

#include <iostream>
#include <vector>

class Stack {
private:
    std::vector<int> data;
public:
    void push(int value) {
        data.insert(data.begin(), value); // 0번 인덱스에서 삽입
    }
    
    void pop() {
        if (!data.empty()) {
            data.erase(data.begin()); // 0번 인덱스에서 삭제
        }
    }

    int top() {
        return data.front();
    }
};

Q4. 해시테이블의 성능은 해시 함수에 따라 달라집니다. 수업 시간에 등번호를 이용해 간단한 해시 함수를 만들어봤습니다. 이번엔 등번호가 아닌 이름을 이용해 데이터를 골고루 분산시키는 코드로 수정해주세요. 힌트: charCodeAt() 함수를 이용 예시: name1 = "이운재"; name1.charCodeAt(0); // 51060 이운재의 0번 인덱스 ‘이’의 유니코드 출력

hashFunction(name){

}

A4.

기존 해시 함수는 등번호를 사용했지만, 이름을 기반으로 해시값을 생성해야 합니다.
이름의 각 문자에 charCodeAt() (C++에서는 ASCII 변환) 값을 활용해 해시값을 생성합니다.

#include <iostream>
#include <string>

int hashFunction(std::string name, int tableSize) {
    int hashValue = 0;
    for (char c : name) {
        hashValue = (hashValue * 31 + c) % tableSize; // 31은 일반적으로 좋은 해시 인수
    }
    return hashValue;
}

int main() {
    std::string name = "이운재";
    int tableSize = 100; // 해시 테이블 크기
    std::cout << "Hash value of " << name << ": " << hashFunction(name, tableSize) << std::endl;
}

이름의 각 문자를 ASCII 값으로 변환하여 해시값 계산하였습니다.