[💬] 밑에 회사 면접 질문들 답 써봄

[겜스갓흥엔진(xmsksakstp)]

1. 자료구조

선형 자료구조 - 리스트, 스택, 큐, 덱

비선형 자료구조 - 우선도 큐, 트리, 그래프, 네트워크

2.배열리스트과 연결리스트의 차이

배열리스트은 모든 메모리 주소가 서로 붙어있고, 무언가 삽입, 삭제하는 작업을 할때 해당 공간을 비운다음 배열 전체를 당기고 미는 과정이 있기 때문에

삽입, 삭제시 효율이 떨어짐, 대신 모든 메모리 주소가 붙어있기 때문에 검색 작업을 할때 효율이 좋고 연결리스트에 비해 실행 효율을 중시함

연결리스트는 프밍이 직접 데이터 필드와 링크 필드를 메모리를 사용해 할당한 후 할당한 링크 필드에 앞노드의 주소, 뒷노드의 주소를 저장하고 데이터 필드에 저장할 값을 입력해 저장하는 방식. 삽입 삭제시, 앞노드의 주소, 뒷노드의 주소만 지우고 새로 입력해주면 되기 때문에 배열에 비해 삽입 삭제가 용이함. 대신 값이 분산적으로 저장되기 때문에 검색 작업은 배열에 비해 성능이 떨어짐, 배열에 비해 메모리 효율을 중시함

3.스택과 큐

스택은 후입 선출의 방식의 선형 리스트로 쌓인 접시더미 등의 예시

스택 상단을 top, 하단을 bottom으로 한다. bottom의 값이 0일 경우 스택이 비어있고, top == bottom일경우 스택이 꽉 찬 경우이다.

큐는 선입 선출의 방식의 자료구조로 선형 큐, 원형 큐로 분류되지만 선형 큐는 거의 사용되지 않는다.

큐의 앞을 front 뒤를 rear라고 한다. front == rear 일경우 큐가 비어있고 front%요소 == (rear+1)%요소 일 경우 큐가 꽉 찬 경우이다.

4.힙

힙은 우선도 큐에 사용되는 정렬 방법으로 완전 이진 트리로 구성된다.

우선 순위에 알맞는 값이 위로 올라오고 자식 노드의 크기에 따른 순서는 상관하지 않는다.

5. 정렬 알고리즘

안정적인 정렬 방법 (같은 요소가 정렬 도중 순서가 바뀌지 않음): 선택O(n^2), 삽입O(n^2), 버블O(n^2), 합병O(nlog2n)

비 안정적인 정렬 방법 (같은 요소가 정렬 도중 순서가 바뀜: 퀵O(nlog2n) 힙O(nlog2n)

번외: 쉘 (삽입정렬이 정렬된 상태에서 시간복잡도가 O(n)인 것을 이용한 정렬) O(n^1.5), 기수정렬 (자릿수로 버킷에 넣다 뺐다 하며 정렬)O(kn)

6. 퀵정렬

양 쪽 끝을 서로 i j 라고 친다.

피봇을 설정한 후 피폿보다 i와 j가 커지고 줄어들며 작은값을 왼쪽 큰값을 오른쪽에 놓는다

그 후 피봇을 i = j 지점 혹은 i > j 일때 j 지점에 피봇을 설정한다.

반복

최선의 경우 시간복잡도가 O(log2n)이며 최악의 경우 (피봇의 교환이 1회도 일어나지 않을때) O(n^2)의 복잡도를 보인다.

median of 3, 가상키 설정, 퀵정렬과 삽입정렬을 서브파일의 갯수에 따라 나눠 호출하는 식으로 개선할수 있다.

나 자료구조 중간고사때 이거랑 비슷한 문제들 풀어본듯;

[익명(223.33)]

배열에 삽입삭제를 어찌하노?

[ㅇ(222.97)]

삽입삭제가 되는 구조를 만들면 가능하지 c++ vector 처럼

[익명(223.33)]

그건 배열이 아니라 배열리스트 잔아 근데 그관점에서 설명은 ㅇㅈ

[겜스갓흥엔진(xmsksakstp)]

리스트 배울때 배열로 만드는 방법, 연결리스트로 만드는 방법 일케 배워가지고 배열, 연결리스트로 외우고 있었네이

[익명(14.38)]

면접자리는 시험문제 푸는 곳이 아니라서.. 간단하게 설명하는 다른 사람이 있었으면 밀려나게 돼

[익명(14.38)]

대신 자잘하게 설명하지 않고 의미만 명확하게 전달하면 더 인상이 좋아짐

[ㅇ(222.97)]

근데 힙은 보통 자료구조 힙을 묻기보다는 메모리영역 힙 질문한거인듯

[듀콜다(duecorda)]

아래위로 질문을 보자면 힙 정렬 질문아닐까? 매모리 힙이요? 물어보면 되겠지만...

[겜스갓흥엔진(xmsksakstp)]

자료구조 문제만 있길래 그짝인줄

[ㅇ(222.97)]

보통 메모리영역만 물러보지 자료구조 힙은 물어보는데가 없어서 말해본거임 ㅋㅋ 뭐 실제 면접장에선 정확히 명시해주겠지

[익명(211.197)]

배열 왜 설명을 리스트랑 섞어서 해놨냐

[겜스갓흥엔진(xmsksakstp)]

리스트 배울때 배운 내용이라...

[익명(211.197)]

모르는애들이 틀린내용보면 혼란옴 수정ㄱ

[익명(211.197)]

수정된 내용도 잘못된거같은데 내용들이 물리적으로 붙어있는건 배열이지 어레이리스트는 아님...

[겜스갓흥엔진(xmsksakstp)]

잘못 배운건가 어레이 리스트도 붙어있는걸로 배웠는데

[익명(14.38)]

박싱 먼저 하고 오브젝트타입을 카피해서 넣기 때문에 값이 이어지지는 않을거로보인다. 애초에 참조타입을 넣는 경우는 말할 것도 없고.. 근데 이건 배열도 마찬가지잖아?