안녕하세요? 사이버 쪽지 시험 반타작 맞은 사람입니다. (ㅋㅋ) 심지어 해시 테이블까지 전부 구현해 놓고 반타작을 맞았는데요. 그래도 괜찮아요. 배울 게 많으니까 행복합니다. 오답 노트 쓰는 것에 희열 있는(??) 사람이라 항상 시험을 보면 오답을 정리하곤 하는데요, 노트에 쓰는 것보다 그냥 같이 공유하는 게 좋을 것 같아서 정리해 보려고 합니다.
- 연결 리스트에 대한 설명으로 맞는 것은?
단일 연결 리스트에서 각 노드는 자신의 이전 노드를 알 수 없다.
배열보다 메모리를 효율적으로 사용할 수 있는 자료 구조이다.
처음에 쓴 답
1. 이중 연결 리스트는 하나의 값을 저장하기 위해 2개의 노드가 필요하다.
2. 단일 연결 리스트에서 각 노드는 자신의 이전 노드를 알 수 있다.
3. 배열보다 메모리를 더 효율적으로 사용할 수 있는 자료 구조이다.
1번의 답을 쓴 이유: 2개의 Node가 필요하다는 구문을 2개의 pointer가 필요하다는 말로 잘못 보았기 때문이다. 하하. 제발 덜렁거리지 말자.
2, 3번이 정답인 이유: 단일 연결 리스트에서는 포인터가 1개이기 때문에 되돌아갈 수 없어, 자신의 이전 노드를 알 수가 없다. (JS는 해당 사항이 없지만) 프로그래밍 언어는 배열의 크기를 정해 놓고 사용하는 것에 반해 배열 리스트는 첨삭이 가능한 유동적인 크기이기 때문에 배열보다 효과적으로 메모리를 사용할 수 있다.
- 노드가 5개인 연결 리스트의 모든 노드를 가장 효율적으로 삭제하고 싶을 때, 총 몇 번의 연산이 필요한가? (JS 기준)
1번
처음에 쓴 답: 5번
5번을 쓴 이유: 구현했던 코드를 생각했을 때, remove를 5번 사용해야 할 것 같다고 생각했음.
1번이 정답인 이유: 구현의 문제가 아닌 자료 구조 문제이다. link로 이어진 자료 구조 형태이기 때문에 head에 있는 pointer를 잇지 않고 한 번만 끊어 버리기만 한다면 뒤에 있는 4개 전부 끊어지는 것이다.
- 해시 테이블과 해시 함수에 대한 설명으로 틀린 것을 모두 고르면?
해시 테이블은 내부적으로 SHA-256 해시 함수를 사용한다.
해시 함수는 어떤 값이 들어오더라도 고유한 값으로 만들어 출력하기 때문에 입력 값과 출력 값을 1대1로 매핑할 수 있다.
처음에 쓴 답
1. 해시 함수를 통해 만들어진 출력 값은 원래의 입력 값으로 되돌릴 수 없다.
2. 해시 테이블은 내부적으로 SHA-256 해시 함수를 사용한다.
1, 2번을 쓴 이유: 해시 함수를 통해 만들어진 출력 값을 1이라고 가정했을 때, 이것은 인덱스 값이고, 고유한 값으로 만들 수 없기 때문에 맞다고 생각을 했다. 그렇지만 인덱스에 1을 넣게 되면 기존에 유지한 출력 값을 테이블에서 고대로 가지고 올 수 있음. SHA-256 해시 함수가 뭔지 궁금해서 찾아봤는데, 옛날에는 좀 썼지만 지금은 안 쓴다고 해서 골랐다.
3, 4번이 정답인 이유: SHA-256은 정보를 암호화하는 함수이다. 테이블은 요즈음엔 보통 쉽게 쓰인다고 한다. SHA-256까지 가지 않아도 충분히... 그리고 정보를 암호화할 땐 다른 것을 쓴다고 했는데, 조금 더 배워야 알 것 같다. 또, 해시 함수는 어떠한 값이 들어왔을 때 값으로 출력은 가능하지만 고유한 값으로 만들어 출력하 수 없다. 문자열은 무궁무진하지만 해시 함수의 출력 값은 정해져 있기 때문이다. 그렇지만 출력 값과 입력 값을 1대 1로 매핑할 수는 있다. 객체와 키로 저장하기 때문이다.
- 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")2번
처음에 쓴 답: 3번
3번을 쓴 이유: 하단의 3개의 인서트에 들어가는 키의 값이 같았기 때문.
2번이 정답인 이유: 충돌은 2번 일어난다.
heigth 인서트 -> 성공적
weigth 인서트 -> 해시 충돌 1번
mobile 인서트 -> 해시 충돌 2번
제발 꼼꼼하게 봅시다.
