체크 포인트 [Data Structure Part II]

dlrbwls0302·2021년 1월 22일
0

1번 문제

해설

배열에 요소를 추가하는 경우 메모리에 연속적으로 할당할 수 있기 때문에 우리가 각각의 변수에 접근하는게 편하다. 하지만 연결 리스트의 노드들은 메모리에 랜덤으로 할당되기 때문에 항상 연속적이라고는 할 수 없다. 아주 낮은 확률이지만 랜덤으로 할당된 노드들이 메모리 상에서 연속적으로 존재할 수는 있기 때문에 1번 문제의 답은 '참'이다.

배열 같은 경우에는 첫 번째 요소의 주소에 4를 더하면 두 번째 요소의 주소로 이동하고 거기에 4를 더하면 세 번째 요소의 주소로 이동할 수 있기 때문에 각각의 변수에 접근하는 것이 편하다.

위 그림을 메모리 공간이라고 하고 흰 색은 연결 리스트의 노드들이 저장된 곳, 빨간 색을 저장되지 않은 곳이라고 생각해보자. 연속적이지 않기 때문에 1 -> 2는 바로 다음이라 큰 문제가 없지만 2 -> 4는 중간에 3이 가로막고 있기 때문에 가는데 어려움이 있다. 따라서 자바스크립트 외에 다른 언어에서는 '포인터'라는 개념이 있는데 이는 그 다음 변수를 가리키는 것이다. 즉 2 -> 4를 가는데 3이 가로 막고 있지만 포인터로 4를 가리키면 2 -> 4를 가는데 문제가 없다는 것이다.


2번 문제

해설

A는 틀린 답이다. 위에 1번 문제의 해설에서 봤듯이 배열 같은 경우는 첫 번째 요소의 주소에 4를 더하면 두 번째 요소의 주소이기 때문에 각각의 변수에 더 빨리 접근할 수 있고 따라서 더 빨리 찾을 수 있기 때문에 A는 틀렸다고 볼 수 있다.

B가 정답인 이유는 단일 연결 리스트의 경우 아래 그림처럼 next를 통해서 head부터 tail까지 한 방향으로만 접근이 가능하기 때문이다. 각 노드는 자신의 다음 노드에 대해서만 알 뿐이지 자신의 이전 노드는 전혀 관심이 없다. 따라서 한 번 지나쳐 버리면 다시 돌아갈 수 없기 때문에 만약 내가 원하는 노드를 지나쳤다면 다시 head로 돌아가서 원하는 노드를 찾아야 한다.

C가 틀린 이유는 연결 리스트를 굳이 tail에서 추가할 필요없이 중간에도 추가할 수 있기 때문이다.

D가 정답인 이유는 연결 리스트를 사용하는 가장 큰 이유이기 때문이다. 연결 리스트는 배열보다 메모리를 좀 더 효율적으로 사용하기 위해 생겨난 개념이다.

E가 틀린 이유는 이중 연결 리스트가 하나의 값을 저장하기 위해서는 한 개의 노드밖에 필요가 없기 때문이다.

이렇게 각각의 노드가 prev과 next를 이용해 전의 노드, 후의 노드를 저장할 수 있기 때문에 굳이 두 개를 만들 필요가 없다.


3번 문제

해설

가장 앞의 노드(head)와 그 뒤의 노드의 연결을 끊어버리면 자동으로 모든 노드가 삭제된다.


4번 문제

해설

순서대로 5 -> 10 -> 15 -> 20인 연결 리스트가 만들어지는데 0번째 인덱스의 연결 리스트를 제거하면 10 -> 15 -> 20이 되고 인덱스도 순서대로 0이 10, 1이 15, 2는 20을 가리키게 된다. 여기서 다시 2번째 인덱스를 삭제하면 20이므로
10 -> 15인 연결 리스트가 된다. 여기서 1번째 인덱스는 15이므로 답은 15가 된다.


5번 문제

해설

위 그림은 이중 연결 리스트이다. 단일 연결 리스트와 마찬가지로 원하는 값을 찾기 위해서는 head부터 차례대로 쭉 훑어나가야 한다. 이것이 연결 리스트의 단점이다. 원하는 노드를 찾기 불편하고 하나를 찾으려고 해도 처음부터 순회하는 식으로 해야하기 때문에 대단히 비효율적이다. 만약 10개의 노드가 연결된 이중 연결 리스트라면 최대 10번의 검색이 필요하다.


