이 문제들을 다 풀면 linked list, hash table 개념 정복!

 

Q. 연결리스트에 대한 설명으로 맞는 것을 모두 고르면?

A 연결 리스트는 특정 인덱스의 노드를 찾을 때 배열보다 빠르다는 장점이 있다.

B 단일 연결 리스트에서 각 노드는 자신의 이전 노드를 알 수 없다.

C 연결 리스트는 반드시 리스트의 끝(tail)에만 노드를 추가해야 한다.

D 배열보다 메모리를 더 효율적으로 사용할 수 있는 자료구조이다.

E 이중 연결 리스트는 하나의 값을 저장하기 위해 2개의 노드가 필요하다.

 

answer B, D

B 단일 연결 리스트에서 각 노드는 자신의 이전 노드를 알 수 없다. (이것은 이중연결리스트에 대한 설명!)

D 배열보다 메모리를 더 효율적으로 사용할 수 있는 자료구조이다. 

 

A는 맞는 설명

: 배열의 시간복잡도는 1이다. 각각의 엘리먼트가 인덱스로 접근에 가능하다. 그래서 linked list의 시간복잡도가 더 오래걸린다.

C는 맞는 설명

: 어떤 노드의 next에도 다 들어갈 수 있다. 들어가고 싶은 자리의 노드의 next를 새 노드에 연결하고 새 노드의 next 를 기존 뒤에 남은 노드에 연결시키면 가능!

D는 맞는 설명

: 배열은 정적인 크기, linked list는 동적인 크기를 할당할 수 있기 때문에 효율적인 것은 linked list다.

 

Q. 노드가 5개인 연결 리스트의 모든 노드를 가장 효율적으로 삭제하고 싶을 때 총 몇 번의 연산이 필요한가? (단, 언어는 자바스크립트를 사용한다.)

A 1

B 2

C 3

D 4

E 5

 

answer A 1

자바스크립트는 참조개념이기 때문에 참조를 끊어주면 더이상 접근이 안된다.

그래서 가장 첫번째 노드만 없애주면 다 없어진다.

garbage collection 이라는 것이 더이상 참조하지 않는 객체는 알아서 메모리에서 해제를 시켜주는 개념이다!

 

 

Q. 다음과 같은 코드의 실행 결과로 적합한 것은?

const list = new LinkedList();
list.insert(5);
list.insert(10);
list.insert(15);
list.insert(20);
list.removeAt(0);
list.removeAt(2);
const value = list.findAt(1);
console.log(value);

 

answer 15

 

 

Q. 10개의 노드가 연결되어 있는 단일 연결 리스트는 원하는 값을 찾기 위해 최대 10번의 검색이 필요하다. 그렇다면 10개의 노드가 연결되어 있는 이중 연결 리스트는 원하는 값을 찾기 위해 최대 몇 번의 검색이 필요한가?

 

answer 10

 

Q. 해시 테이블과 해시 함수에 대한 설명으로 틀린 것을 모두 고르면?

A 두 개 이상의 값에 하나의 키를 사용할 수 없다.

B 키와 값을 한 쌍으로 저장할 수 있는 자료구조이다.

C 해시 함수는 어떤 값이 들어오더라도 고유한 값으로 만들어 출력하기 때문에 입력 값과 출력 값을 1대1로 매핑할 수 있다.

D 해시 테이블은 내부적으로 SHA-256 해시 함수를 사용한다.

E 해시 함수를 통해 만들어진 출력 값은 원래의 입력 값으로 되돌릴 수 없다.

 

answer C, D

C 해시 함수는 어떤 값이 들어오더라도 고유한 값으로 만들어 출력하기 때문에 입력 값과 출력 값을 1대1로 매핑할 수 있다.

D 해시 테이블은 내부적으로 SHA-256 해시 함수를 사용한다.

 

A 1대 다가 안되지 않느냐? 라고 물어보는 문제

키와 밸류가 각각 1:1로 들어간다.

 

B A와 같은 말이다.

 

C 1:1 매핑은 맞는데 어떤 값이 들어오더라도 고유한 값이 되는 것은 아니다. 같은 값이 리턴되어 충돌이 일어날 수 있다.

이것이 해쉬충돌!

 

D sha256 함수는 해쉬 함수의 일종인데 암호화를 할 때 쓴다. 

 

E 값으로 키를 알아낼 수 없기 때문에 !

 

 

Q. 다음과 같은 코드의 실행 결과로 적합한 것은?

const hashTable = new HashTable();

hashTable.insert("apple", "I love apple");
hashTable.insert("pineapple", "I love pineapple");
hashTable.insert("mint_choco", "... what?");
hashTable.insert("apple", "I need a macbook pro");

console.log(hashTable.retrieve("apple"));

 

A I love apple

B I love pineapple

C ... what?

D I need a macbook pro

E undefined

 

 

answer I need a macbook pro

key value는 1:1이기 때문에 덮어씌운다. (overwriting)

이건 덮어씌우는 것이기에 충돌이랑 다른 개념

충돌은 hashing 과정에서 나는거다. (key가 해쉬함수를 들어가서 리턴되는 index가 같은 것이 충돌)

storage에 같은 index에 같이 들어가는게 hashing 충돌

 

 

Q. HashTable이 A라는 해시 함수를 사용할 때, 다음 코드를 실행 한 후 해시 충돌이 발생하는 횟수는?

function A(key) {
  return key.length % 5;
}

const hashTable = new HashTable();
hashTable.insert("name", "kim")
hashTable.insert("age", 22)
hashTable.insert("height", 177)
hashTable.insert("weight", 65)
hashTable.insert("mobile", "010-9191-2929")

 

A 0

B 1

C 2

D 3

E 4

 

answer 2

해시함수가 key의 length를 5로 나눈 나머지를 리턴하는 것이기 때문에

key의 length가 동일할 때 같은 값을 리턴해서 충돌이 나게 될 것이다. 

그럼 length가 같은 키가 몇개인지만 찾으면 됨

여기서 총 3개(height, weight, mobile)가 6자로 동일하니까 2번 충돌이 난다는 것이다.