터틀넥 스튜디오

🤔 면접 질문 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를 통해 불연속적인 데이터를 연결하여 ..

🤔 면접 질문 Q1. Dynamic Array는 어떤 자료구조인가요? A1. Array의 경우 size가 고정되었기 때문에 선언 시, 설정한 size보다 많은 갯수의 data가 추가되면 저장할 수 없습니다. 이에 반해 Dynamic Array는 저장공간이 가득 차게 되면 resize를 하여 유동적으로 size를 조절하여 데이터를 저장하는 자료구조입니다. 💡 면접 tip Array의 특징중 fixed-size의 한계점을 보완하고자 고안된 자료구조인 Dynamic Array에서 면접을 위해 깊게 공부할 내용은 크게 두 가지이다. 👍 resize를 하는 방식 👍👍 데이터 추가(append)할 때의 시간 복잡도(Time Complexity) 1️⃣ Dynamic Array Dynamic Array는 size를 ..

🤔 면접 질문 Q1. Array는 어떤 자료구조인가요? A1. Array는 연관된 data를 메모리 상에 연속적이며, 순차적으로 미리 할당된 크기만큼 저장하는 자료구조입니다. 💡 면접 tip : Array에 관한 질문을 할 때에는 매우 높은 확률로 Linked List에 대한 질문도 같이 나오게 된다. 따라서, Array의 다양한 특징 중에서 Linked List와 비교가 되는 특성들을 위주로 대답을 하게 되면 편하게 풀어나갈 수 있다. Array와 Linked List의 가장 큰 차이점은 메모리에 저장되는 방식과 이에 따른 Operation의 연산 속도(Time Complexity = 시간 복잡도)이다. 이를 유념하여 공부해가면 좋은 답변을 할 수 있을 것이다. 1️⃣ Array의 특징 고정된 저장 공..