자료구조와 알고리즘

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

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

• 특별한 기능으로 저장하고 열람이 있습니다.

  • 데이터 저장에 유리한 연결리스트가 있지만 자료를 열람할 때 비효율적일 거 같습니다.

  • 데이터를 열람하는 건 배열의 인덱스 참조로 빠르게 열람할 수 있을 겁니다. 하지만 저장할 때 성능이 좋지 않습니다.

• 그래서 빠른 데이터 읽기, 삽입을 할 수 있는 해시 테이블을 사용하려고 합니다.

  • 해시 함수를 이용해서 데이터에 빠르게 접근할 수 있고 값을 연결리스트로 구현할 시 데이터 저장, 삭제가 용이합니다.

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

• 큐 자료구조를 사용할 겁니다.

  • 먼저 들어온 작업을 먼저 처리하는 규칙을 활용하기 위해서 입니다.

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

• 기존에 작성한 Stack 코드에서 삽입, 제거, 참조의 인덱스 0을 변경했습니다.

  • 삽입의 경우 제일 끝자리에 새로 추가하는 값이라서 list 의 count 로 변경했습니다.

  • 제거와 참조의 경우 list 의 count 에서 -1 로 값을 변경했습니다. (인덱스는 0부터 시작)

• [깃허브 코드]

/*
    스택에 필요한 연산
     */
    // 1. push - 데이터 삽입
    public void push(Object data) {
        // 연결리스트의 head 에 삽입
        this.list.insertAt(this.list.getCount(), data);
    }

    // 2. pop - 데이터 제거
    public Node pop() {
        try {
            // 연결리스트의 head 에서 꺼내기
            return this.list.deleteAt(this.list.getCount() - 1);
        } catch (Exception e) {
            // 비어있는 리스트 지울경우 예외 던지기
            return null;
        }
    }

    // 3. peek - 데이터 참조
    public Node peek() {
        return this.list.getNodeAt(this.list.getCount() - 1);
    }

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

• name 을 Object 타입으로 받아서 name이 String 타입이라는 걸 알려주기 위해 String 으로 형변환 했습니다.

• set() 의 경우 key, value 매개변수는 값을 HashData 에 저장할 때 사용해야 해서 이름을 바꾸지 않았습니다.

  • hashFuntion() 에 매개변수로 value 를 주었습니다.

• get(), remove() 메서드의 매개변수에서 받아오는 타입을 Object 로 문자열을 받아올 수 있게 변경했습니다.

   

• [깃허브 코드]

public int hashFunction(Object name) {
        String name1 = (String) name;
        return name1.charAt(0) % 10;
    }


public void set(int key, Object value) {
     DoublyLinkedList list = (DoublyLinkedList) this.arr[this.hashFunction(value)];
}
public Object get(Object key) {
     DoublyLinkedList list = (DoublyLinkedList) this.arr[this.hashFunction(key)];
}
public DoublyNode remove(Object key) {
     DoublyLinkedList list = (DoublyLinkedList) this.arr[this.hashFunction(key)];
}

 ※ 출처

[인프런 / 그림으로 쉽게 배우는 자료구조와 알고리즘 (감자) / 섹션 1~2]