6번 문제

해설

alternatePrint의 함수에 차례로 1, 3, 5가 들어가고 console.log에 의해서 1, 3, 5가 나온다. 그러고 나서 5의 다음 다음 숫자는 null이기 때문에 return을 하고 종료를 한다. 그리고 console.log에 의해서 다시 5, 3, 1이 찍혀 D처럼 1 - 3 - 5 - 5 - 3 - 1이 된다.


7번 문제

해설

A가 정답인 이유는 해시 테이블에 존재하는 한 개의 데이터는 한 쌍의 키와 값으로 되어있기 때문이다. 따라서 두 개 이상의 값에 하나의 키를 사용할 수 없다. 만약 키가 한 개인데 값이 두 개 이상이면 사용자가 키를 검색할 때 마다 두 개의 값이 반환되기 사용에 어려움이 있다.

B는 아까 말했듯이 해시 테이블에 저장된 데이터는 한 쌍의 키와 값으로 되어있다.

C가 틀린 이유는 해시 함수를 통해서는 항상 고유한 값이 생기지 못하기 때문이다. 만약 A라는 키와 B라는 키를 해시 함수를 돌렸는데도 같은 값이 나오는 경우를 '해시 값이 충돌했다' 라고 표현한다. 해시 함수를 이용하더라도 겹치는 부분(충돌)이 생기기 때문에 1대1 매핑은 할 수 없고 그 대신 체이닝(분리 연결법) 방식을 써서 같은 주소에 여러 데이터를 줄줄이 엮는 식으로 저장할 수 있다.

위 그림에서 보면 John Smith라는 키와 Sandra Dee라는 키를 해시 함수에 넣었더니 152라는 같은 값을 받게 된 것을 볼 수 있다. 그러면 152라는 주소에 John Smith라는 키와 521-1234라는 값을 저장하고 그 다음 데이터인 Sandra Dee라는 키와 521-9655라는 값을 저장하고 둘을 체인으로 연결해 줌으로서 152라는 주소에 일렬로 저장된 것을 볼 수 있다. 체이닝 방식의 장점은 해시 테이블의 확장이 필요없고 간단하게 구현할 수 있으며 손쉽게 삭제할 수 있다는 점이다.

D가 틀린 이유는 SHA-256이 2^256만큼의 경우의 수를 만들어서 저장하는데 꼭 모든 해시 테이블이 SHA-256을 이용한다고 생각하지 않는다. SHA-256은 블록 체인에서 가장 많이 사용한다고 한다.

E가 틀렸다고 보는 이유는 해시 함수를 통해 얻은 출력 값은 해시 테이블 안에서 어디 주소로 저장될지 알려주는 주소일 뿐이지 이를 통해 입력을 생성하는 것은 금시초문이여서 틀린 답이라고 생각한다.


8번 문제

해설

해시 테이블에 어떤 키와 값을 저장했는데 새로 들어온 데이터가 같은 키를 가지고 있다면 기존의 저장된 값은 새로운 값으로 덮어 씌워지게 된다. 문제에서 'apple'이라는 키에는 'I love apple'이라는 값이 저장된 것을 알 수 있다. 그런데 또 다시 'apple'이라는 키와 'I need a macbook pro'라는 값이 들어온 것을 알 수 있다. 따라서 'I love apple' -> 'I need a macbook pro'로 값이 바뀌게 된다.


9번 문제

해설

키의 길이에 따라 해시 함수의 출력 값이 달라지는 것을 알 수 있다. 키의 길이가 같은 것들은 같은 출력 값을 갖게되기 때문에 충돌할 수 밖에 없다. 'height', 'weight'와 'mobile'은 전부 길이가 6이다. 이 셋의 해시 함수의 출력 값은 같기 때문에 충돌할 수 밖에 없다. 따라서 'height'와 'weight'가 한 번 충돌하고 'weight'와 'mobile'이 충돌해서 답은 C인 총 두 번의 충돌이 발생한다.

profile
오늘의 공부가 쌓여서 내일의 나를 만들어낸다.

관심 있을 만한 포스트

0개의 댓글