FRONTEND - 자료구조, 운영체제 면접 질문

Array와 LinkedList의 차이가 무엇인가요? (N사 전화면접)

Array는 Random Access를 지원한다. 요소들을 인덱스를 통해 직접 접근할 수 있다. 따라서 특정 요소에 접근하는 시간복잡도는 O(1)이다. 반면 Linkedlist는 Sequential Access를 지원한다. 어떤 요소를 접근할 때 순차적으로 검색하며 찾아야 한다. 따라서 특정 요소에 접근할 때 시간복잡도는 O(N)이다.

저장방식도 배열에서 요소들은 인접한 메모리 위치에 연이어 저장된다. 반면 Linkedlist에서는 새로운 요소에 할당된 메모리 위치 주소가 linkedlist의 이전 요소에 저장된다.

배열에서 삽입과 삭제는 O(N)이 소요되지만, Linkedlist에서 삽입과 삭제는 O(1)이 소요된다.

배열에서 메모리는 선언 시 컴파일 타임에 할당이 된다.(정적 메모리 할당) 반면 Linkedlist에서는 새로운 요소가 추가될 때 런타임에 메모리를 할당한다.(동적 메모리 할당)

배열은 Stack 섹션에 메모리 할당이 이루어 진다. 반면 Linkedlist는 Heap 섹션에 메모리 할당이 이루어진다.

 

Stack과 Queue의 차이점은 무엇인가요? (N사 전화면접)

스택은 쌓아 올리는 자료구조이다. 같은 구조와 크기의 자료를 정해진 방향으로 쌓을 수 있고, 한 방향으로만 접근할 수 있다. top을 통해서 push, pop을 하면서 삽입과 삭제가 일어난다. 후입선출 구조이다. DFS나 재귀에서 사용된다.

큐는 원소의 줄을 세우는 자료구조이다. 큐는 한 쪽 끝에서 삽입 작업을, 다른 쪽 끝에서 삭제 작업을 진행한다. 선입선출 구조이다. 주로 데이터가 입력된 시간 순서대로 처리되어야 하는 경우 사용한다. BFS나 캐시를 구현할 때 사용한다.

 

BST와 Binary Tree에 대해서 설명하세요. (N사 전화면접)

이진탐색트리(Binary Search Tree)는 이진 탐색과 연결 리스트를 결합한 자료구조이다. 이진 탐색의 효율적인 탐색 능력을 유지하면서, 빈번한 자료 입력과 삭제가 가능하다는 장점이 있다. 이진 탐색 트리는 왼쪽 트리의 모든 값이 반드시 부모 노드보다 작아야 하고, 반대로 오른쪽 트리의 모든 값이 부모 노드보다 커야 하는 특징을 가지고 있어야 한다. 이진 탐색 트리의 탐색, 삽입, 삭제의 시간복잡도는 O(h)이다. 트리의 높이에 영향을 받는데, 트리가 균형이 맞지 않으면 워스트 케이스가 나올 수 있다. 그래서 이 균형을 맞춘 구조가 AVL Tree이다.

 

PriorityQueue의 동작 원리가 어떻게 되나요? (N사 전화면접)

우선순위 큐는 힙이라는 자료구조를 가지고 구현한다. top이 최대면 최대힙, top이 최소면 최소힙으로 표현한다. 힙으로 구현된 이진 트리는 모든 정점이 자신의 자식 요소보다 우선순위가 높다는 성질을 가지고 있다. 이 성질을 통해 삽입과 삭제 연산을 모두 O(logN)으로 수행할 수 있다.

 

해시테이블(HashTable)에 대해서 설명해주세요.

해시테이블은 효율적인 탐색을 위한 자료구조로 key값을 value에 대응시킨다. 해시테이블을 구현하기 위해서는 연결 리스트와 해쉬 함수가 필요하다. 해싱은 임의의 길이의 값을 해쉬 함수를 통해 고정된 크기의 값으로 변환하는 작업을 말하는데, 키 값을 해시 코드로 변환한 후 해당 해시 코드로 배열의 인덱스를 참조하여 값을 찾는다. 충돌이 발생할 수 있으며, 최악의 경우 O(N), 일반적으로 잘 구현된 경우는 O(1)의 시간 복잡도를 가지게 된다. 충돌은 Chaining, Open addressing 등의 방식으로 해결할 수 있다.

