새삼 너무 감격스러워서 / Kahoot 복습 (자료 구조)

 

오늘 수업 때 했던 퀴즈에서 3등/15 을 했다.

별 거 아닐 수 있지만 나 스스로는 너무 감격해서 내 이름이 나왔을 때 셀피를 찍고 싶었지만

조용히 등수만 스크린샷을 찍었다.

 

그것도.

이머시브 과정 중에 가장 어렵다고 하는 hash table이 포함된 퀴즈에서!

 

열심히 공부했는데 보람이 있었다.

11시에 애기 재우고 새벽 공부를 한 보람이.

 

퀴즈 하나가 전부를 의미하는 건 아니지만, 꽤 큰 의미였다.

또 열심히 해 봐야지.

 

 

 

< linked list, hash table 에 관한 질문 및 답변 >

 

• JavaScript 공부할 때 mdn공식 문서를 보았던 것처럼 Data Structure에 관한 공식 문서는 없나요?

     -> 네. 코드스테이츠 강의 내용 외에는 유튜브 같은 데를 참고해 보세요.

         많이 본다고 좋은 건 아니고 어떤 부분을 모르는지 질문 내용을 특정해서 검색해 볼 것을 추천해드립니다.

 

 

• 배열이나 객체와는 달리 linked list 나 hash table 등 자료구조들은 참고하는 문서들마다 언급하는 속성이나 메서드가 조금씩 다릅니다.

     -> 그렇습니다. 과제에서 나왔던 내용들 위주로 알면 될 것 같습니다.

 

 

• peek 와 top 이 같은 의미로 쓰이는 것 같은데 두 가지 용어가 있는 이유가 뭔가요? 다른 건가요?

     -> 사실 같은 역할을 한다.

 

 

 

 

< Kahoot 퀴즈 내용 복습 >

 

• top 값은 맨 위에 위치한 데이터의 index 값으로 값을 꺼내(삭제하)지는 않는다.
• 스택에 할당된 공간이 꽉 차면 더 이상 push할 수 없으므로 stack overflow 상태가 된다.

 

 

 

 

 

 

 

• A,E,C,F,D 를 차례대로 넣은 후 top값을 두 번 삭제하면 A,E,C 만 남게 됨.
• top 값을 조회하는 peek는 C, stack의 사이즈는 3이 된다.

 

 

 

 

• 하노이의 탑의 구조는 오히려 가장 마지막에 삽입된 것이 먼저 나오게 되는 stack과 유사하다.

 

 

 

 

 

 

• front부터 rear의 갯수를 세면 (6-2) +1 = 5

 

 

 

 

 

• 예를 들어 index 3의 값을 찾는다고 가정하면 배열의 경우 한 번에 찾을 수 있지만 linked list의 경우 두 번의 연산을 더 거쳐야 한다.
  • 보통 index 만큼의 연산을 하므로 배열보다 오래 걸리게 된다.
• 단일 연결 리스트는 한 방향으로 next 속성만 가지므로 이전 노드를 알 수 없다.
• 필요한 곳 어디에나 노드를 추가할 수 있다는 점이 linked list의 장점 중 하나이다.
• 이중 연결 리스트에서 하나의 값을 저장하기 위해 필요한 것은 2개의 레퍼런스이다. (next, previous)

 

 

 

 

 

• 노드를 삭제한다는 것은 노드의 연결을 끊는 것을 의미한다. 따라서 가장 앞에서 한 번 끊으면 이후 모든 노드의 연결이 끊어진다.

 

 

 

 

 

• 최악의 경우 가장 마지막에 찾는 값이 있다고 가정하므로 최대 10번까지 검색이 필요하다.

 

 

 

 

 

 

 

• 해시 함수는 항상 고유한 값을 만들어서 1:1로 매핑하는 것이 아니라 같은 출력값이 생기면 충돌을 일으킨다.
• 해시 함수를 통해 만들어진 출력은 원래의 입력 값으로 되돌릴 수 없다는 특징 때문에 비밀번호 저장 등에 사용된다.

 

 

 

 

 

 

 

• 해시 테이블에 값을 삽입할 때 apple 이라는 키를 두 번 넣으면 마지막에 넣은 값으로 덮어 씌우게 된다.

 

 

 

 

 

 

 

• 위 해시 함수는 키를 입력 받아서 키의 길이를 반환하는 함수이다.
• name, age, height, weight, mobile 이라는 키를 차례로 넣으면 4,3,5,5,5 라는 해시값을 리턴하게 된다.
• 즉, height까지는 이전값과 같지 않으므로 문제가 없지만 weight를 입력할 때, mobile을 입력할 때 충돌이 2번 일어나게 된다.