오답노트

프최's log·2020년 9월 4일

study

목록 보기

6/59

1.스택/큐

스택에 대한 설명 중 틀린 것을 모두 고르면?

A. 먼저 들어간게 나중에 나오는 First In Last Out 구조이다.
B. 먼저 들어간게 먼저 나오는 First In First Out 구조이다.
C. top 메서드는 스택의 맨 위에 있는 값을 꺼내고, 해당 값을 반환한다.
D. 스택에 할당된 공간이 꽉 차면 더이상 push 할 수 없다.
E. 재귀 함수를 실행할 때 사용된다

1번 문제는 스택에 대해 LIFO만 생각하고 있다가 덜렁거리면서 막 눌렀던 문제로 기억한다. ㅎ...ㅎ; 그래서 더 우왕좌왕하면서 풀이도 제대로 못했던 문제. 다시한번 반성!

오답 선택 이유
- A : LIFO만 생각하고, FILO는 잘못 되었다고 선택했다.(ㅎ..) 스택은 먼저 들어간게 나중에 나오는 구조로 후입선출이다.
  고로, B는 자동적으로 아니게 되며, B의 설명은 'Queue'에 대한 설명이다.
- D : 스택에 할당된 공간이 꽉 차면 stackoverflow를 생각해서 넘치니까 안 들어간다고 생각했다. 이 경우, 추가 할당이 메모리의 다른 섹션으로 넘어가 진행된다는 글을 발견했고(https://boycoding.tistory.com/235) push를 할 수 없는 건 아니다라는 결론!
답 풀이(optional)
- C : top메서드(스프린트에서의 pop)은 top이 가리키는 자료를 삭제시키므로 반환하지 않는다.

B,C

다음과 같은 코드의 실행 결과는?

function calc(expression) {
// 1. 문자를 하나씩 검사한다.
// 2. 숫자를 만나면 숫자를 스택에 푸시한다.
// 3. 연산자를 만나면 스택에서 팝을 두 번 하고, 두 개의 숫자를 가지고 연산한다.
// 4. 3의 연산 결과를 다시 스택에 푸시한다.
// 5. 문자열이 끝날 때 까지 반복한다.
// 6. 문자열이 끝나면 연산 결과 값을 리턴한다.
}
const result = calc("9 3 * 15 5 / + 2 -")
console.log(result);

A. 20
B. 28
C. 32
D. 34
E. 45

오답 선택 이유
- D : 수도 코드 해석을 잘못 했다. 두개의 숫자를 가지고 연산을 할 때, 만나는 연산자를 쓴다고 생각을 안 하고 더하기만 했다.(바보인가)
답 풀이(optional)
1.숫자 9,3을 만나서 스택에 저장
2. 연산자 를 만나 93이 진행되고 스택에 27 저장
3. 숫자 15,5를 만나서 스택에 저장 // 현재 스택에 27, 15, 5 저장 중
4. 연산자 / 를 만나서 15/5를 진행되고 스택에 3 저장 // 현재 스택에 27, 3 저장 중
5. 연산자 + 를 만나서 27+3이 진행되고 스택에 30 저장 // 현재 스택에 30 저장 중
6. 숫자 2를 만나서 스택에 저장 // 현재 스택에 30, 2 저장 중
7. 연산자 - 를 만나서 30-2가 진행되어 스택에 28 저장
8. 문자열 검사가 끝나서 최종 연산결과인 28이 리턴된다.

B. 28

큐에 대한 설명 중 틀린 것을 모두 고르면?

A 먼저 들어간게 먼저 나오는 First In First Out 구조이다.
B 먼저 들어간게 나중에 나오는 First In Last Out 구조이다.
C dequeue는 큐의 가장 앞에 있는 값을 꺼내서 반환한다.
D rear는 큐의 마지막 값의 인덱스를 가리킨다.
E 하노이의 탑의 구조는 큐와 유사하다

여기서 정답 1개만 선택하고 다른 걸 고르지 않았다.

답 풀이(optional)
- B : 큐는 선입선출(FIFO)구조인 A가 정답이기 때문에 B가 틀렸다.
- E : 하노이의 탑 구조는 스택과 유사하다.

B,E

2.연결리스트/해시테이블

연결리스트의 요소는 메모리에 연속적으로 할당될 수 있다.

A 참
B 거짓

답 풀이(optional)
동적으로 수시로 할당되므로 연속적으로 나열되어있으면 가능하다.

A 참

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

A : 연결 리스트는 특정 인덱스의 노드를 찾을 때 배열보다 빠르다는 장점이 있다.
B : 단일 연결 리스트에서 각 노드는 자신의 이전 노드를 알 수 없다.
C : 연결 리스트는 반드시 리스트의 끝(tail)에만 노드를 추가해야 한다.
D : 배열보다 메모리를 더 효율적으로 사용할 수 있는 자료구조이다.
E : 이중 연결 리스트는 하나의 값을 저장하기 위해 2개의 노드가 필요하다.

답 풀이(optional)
A : 연결리스트에는 인덱스가 없고 메모리 주소를 통해 찾아가기 때문에 배열보다 느리다.
B : 단일 연결 리스트에서는 이후 노드를 알 수 있다. 고로 이전 노드 정보는 알 수 없다.
C : 연결리스트는 리스트의 시작(head)뿐만 아니라 중간에서도 추가할 수 있다.
D : 삽입.제거가 많은 작업에 효율적이다.O(1), 메모리 랜덤접근이 많은 작업에 있어서는 배열이 효율적(O(n))
E : 여기서 초점은 '노드', 맨처음에 '포인터'를 헷갈려서 틀릴 뻔 했다. 이중 연결 리스트는 1개의 노드를 가지며, 2개의 포인터(이전 노드 정보, 이후 노드 정보)를 지닌다.

B,D

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

A : 1
B : 2
C : 3
D : 4
E : 5

답 풀이(optional)
답 선택할 때는 단순하게, 헤드를 지우면 나머지 애들이 연결된 상태니 자연스럽게 딸려와서 모두 삭제 된다고 생각했는데 체크 포인트 시간에서 조금 더 자세한 설명을 들을 수 있었다.
헤드(포인터=표지판)를 끊어버리면 나머지 자료들을 접근하지 못해서 삭제하는 효과가 나타난다. → 가비지 컬렉터가 알아서 삭제(가비지 컬렉터 작동 기준점은 노드가 더이상 사용되지 않을 때 삭제된다고 한다.)
- 가비지 컬렉터 : 메모리 자원관리 + 사용되지 않는 메모리 추적

A

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

오답 선택 이유 & 답 풀이
8번이라고 썼는데, 사실 이중 연결 리스트의 탐색 방법에 대해 생각해보지 못 했다. 검색해서 알아보니 탐색방법은 연결리스트와 동일하다. 탐색방향이 일편적이고 순차적으로 노드의 수를 세어나간다. 고로 단일 연결 리스트와 동일하게 10번의 검색을 한다.

10번

데이터의 값이 아래와 같이 저장된 연결 리스트가 있다.

(head) 1 - 2 - 3 - 4 - 5 - 6 (tail)

alternatePrint(head)의 결과로 적합한 것은?

function alternatePrint(node) {
   if (node == null) {
     return;
   }
   console.log(node.data);
  if (node.next) {
     alternatePrint(node.next.next);
   }
   console.log(node.data);
 }

A : 1 - 3 - 5
B : 2 - 4 - 6
C : 2 - 4 - 6 - 6 - 4 - 2
D : 1 - 3 - 5 - 5 - 3 - 1
→ 콜스택 개념
E : 1 - 2 - 3 - 4 - 5 - 6

오답 선택 이유
- A : alternatePrint(node.next.next) 까지는 이해를 했는데 마지막 console.log 는 대체 무엇일까 고민하긴 했다. 그래서 D인가? 했지만 설마하고 A를 선택했더니 오답이었다.
답 풀이(optional)
최초 노드 1 이 찍힌 후, 1 밑에 next 값이 있으니 재귀로 들어간다. 이 때 값은 1의 다음다음 값인 '3'이 들어가게 되고, 3 또한 next를 갖고 있다. 재귀함수가 가져가는 그 값은 바로 '5'. 그래서 1-3-5 까지 나온 후, 더이상 들어갈 수 없으니 함수가 종료되고 갖고 있던 값을 다시 반환한다. 콜스택 개념이 적용 이다. 5-3-1 순으로 반환이 진행되고, 최종적으로 1-3-5-5-3-1이 결과값이 되는 원리이다.

D

해시 테이블과 해시 함수에 대한 설명으로 반드시 참인 것을 모두 고르면?

A. 두 개 이상의 값에 하나의 키를 사용할 수 없다.
B. 키와 값을 한 쌍으로 저장할 수 있는 자료구조이다.
C. 해시 함수는 어떤 값이 들어오더라도 고유한 값으로 만들어 출력하기 때문에 입력 값과 출력 값을 1대1로 매핑할 수 있다.
D. 해시 테이블은 내부적으로 SHA-256 해시 함수를 사용한다.
E. 해시 함수를 통해 얻은 출력 값을 통해 입력을 생성할 수 있다.
→ 입력값을 알 수 없다.

오답 선택 이유
- C : 입력값과 출력값이 1:1 매핑된다고 어디서 봤던 기억이 있어서 선택했는데 오답이라서 사실 이건 좀 더 찾아볼 예정이다. 해시 충돌이 일어난다고 해서 오답..
  → 오늘 오피스아워에서 궁금증이 조금 해결되었다. 서로 다른 문자열이 해시함수를 통해 Hash 한 결과가 같은 경우, 즉 중복되는 경우도 발생할 수 있다는 결론. 고로 좋은 해시함수를 써야한다.
- D : 구글링으로 쳐서 SHA-256을 활용했다는 글이 보여서 선택했다(하..) 해시 테이블은 다른 해쉬함수도 사용용할 수 있다. 나눗셈법 = Division Method ( 입력값 % 테이블크기 ), 자릿수 접기= Digit Folding (숫자의 각 자릿수를 더해 만드는 것 = 아스키코드 값의 합) 등등..참조사이트(https://luyin.tistory.com/191)
추가 답 풀이(optional)
A. 두 개 이상의 값에 하나의 키를 사용할 수 없다.
→ 키와 값을 반대로 착각하고 해석해서 선택을 안 했던 답.. 하나의 키는 한 개의 값을 갖는다.
B. 키와 값을 한 쌍으로 저장할 수 있는 자료구조이다.
E. 해시 함수를 통해 얻은 출력 값을 통해 입력을 생성할 수 있다.
→ 입력값을 알 수 없다.(수학적으로는 가능하다고 한다)

A,B

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

A라는 해시 함수를 이용한다고 기재되어 있었는데 엉뚱한 생각을 하고 풀었다.(...) 하단 코드에 대한 오답 노트는 소스에다가 주석으로 풀이를 적었다.

function A(key) {
  return key.length % 5; // → 마지막에 키의 길이가 동일한 값이 2번 들어와서 충돌이 생김.
}

const hashTable = new HashTable();
hashTable.insert("name", "kim") // 4
hashTable.insert("age", 22) // 3
hashTable.insert("height", 177) // 1
hashTable.insert("weight", 65) // 1 → height이 이미 쓰고 있음.
hashTable.insert("mobile", "010-9191-2929") // 1  → height이 이미 쓰고 있음.