터틀넥 스튜디오

🤔 면접 질문 Q1. Hash table에서 collision이 발생하면 어떻게 되나요? 해결방법엔 뭐가 있을까요? A1. collision이 발생할 경우 대표적으로 2가지 방법으로 해결합니다. 첫 번째, open addressing 방식은 collision이 발생하면 미리 정한 규칙에 따라 hash table의 비어있는 slot을 찾습니다. 빈 slot을 찾는 방법에 따라 크게 Linear Probing, Quadratic Probing, Double Hashing으로 나뉩니다. 두 번째, separete chaining 방식은 linked list를 이용합니다. 만약에 collision이 발생하면 linked list에 노드(slot)를 추가하여 데이터를 저장합니다. 💡 면접🐕🍯 tip 정말 자주나오..

🤔 면접 질문 Q1. Hash Table는 어떤 자료구조인가요? A1. hash table은 효율적인 탐색(빠른 탐색)을 위한 자료구조로써 key-value쌍의 데이터를 입력받습니다. hash function h에 key값을 입력으로 넣어 얻은 해시값 h(k)를 위치로 지정하여 key- value 데이터 쌍을 저장합니다. 저장, 삭제, 검색의 시간 복잡도는 모두 O(1)입니다. 💡 면접🐕🍯 tip CS 면접에서 가장 자주 나오는 질문중에 하나다. Hash table이 면접 단골질문인 이유는 다음과 같다. ☝ 실무에서도 활용도가 높은 자료구조다. ✌ Linked list, Array 더 나아가면 Tree까지 질문할 수 있다. 🤟시간복잡도에 대해서 물어보기 좋다. 한편, 좋은 hash function의 조건..

🤔 면접 질문 Q1. BST는 어떤 자료구조 인가요? A1. 이진탐색트리(Binary Search Tree; BST)는 정렬된 tree입니다. 어느 node를 선택하든 해당 node의 left subtree에는 그 node의 값보다 작은 값들을 지닌 node들로만 이루어져 있고, node의 right subtree에는 그 node의 값보다 큰 값들을 지닌 node들로만 이루어져 있는 binary tree입니다. 검색과 저장, 삭제의 시간 복잡도는 모두 O(logn)이고, worst case는 한쪽으로 치우친 tree가 됐을 때 O(n)입니다. 💡 면접🐕🍯 tip BST는 저장과 동시에 정렬을 하는 자료구조이다. 따라서 새로운 데이터를 저장할 때 일정한 규칙에 따라 저장을 하게 된다. Heap을 공부했었을..