해시테이블은 균형 이진 탐색 트리로도 구현할 수 있다. 이 경우는 탐색 시간이 O(logN)이 된다. 이 방법은 크기가 큰 배열을 미리 할당해 놓지 않아도 되기 때문에 잠재적으로 적은 공간을 사용한다는 장점이 있다.

 

최소 스패닝 트리(Minimum Spanning Tree)에 대해서 설명해주세요.

그래프 G의 스패닝 트리 중 edge weight 값이 최소인 스패닝 트리를 말한다. 스패닝 트리란 그래프 G의 모든 vertex가 cycle 없이 연결된 형태를 말한다. n개의 vertex를 가지는 그래프에서 반드시 (n-1)개의 edge만을 사용해야 하며 사이클이 포함되어서는 안 된다. Kruskal과 Prim을 통해서 MST를 구현할 수 있다. Kruskal의 경우 그래프의 간선들을 오름차순으로 정렬하여 가장 낮은 가중치의 간선부터 차례로 MST에 집합체 추가하는 그리디 알고리즘 방식을 사용한다. Prim의 경우는 시작 정점부터 단계적으로 트리를 확장하는 방법이다.

 

참고자료

1. <코딩 인터뷰 완전분석(Cracking the coding interview)> 게리 라크만 맥도웰 저
2. https://medium.com/@audrl1010/linked-list-와-array-차이점-4ba873c2e5f5
3. https://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220791188929
4. https://baeharam.github.io/posts/data-structure/hash-table/
5. https://ratsgo.github.io/data structure&algorithm/2017/10/22/bst/
6. https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 - Heee's Development Blog

 

컴파일러와 인터프리터의 차이가 무엇인가요? (N사 전화면접)

컴파일러와 인터프리터 모두 고레벨 언어를 기계어로 변환하는 역할을 수행하지만 차이점은 컴파일러의 경우 전체 코드를 보고 명령어를 수집하고 재구성하는 반면, 인터프리터는 소스코드의 각 행을 연속적으로 분석하며 실행한다. 인터프리터는 고레벨 언어를 중간 레벨 언어로 한 번 변환하고 이를 각 행마다 실행하기 때문에 일반적으로 컴파일러가 인터프리터보다 실행 시간이 빠른 경우가 많다. java의 경우 .java 파일을 .class 파일로 자바 컴파일러가 컴파일을 하고, .class 파일을 기계어로 인터프리터가 변환하는 것이다.

 

프로세스와 스레드의 차이가 무엇인가요? (N사 전화면접)

프로세스는 운영체제로부터 CPU 자원을 할당받는 작업의 단위이다. 그리고 메모리에 올라와 실행되고 있는 프로그램의 인스턴스(독립적인 개체)를 의미한다. Code, Data, Stack, Heap의 구조로 되어 있다, 이러한 구조로 된 독립된 메모리 영역을 할당받는다.

스레드는 프로세스 내에서 실행되는 여러 흐름의 단위이다. 스레드는 프로세스 내에서 각각 Stack만 따로 할당받고 Code, Data, Heap 영역은 공유한다.

멀티 프로세스에 비해 멀티 스레드가 가지는 장점은 먼저 첫 번째로 프로세스를 생성하여 자원을 할당하는 시스템 콜이 감소함으로서 자원을 효율적으로 관리할 수 있다는 점이다. 두 번째로 프로세스 간 통신(IPC)보다 스레드 간의 통신 비용이 더 적게 발생한다. 다만 멀티 스레드 사용 시에는 공유 자원으로 인한 문제를 해결하기 위해 동기화를 신경써 주어야 한다.

 

LRU에 대해서 설명해 보세요. (N사 전화면접)

LRU는 페이지 교체 알고리즘 중 하나로, 최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 방식이다.

 

Thread-safe의 개념에 대해 설명하세요. (K사 전화면접)

Thread safe는 멀티 스레드 프로그래밍 환경에서 일반적으로 어떤 함수나 변수, 혹은 객체가 여러 스레드로부터 동시에 접근이 이루어져도 프로그램의 실행에 문제가 없는 것을 말한다.

Thread-safe한 코드를 만들기 위해서는 Critical Session을 통해 스레드 내부에서 처리되는 연산들을 직렬화 하여 한 번에 한 스레드에서 연산이 수행되도록 만들어 주어야 한다.

 

GPU와 CPU의 차이에 대해 설명하세요. (K사 전화면접)

