💡 자료구조와 알고리즘 미션

1. 여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다.

이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.

✅ 해시 테이블을 이용하여 학생의 정보를 저장할 것 같다.

해시 테이블은 해시 함수를 통해 입력값의 key를 받아 고유한 값 index로 변환을 시켜 테이블에 저장하는 자료구조이다.

O(1)의 시간 복잡도로 데이터 삽입, 삭제, 조회가 가능하기 때문에 가장 효율적으로 학생의 정보를 관리할 수 있다.

하지만 해시 함수에 의해 다른 데이터가 동일한 버킷에 할당되어 충돌이 발생한다면 O(n)의 시간 복잡도로 효율성이 줄어들 수 있다.

이를 해결하기 위해, 각 버킷마다 연결리스트를 통해 충돌 데이터를 이어주는 분리 연결법, 또는 버킷에 하나의 데이터만 저장하고 충돌 시 다른 비어있는 버킷에 할당해주는 개방 주소법을 통해 충돌을 방지할 수 있다.

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

✅ "주문은 들어온 순서대로 처리됩니다"라는 의미는 FIFO(First In First Out)를 뜻하며, 해당 개념의 대표적인 자료구조는 큐(Queue) 가 있다.

큐는

1. 양방향 리스트로 구현이 가능하며

2. head와 tail 노드가 지정되어, 첫 노드가 처리 후 제거되어도 다음 tail을 O(1)의 시간복잡도로 조회가 가능하고

3. 각 노드가 prev와 next를 통해 앞, 뒤 노드의 주소를 저장하고 있어서 삽입, 삭제 또한 O(1)의 시간복잡도로 작업이 가능하다.

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

✅

기존: 1, 2, 3, 4 입력 시, (출구)[1,2,3,4](입구) <- 삽입 후, 4->3->2->1 로 출력

변경: 1, 2, 3, 4 입력 시, 삽입 -> (출구)[4,3,2,1](입구) 후, 4->3->2->1 로 출력

ReverseStack 클래스 작성

class ReverseStack {
    constructor() {
        this.list = new LinkedList();
    }

    push(data){
        this.list.insertLast(data);
    }

    pop() {
        try {
            return this.list.deleteLast();
        } catch (error) {
            return null;
        }
    }

    peek() {
        return this.list.getNodeAt(this.list.count-1)
    }

    isEmpty() {
        return this.list.count === 0;
    }

    printAll() {
        this.list.printAll()
    }

}

// 결과 출력
let reverseStack = new ReverseStack();
let stack = new Stack();

console.log("=======Stack input=======");

stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);

stack.printAll();

console.log(stack.pop().data);
console.log(stack.pop().data);
console.log(stack.pop().data);
console.log(stack.pop().data);


console.log("=======ReverseStack input=======");
reverseStack.push(1);
reverseStack.push(2);
reverseStack.push(3);
reverseStack.push(4);

reverseStack.printAll();

console.log(reverseStack.pop().data);
console.log(reverseStack.pop().data);
console.log(reverseStack.pop().data);
console.log(reverseStack.pop().data);

=======Stack input=======
[4, 3, 2, 1]
4
3
2
1
=======ReverseStack input=======
[1, 2, 3, 4]
4
3
2
1

사실 문제를 제대로 이해했는 지 맞나 모르겠다 ㅎㅎ..

스택은 결국 FILO(First In Last Out)이니 입구와 출구가 동일하다고 볼 수 있지 않나..? 라고 생각했지만

인덱스가 전환되는 것에 집중하여 기존에 삽입된 인덱스가 전환되는 형태로 스택을 수정하였다.

즉, 연결리스트의 head부분으로 저장되는 것이 아닌 tail (여기서는 리스트의 count 인덱스)에 데이터를 연결하면 마지막 인덱스부터 저장되는 스택을 구현할 수 있었다.

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

✅

hashFunction(name){
   // 1. 이름 유니코드로만 설정 : 63.6%
   return name.charCodeAt(0) % 10;

  // 2. 이름의 각 유니코드를 더한 값 : 63.6%
  return [...name].reduce((acc, cur) => acc + cur.charCodeAt(0), 0) % 10;

  // 3. 첫 자의 유니코드의 각 숫자를 합친 값 : 54.5%
  return [...(name.charCodeAt(0) + '')].reduce((acc, cur) => acc + cur.charCodeAt(0), 0) % 10;
}

// 중복 비율 계산
getDuplicateFrequency(arr) {
    let array = arr.map((name) => this.hashNameFunction(name));
    const frequency = array.reduce((acc, cur) => {
        acc[cur] = (acc[cur] || 0) + 1;
        return acc;
    }, {});

    let duplicatedCount = 0;
    let totalCount = array.length;

    for (let key in frequency) {
        if (frequency[key] > 1) {
            duplicatedCount += frequency[key];
        }
    }

    console.log(Math.round((duplicatedCount / totalCount) * 100 * 10) / 10);
}

좋은 해시 함수를 작성하는 것은 어려운 것 같다. 여러 방면에서 코드를 작성해봐도 생각보다 중복 비율이 줄어들지는 않는 것 같다.

📒 회고

이번 주말은 여러 일정이 겹쳐있어서 미션을 수행할 시간이 많이 부족했뿐만 아니라, 생각보다 미션이 오래 걸렸던 것 같다.

다음 주 부터는 미리미리 강의 정리하면서 발자국도 함께 작성하는 것이 중요할 것 같고 미션도 올라오는 대로 바로 시작해야

안정적으로 미션을 제출할 수 있을 것 같다.

추가로 스터디에서 사람이랑 미션에 대해서도 얘기해보며 집단 지성을 이용해서 조금 더 획기적인 아이디어들을

토론하고 고민해보는 것도 좋은 생각일 것 같다!