기술면접은 대부분 말로해야하거나 때로는 코딩도 주어지기때문에
그림은 생략하고 쉽게 말로전달할수있도록 정리해봤습니다.
질문 1 : Array와 List의 차이점은 무엇인가요??
배열(Array)
(1) 고정된 크기를 갖고 같은 자료형의 원소들이 연속적으로 나열되어있음,
(2) 각 원소를 인덱스로 관리하며 데이터의 접근, 수정 시간복잡도는 O(1)
(3) 배열을 선언시 배열의 크기를 지정, 그러나 선언후 크기가 고정적임
(4) 특정원소에대한 읽기,쓰기를 지원, 언어에 따라 배열의 길이에 대한것까지만 지원함
(5) 랜덤엑세스가 가능
(6) 논리적, 물리적 주소가 같음
리스트(List)
(1) 리스트는 두가지가 존재 ArrayList와 , LinkedList
(2) 두가지 공통점은 중간에 빈공간을 허용하지 않음
ArrayList
(1) 내부적으로 배열을 이용하여 요소를 저장하는 자료구조 배열의 정적인 크기라는 한계점을 극복하여 리스트의 저장공간 크기는 가변적임
(2) 배열을 이용하였기 때문에 특정위치에 있는 원소 접근의 시간복잡도가 O(1)
(3) 데이터를 추가하거나 삭제가 느림 O(n), 그러나 맨뒤에 있는 데이터를 삽입,삭제일 경우 O(1)
(4) 배열로 구현되어있기에 마찬가지로 랜덤엑세스가 가능
(5) 저장공간을 확장 or 복사 하는 과정의 시간복잡도 O(n)
(6) 지정된 capacity가 존재, capacity는 항상 size<=capacity의 를 보장하기 때문에 데이터삽입시 size>capacity인경우
capacity를 증가한후 새로운 배열을 생성하여 내부적으로 기존의 데이터를 복사하는 하는 과정이 일어남
(7) 논리적 물리적 주소가 같음
LinkedList
(1) ArrayList와 달리 맨앞에 원소를 삽입 or 삭제하는 시간이 O(1) ->이유는 양방향 연결리스트로 구현되어있기때문에
(2) 데이터가 연속적으로 나열되어있지 않음 , 논리적, 물리적 주소가 다름
(3) 인덱스를 활용할수 없기때문에 랜덤엑세스가 불가능
(4) 중간위치에 데이터의 접근, 수정, 삽입, 삭제 시간복잡도는 O(n)
(5) 새로운 원소가 삽입 삭제일경우 저장공간을 확장하거나 축소해줄 필요가 없음;
질문 2 : 두개의 스택으로 큐를 구현하고 왜그렇게 구현했는지, 시간복잡도가 어떻게 되는지 설명하라
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
#include<iostream>
#include<stack>
using namespace std;
class Queue{
private:
stack<int>st1, st2;
public:
void push(int data) {
st1.push(data);//push 작업은 st1에 데이터를 넣음
}
void pop() {
if (st2.empty()) {//st2가 비어있다면 st1에있는데이터를 모두 꺼내서 st2에 넣음
while (!st1.empty()) {
st2.push(st1.top());
st1.pop();
}
}
st2.pop();
}
int front() {
if (st2.empty()) {//st2가 비어있다면 st1에있는데이터를 모두 꺼내서 st2에 넣음
while (!st1.empty()) {
st2.push(st1.top());
st1.pop();
}
}
return st2.top();
}
int size() {
return st1.size() + st2.size();//데이터의 갯수는 2개가 가지고있는 데이터의 갯수의합
}
bool empty() {
return st1.empty() && st2.empty();//둘다 비었는지 확인
}
};
int main()
{
Queue q;
q.push(1);
q.push(2);
q.push(3);
cout << q.front() << "\n"; //1이출력
q.pop();
q.push(4);
q.push(5);
cout <<"사이즈 : " << q.size() << endl; //사이즈 4출력
while (!q.empty()) {
cout << q.front() << "\n"; //2 -> 3 -> 4 -> 5 출력
q.pop();
}
}
|
cs |
(1) 스택 2개로 구현을함 하나는 데이터를 삽입하기위한 메모리이고, 다른하나는 데이터를 꺼내기 위한 메모리로 구성
(2) 데이터를 삽입하는경우 st1에만 데이터를 삽입
(3) 데이터를 pop하는 경우 st2에 있는 데이터가 없으면 st1에 데이터를 st2에 옮겨주고 st2에 있는 가장 상단에있는 데이터를 pop하는 형식으로 구현하면 구현할수 있습니다
(4) push 시간복잡도는 st1에만 push를 하기때문에 시간복잡도 O(1)
(5) pop 시간복잡도는 2가지로 분류 st2가 비어있으면 st1에 있는 데이터를 st2에 담아주기때문에 이때의 시간복잡도는 O(n) , 그러나 st2가 비어있지 않으면 st2가 비어있을때까지 pop의 시간복잡도는 O(1) 입니다.
질문 3 : 3way handshake에 대해 과정을 설명하고 , 2way handshake만 성공할시 어떻게 되는지 설명하라
(1) tcp 장치들 사이의 논리적인 접속을 성립하기위해 3 way handshake를 사용합니다.
(2) 1way에서 Client > Server : TCP SYN 을보냅니다.
2way에서 Server > Client : TCP SYN, ACK
3way 에서Client > Server : TCP ACK 을 받게되면 3way handshake가 성립되기때문에 논리적인 접속을 성립됩니다.
(3) 3way에서 client는 server에서 요청한 대답을 기다리고 있는 상태지만 내부적으로 Connection Time이 존재함 그러나. Connection Time이 무한정이지는 않기때문에 해당 Connection Time만큼 대답을 받지 못한경우 TimeOut을 발생시키고 연결은 연결을 실패로 돌아감 이것을 Connection TimeOut이라고 함
질문 4 : 트랜잭션이 무엇인지 설명하시오
트랜잭션(Transaction 이하 트랜잭션)이란, 데이터베이스의 상태를 변화시키기 해서 수행하는 작업의 단위를 뜻한다.
쉽게 얘기하면 게시판에 글을 작성하고 올렸을때 자신이 작성했던 글과 다른사람들이 작성했던 글들의 목록이 보인다 이때 내가 작성했던 글과 목록들을 한꺼번에 보인다면 insert와 ,select를 합친것이다 이러한 작업단위가 트랜잭션이다.
트랜잭션은 4가지 특징이 존재
원자성 : 트랜잭션이 데이터베이스에 모두 반영되던가 아니면 전혀 반영되지 않아야함
일관성 : 트랜잭션의 작업처리 결과가 항상 일관성 있어야함
독립성 : 어떤 하나의 트랜잭션이라도 , 다른 트랜잭션의 연산에 끼어들수 없음
지속성 : 트랜잭션이 성공적으로 완료됐을 경우, 결과는 영구적으로 반영되어야함
질문 5 데이터베이스 인덱스에 관해 설명하시오
데이터베이스의 테이블에대한 검색 속도를 향상시켜주는 자료구조임
인덱스의 가장 큰 특징은 데이터들이 정렬 되어있기때문에 데이터 조회시 인덱스를 활용하면 검색속도를 향상시킬 수있음
인덱스를 사용하면 ORDER BY에 의한 정렬 과정을 피 할수 있음 ORDER BY는 부하가 많이 걸리는 작업임
인덱스 구조는 B TREE 구조로 B * TREE or B+ TREE 구조가 가장 많이 사용됨
'면접' 카테고리의 다른 글
| 2022 SW마에스트로 심층면접 후기 (0) | 2022.03.29 |
|---|