CPU는 입출력장치, 기억장치, 연산장치 등을 포함한 컴퓨터 리소스를 관리하는 최상위 계층의 중앙처리장치이다. 따라서 데이터 처리와 더불어 프로그램에서 작업의 우선순위를 지정하고 전환하며 가상 메모리를 관리하는 등의 역할을 한다. CPU는 직렬 처리에 최적화된 몇 개의 코어로 구성되어 있다.

GPU는 반복적이고 비슷한 대량의 연산을 수행하며 이를 병렬적(parallel)으로 나누어 작업하기 때문에 CPU에 비해 속도가 압도적으로 빠르다. GPU는 병렬 처리용으로 설계된 수 천 개의 보다 소형이고 효율적인 코어로 구성되어 있다.

 

교착상태(데드락)가 무엇이고 발생하는 조건을 설명해 주세요.

교착 상태는 프로세스가 자원을 얻지 못해 다음 처리를 하지 못하는 상태로, 시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생한다.

상호 배제, 점유 대기, 비선점, 순환 대기 네 가지 조건을 모두 만족해야 교착 상태가 발생한다. 순환 대기의 경우 점유 대기와 비선점 조건을 만족해야 성립하므로 4가지 조건은 완전히 서로 독립적이지 않다.

 

페이지 폴트가 무엇인가요?

가상 메모리의 페이지 테이블에는 페이지가 물리 메모리에 있는지, 스왑 영역에 있는지 표시하는 유효 비트를 사용한다. 프로세스가 페이지를 요청했을 때 그 페이지가 메모리에 없는 경우를 페이지 폴트라고 한다. 페이지 폴트가 발생하면 프레임을 새로 할당 받아야 하며, 프로세스가 해당 페이지를 사용할 수 있도록 스왑 영역에서 물리 메모리로 옮겨야 한다. 그리고 페이지 테이블을 재구성 하고, 프로세스의 작업을 재 시작한다.'

 

문맥 전환(Context Switching)이 무엇인가요?

멀티 프로세스 환경에서 CPU가 어떤 하나의 프로세스를 실행하고 있는 상태에서, 인터럽트 요청에 의해 다음 우선 순위의 프로세스가 실행되어야 할 때 기존의 프로세스의 상태 또는 레지스터 값(context)을 저장하고 CPU가 다음 프로세스를 수행하도록 새로운 프로세스의 상태 또는 레지스터 값(context)을 교체하는 작업을 context switching이라고 한다.

OS에서 context는 CPU가 해당 프로세스를 실행하기 위한 해당 프로세스의 정보들이다. 이 context는 프로세스의 PCB(Process Control Block)에 저장된다.

 

메모리가 어떻게 구성되어 있는지 설명해 주세요.

메모리는 크게 코드, 데이터, 스택, 힙 영역으로 나누어져 있다. 코드 영역은 실행될 프로그램의 코드가 저장되어 있는 영역이다. 데이터 영역은 전역 변수와 정적 변수가 저장되어 있는 영역이다. 스택 영역은 지역변수와 매개 변수가 저장되어 있으며, 함수의 호출과 함께 할당되는 영역이다. 힙 영역은 사용자에 의해 동적으로 할당되고 해제될 수 있는 메모리 영역이다. 스택 영역은 컴파일 타임에 크기가 결정되고, 힙 영역은 런 타임에 크기가 결정된다.

 

가상 메모리(Virtual Memory)에 대해 설명해 주세요.

가상 메모리는 멀티 프로세스 환경에서 프로세스마다 충분한 메모리를 할당하기에 물리 메모리의 한계가 있어서 나타난 개념이다. 가상 메모리에서 프로세스는 가상 주소를 사용하고, 실제 해당 주소에서 데이터를 읽고 쓸 때 물리 주소로 바꿔주게 된다. MMU(Memory Management Unit)를 통해 CPU에서 코드 실행 시, 가상 메모리 접근이 필요할 때, 해당 주소를 물리 주소로 변환해 준다.

 

참고 자료

1. https://m.blog.naver.com/PostView.nhn?blogId=complusblog&logNo=220985528418&proxyReferer=https:%2F%2Fwww.google.com%2F
2. https://gmlwjd9405.github.io/2018/09/14/process-vs-thread.html
3. https://sdc-james.gitbook.io/onebook/1./1.1.-artificial-intelligence/1.1.1.-cpu-gpu
4. https://geekhub.tistory.com/58
5. https://jeong-pro.tistory.com/93

 

12