🤔 면접 질문 Q1. Queue vs priority queue를 비교하여 설명해 주세요 A1. Queue 자료구조는 시간 순서상 먼저 집어 넣은 데이터가 먼저 나오는 선입선출 FIFO(First In First Out) 구조로 저장하는 형식입니다. 이와 다르게 우선 순위 큐(priority queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나옵니다. Queue의 operation의 시간복잡도는 enqueue = O(1), dequeue = O(1)이고, Priority queue는 push = O(logn), pop = O(logn)입니다. 💡 면접🐕🍯 tip : 면접질문에서 '우선 순위 큐'를 잘 답하기 위해서는 구현 방법과 operation의 시간 복잡도를 잘 설명할 수 있어야 한..

🤔 면접 질문 Q1. Queue 두 개를 이용하여 Stack을 구현해 보세요 A1. 편의상 push()에 사용할 queue는 q1이라 부르고 pop()에 사용할 queue는 q2라 명명하겠습니다. 두 개의 queue로 stack을 구현하는 방법은 다음과 같습니다. 1. push() : q1으로 enqueue()를 하여 데이터를 저장합니다. 2. pop() a. q1에 저장된 데이터의 갯수가 1 이하로 남을 때까지 dequeue()를 한 후, 추출된 데이터를 q2에 enqueue()합니다. 결과적으로 가장 최근에 들어온 데이터를 제외한 모든 데이터는 q2로 옮겨집니다. b. q1에 남아 있는 하나의 데이터를 dequeue()해서 최근에 저장된 데이터를 반환합니다.(=LIFO) c. 다음에 진행될 pop()..

🤔 면접 질문 Q1. Stack 두 개를 이용하여 Queue를 구현해 보세요 A1. queue의 enqueue()를 구현할 때 첫 번째 stack을 사용하고, dequeue()를 구현할 때 두 번째 stack을 사용하면 queue를 구현할 수 있습니다. 편의상 enqueue()에 사용할 스택을 instack이라 부르고, dequeue에 사용할 stack을 outstack이라 명명하겠습니다. 이 두 개의 stack으로 queue를 구현하는 방법을 설명드리겠습니다. 1. enqueeue() : instack에 push()를 하여 데이터를 저장합니다. 2. dequeue() a. 만약 outstack이 비어 있다면 instack.pop()을 하고, outstack.push()를 하여 instack에서 outs..

🤔 면접 질문 Q1. Stack는 어떤 자료구조인가요? A1. Stack은 후입선출 LIFO(Last In First Out)의 자료구조입니다. 시간 복잡도는 push O(1), pop O(1)입니다. 활용 예시는 후위 표기법 연산, 괄호 유효성 검사, 웹 브라우저 방문기록(뒤로가기), 깊이 우선 탐색(DFS) 등이 있습니다. 💡 면접🐕🍯 tip : 코딩테스트에서는 stack이 굉장히 중요한 자료구조이지만, 면접에서는 stack을 단독으로 질문하는 경우는 많이 없다. 따라서 Queue의 FIFO와 대조되는 LIFO라는 특성과, 활용예시 정도의 기본적인 내용만 이해하고 가면 충분하다. 1️⃣ LIFO Stack은 시간 순서상 가장 최근에 추가한 데이터가 가장 먼저 나오는 후입선출(LIFO = Last In..

🤔 면접 질문 Q1. Queue는 어떤 자료구조인가요? A1. Queue는 선입선출 FIFO(First In First Out)의 자료구조입니다. 시간 복잡도는 enqueue O(1), dequeue O(1)입니다. 활용 예시는 Cache 구현, 프로세스 관리, 너비우선탐색(BFS) 등이 있습니다. 💡 면접🐕🍯 tip : Queue는 기초적인 자료구조로 면접에서 간단한 질문으로 종종 나오는 문제이다. LIFO인 stack과 다르게 FIFO 자료구조임을 잘 기억하고 있으면 된다. 또한, 활용 예시들과 Circular Queue 자료구조를 잘 숙지하고 있다면 면접에서 충분한 답을 할 수 있을 것이다. 1️⃣ FIFO Queue는 시간 순서상 먼저 집어 넣은 데이터가 먼저 나오는 선입선출 FIFO(First ..

🤔 면접 질문 Q1. Array와 Linked list를 비교해서 설명해주세요. A1. Array는 메모리 상에서 연속적으로 데이터를 저장하는 자료구조입니다. 반면 Linked list는 메모리상에서는 연속적이지 않지만, 각각의 원소가 다음 원소의 메모리 주소값을 저장해 놓음으로써 논리적 연속성을 유지합니다. 그래서 각 operation의 시간 복잡도의 차이가 있습니다. 데이터 조회는 Array의 경우 O(1), Linked list는 O(n)의 시간 복잡도를 갖습니다. 삽입/삭제의 경우 Array는 O(n), Linked list는 O(1)의 시간 복잡도를 갖습니다. 💡 면접🐕🍯 tip : Array와 Linked list의 주된 차이점들은 메모리 구조에 기인한다. Array는 메모리상에서 연속적으로 ..

🤔 면접 질문 Q1. Linked List에 대해서 설명해주세요. A1. Linked List는 Node라는 구조체로 이루어져 있는데, Node는 데이터 값과 다음 Node의 address(주소)를 저장합니다. Linked List는 물리적인 메모리상에서는 비연속적으로 저장이 되지만 Linked List를 구성하는 각각의 Node가 next Node의 address를 가리킴으로써 논리적인 연속성을 가진 자료구조입니다. 💡 면접 tip : Linked List는 tree, graph등 다른 자료구조를 구현할 때 자주 쓰이는 기본 자료구조이다. 면접에서 Linked List를 설명할 때에는 메모리상에서 불연속적으로 데이터가 저장되는 점과 Node의 Next address를 통해 불연속적인 데이터를 연결하여 ..