2021.12.10 면접 질문 준비 - Part 1. 전산 기초 자료구조

• Array vs Linked List
  • Array는 크기가 고정되어 있으며, 요소들을 인덱스를 통해 바로 접근할 수 있기 때문에 접근할 때 시간 복잡도는 O(1)입니다
    또한 삽입이나 삭제를 할 때 빈 자리 이후의 원소들이 자리를 채워야 하기 때문에 시간복잡도는 O(N) 입니다
    반면 LinkedList는 크기가 고정되어있지 않으며, 요소를 접근할 때 순차적으로 검색하며 찾아야하기 때문에 시간복잡도는 O(N)입니다
    또한 삽입이나 삭제를 할 때 새로운 요소에 할당된 메모리 위치 주소가 LinkedList의 이전 요소에 저장되기 때문에 시간복잡도는 O(1)입니다
  • https://velog.io/@humblechoi/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Array-vs-LinkedList
    https://do-rang.tistory.com/25
    
    
• LinkedList
  • LinkedList는 한 노드에 데이터, 다음노드주소값이 담겨있고, 노드끼리 순차적으로 연결되어있는 방식의 자료구조 입니다
    LinkedList는 크기가 고정되어있지 않아서 삽입이나 삭제가 편리합니다
    또한 필요할 때마다 크기를 변경할 수 있어 메모리의 낭비를 줄일 수 있습니다
    하지만 탐색하는 속도가 느립니다
    탐색할 때마다 0번째 인덱스에서 시작해서 원하는 인덱스까지 순차적으로 이동해야하기 때문입니다
  • https://do-rang.tistory.com/25
    
    
• Stack and Queue
  • 스택은 LIFO의 자료구조를 구현한 클래스로, 나중에 넣은 객체가 먼저 빠져나가는 자료구조입니다
    한편 큐는 FIFO의 자료구조를 구현한 인터페이스로, 먼저 넣은 객체가 먼저 빠져나가는 자료구조입니다
  • 활용예시 : 
    큐 - 프린터, 콜센터, 은행업무, 주문
    스택 - 브라우저뒤로가기, 되돌리기,
  • https://techhan.github.io/study/interview-01/
    https://devuna.tistory.com/22
    
    
• Tree
  
  • 트리는 비선형 자료구조 중 하나로, 나무가 나뭇가지를 가져 뻗어나가는 형태의 알고리즘이다. 
    데이터 하나의 단위를 노드라고 하는데, 한 노드는 여러개의 자식 노드를 가질 수 있으며, 그 자식 노드 또한 여러개의 자식 노드들을 가질 수 있다
  • 정의 - 특징 - 활용예시 흐름으로 설명하자
  • 비선형 자료구조..왜?
    • 선형 -배열 링크드리스트
      그 외에는 비선형구조
  • https://readerr.tistory.com/50 
    
    
• Binary Heap
  • Binary Heap이란 최대 또는 최소를 빠르게 찾아내기 위해 만들어진 완전이진트리(CBT)로써 부모노드와 자식 노드간에 대소 관계가 성립합니다. 
    이러한 대소 관계를 기반으로 Heap은 Max Heap과 Min Heap으로 나눌 수 있습니다. MaxHeap은 루트노드의 값이 가장 크고, 부모가 자식보다 값이 큰 구조를 가지고 있습니다. 
    Min Heap은 루트노드의 값이 가장 작고, 부모가 자식보다 값이 작은 구조를 가지고 있습니다.
  • 완전이진트리 만족 조건?
    • 부모노드에 대한 자식노드는 마지막 레벨의 부모노드를 제외하고 모두 2개
  • https://imbf.github.io/interview/2021/03/03/NAVER-Practical-Interview-Preparation-5.html
    
    
• Hash Table
  • 해시테이블은 효율적인 탐색을 위한 자료구조로 key값을 value에 대응시킵니다. 해시테이블을 구현하기 위해서는 연결 리스트와 해쉬 함수가 필요합니다.  
    해싱은 임의의 길이의 값을 해쉬 함수를 통해 고정된 크기의 값으로 변환하는 작업을 말하는데, 키 값을 해시 코드로 변환한 후 해당 해시 코드로 배열의 인덱스를 참조하여 값을 찾습니다.
    충돌이 발생할 수 있으며, 최악의 경우 O(N), 일반적으로 잘 구현된 경우는 O(1)의 시간 복잡도를 가지게 됩니다. 충돌은 Chaining, Open addressing 등의 방식으로 해결할 수 있습니다.
  • Chaining이란?
    • 같은갑이 발생하면 다시한번 키밸류로 나눈다
  • https://velog.io/@humblechoi/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EB%A9%B4%EC%A0%91%EC%A7%88%EB%AC%B8-%EB%AA%A8%EC%9D%8C
    
    
• Graph
  • 그래프는 실제 세계의 현상이나 사물을 정점 또는 노드와 간선으로 표현하기 위해 사용하는 것입니다
    그래프는 루트노드가 없고 부모/자식 관계가 존재하지 않습니다
    종류는 방향성에 대한 방향그래프, 무방향그래프가 있고
    사이클에 대한 순환 그래프, 비순환 그래프가 있습니다.
  • 트리랑 잠깐 비교 - 종류 -이에 대한 설명 - 탐색 종류 - 이에대한 설명 흐름으로
  • https://velog.io/@bbkyoo/%EB%A9%B4%EC%A0%91%EC%A4%80%EB%B9%84%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%9813%EA%B7%B8%EB%9E%98%ED%94%84-%EC%9D%B4%ED%95%B4#1-%EA%B7%B8%EB%9E%98%ED%94%84-graph-%EB%9E%80

 

 

 

 

 

질문 출처 :https://github.com/iamzin/Interview-Question-for-Beginner