면접 질문 준비(CS기초부분)

IT 기업 신입사원 면접에서 많이 질문하는 면접 질문 목록입니다. 자료구조와 알고리즘 관련 질문 중 스택, 큐, 데크 등 주요 자료구조에 대한 설명과 해시 테이블에 대한 설명입니다. 또한 순차 자료구조와 연결 자료구조의 차이점도 설명되어 있습니다.

 

자료구조와 알고리즘 면접 질문과 답변 정리

자료구조란?

자료구조란 데이터를 원하는 규칙 또는 목적에 맞게 저장하기 위한 구조입니다.

알고리즘이란?

알고리즘은 자료구조에 쌓인 데이터를 활용해 어떠한 문제를 해결하기 위한 여러 동작들의 모임입니다.

 

각 자료구조에 대한 설명

스택(Stack)

스택은 접시를 쌓듯이 자료를 차곡차곡 쌓아 올린 형태의 자료구조입니다. top위치의 원소에만 접근이 가능하기 때문에, 마지막에 삽입한 원소가 가장 먼저 삭제되는 Last-In-First-Out 구조입니다. 용어: top, push, pop

큐(Queue)

큐는 뒤에서는 삽입만 가능하고 앞에서는 삭제만 가능한 자료구조입니다. 따라서 가장 먼저 삽입된 원소가 가장 먼저 삭제되는 First-In-First-Out 구조입니다. 용어: front, rear, enqueue, dequeue

데크(Deque)

데크는 큐 두개를 좌우로 뒤집어서 붙인 구조로, 큐의 양쪽 끝에서 삽입과 삭제 모두를 수행할 수 있도록 확장한 자료구조입니다.

트리(Tree)

트리는 정점과 간선을 이용해 사이클을 이루지 않도록 구성한, 그래프의 특수한 형태입니다. 계층 관계를 갖는 데이터를 표현하기에 적합한 구조입니다.

힙(Heap)

힙은 최댓값 또는 최솟값을 찾아내는 연산을 쉽게 하기 위해 고안된 완전이진트리입니다. 각 노드의 키값이 자식의 키값보다 크거나 같은 경우는 최대 힙, 작거나 같은 경우는 최소 힙이 됩니다.

우선순위 큐(Priority Queue)

우선순위 큐는 가장 우선 순위가 높은 데이터를 먼저 꺼내기 위해 고안된 자료구조입니다. 우선순위 큐를 구현하기 위해서 일반적으로는 힙을 사용합니다.

 

최소비용 신장트리(MST: Minimum Spanning Tree)

신장 트리는 N개의 정점으로 이루어진 무방향 그래프에서, N개의 모든 정점과 N-1개의 간선으로 만들어진 트리입니다.

최소비용 신장 트리는 신장 트리를 구성하는 간선들의 가중치의 합이 최소가 되는 신장 트리를 의미합니다. 최소비용 신장 트리를 만드는 알고리즘은 대표적으로 크루스칼 알고리즘과 프림 알고리즘이 있습니다.

크루스칼 알고리즘

크루스칼 알고리즘은 매 차례마다 가중치가 낮은 간선을 삽입하거나 가중치가 높은 간선을 삭제하는 방식으로 MST를 만드는 알고리즘입니다. 간선을 오름차순 또는 내림차순으로 정렬하여 선택하는데, 사이클이 생성되지 않게 하기 위해 매번 사이클 생성 여부를 판단해야 합니다.

프림 알고리즘

• 프림 알고리즘은 하나의 시작 정점을 기준으로 트리를 점점 확장해가는 알고리즘입니다. 선택된 정점들과 선택되지 않은 정점들을 연결하는 간선들 중 가중치가 최소인 간선으로 연결된 정점을 새로 선택하며, 모든 정점이 선택될 때까지 반복합니다.
• 프림 알고리즘은 이미 선택된 정점을 다시 선택하지 않기 때문에, 사이클 생성 여부를 판단하지 않아도 됩니다.

크루스칼 알고리즘은 가중치를 기준으로 간선을 정렬해야 하기 때문에 간선의 개수가 많지 않은 경우에 적합하며, 간선의 개수가 많을 때는 프림 알고리즘을 사용하는 것이 적합합니다.

 

해시 테이블(Hash Table)

• 해시 테이블은 <key, value>로 데이터를 저장하는 자료구조 중 하나로, 빠른 데이터 검색이 필요할 때 유용합니다. key값에 대해서 해시 함수를 계산하여 주소를 구하고, 구한 주소에 해당하는 위치로 바로 이동하여 값을 꺼내오는 구조입니다.
• 고유한 인덱스로 값을 조회하기 때문에 평균적으로 O(1)의 시간 복잡도를 갖습니다.
• 그러나 해시함수를 통해 계산된 주소값이 충돌하는 경우 chaining 방식 또는 open addressing 방식 등으로 충돌을 해결할 수 있지만, 최악의 경우에는 모든 저장공간을 방문해야 하기 때문에 시간 복잡도가 O(n)까지 늘어날 수 있습니다.
• chaining 방식: 해시 테이블의 각 인덱스의 저장공간을 연결 리스트로 구현. 충돌이 발생해도 노드를 하나 추가하면 됨.
• open addressing 방식: 주소값이 충돌하면 비어있는 주소를 찾아서 그 공간에 저장.

 

순차 자료구조(ArrayList)와 연결 자료구조(LinkedList)의 차이점

• 순차 자료구조는 시작 위치부터 빈자리 없이 자료를 순서대로 연속하여 저장하는 방식으로, 데이터의 논리적인 순서와 물리적인 순서가 일치합니다.
• 연결 자료구조는 물리적 위치가 논리적인 순서와 상관없이 저장되며, 링크에 의해서 논리적인 순서를 표현하는 방식입니다.
• 순차 자료구조는 원하는 데이터에 무작위로 접근할 수 있지만, 연결 자료구조는 순차적인 접근만 가능합니다.
• 순차 자료구조는 리스트의 크기가 제한되어있으며, 리스트의 크기를 재조정하려면 많은 연산이 필요합니다. 반면 연결 자료구조는 링크 정보를 변경하여 추가/삭제 연산을 빠르게 수행할 수 있습니다.

 

정렬 알고리즘

아래는 정렬 알고리즘의 종류와 설명 및 시간 복잡도입니다. 기본적인 정렬 알고리즘은 대표 면접 기출문제이므로 꼭 알아두어야 합니다.

삽입 정렬 (insertion sort)

• 삽입 정렬은 두번째 위치부터 시작하여, 그 앞의 이미 정렬된 원소들과 비교하여 삽입할 위치를 찾아 삽입하는 알고리즘입니다. 평균 시간복잡도는 O(n2)이며, 가장 빠른 경우 O(n)까지 빨라질 수 있습니다.

선택 정렬 (selection sort)

• 선택 정렬은 각 순서에 원소를 넣을 위치는 이미 정해져 있고, 해당 위치에 어떤 원소를 넣을지 선택하는 알고리즘입니다. 오름차순으로 정렬한다면 첫 번째 순서에는 첫 번째 위치에 가장 최솟값을 선택하여 넣고, 두 번째 순서에는 두 번째 위치에 남은 값 중 최솟값을 선택하여 넣는 과정을 마지막까지 반복합니다. 구현이 간단하지만 O(n2)의 시간복잡도를 갖는 비효율적인 정렬 방식입니다.

버블 정렬 (bubble sort)

• 버블 정렬은 인접한 두 원소를 비교하여 자리를 교환해가며 정렬하는 알고리즘입니다.
• 오름차순으로 정렬한다면 첫번째 순서에는 처음부터 마지막 원소까지 비교하여 결과적으로 마지막 위치에 가장 큰 값이 위치하게 되고, 두 번째 순서에는 마지막 원소를 제외하고 같은 과정을 반복하며 정렬하는 방식입니다. 구현이 간단하지만 O(n2)의 시간복잡도를 갖는 비효율적인 정렬 방식입니다.

퀵 정렬 (quick sort)

• 퀵 정렬은 pivot을 설정하여 원소들을 pivot보다 큰 값과 작은 값으로 분할하여 정렬하는 분할 정복 알고리즘입니다. 시간 복잡도는 O(nlogn)이지만, 계속해서 불균등하게 나누어지는 경우에는 O(n2)까지 나빠질 수 있습니다.

병합 정렬 (merge sort)

• 병합 정렬은 주어진 배열을 크기가 1인 배열로 분할한 뒤 이들을 병합하면서 정렬을 진행하는 분할 정복 알고리즘입니다. 시간 복잡도는 항상 O(nlogn)입니다.

셸 정렬 (shell sort)

• 셸 정렬은 삽입 정렬이 어느 정도 정렬된 배열에 대해서 매우 빠르다는 점에서 착안하여 삽입 정렬을 보완한 알고리즘입니다.
• 일정한 간격으로 떨어져 있는 원소들끼리 부분집합을 구성하여, 각 부분집합 내에서 삽입 정렬을 수행한 뒤 모든 부분집합을 다시 합치는 과정을 반복하며 정렬합니다. 시간 복잡도는 평균적으로 O(n1.5)이며, 최악의 경우에는 O(n2)입니다.

힙 정렬 (heap sort)

• 힙 정렬은 주어진 데이터를 힙으로 만들어 최댓값 또는 최솟값부터 하나씩 꺼내며 정렬하는 알고리즘입니다. 전체를 정렬할 때보다는 가장 크거나 작은 값 몇 개를 필요로 할 때 가장 유용합니다. 시간 복잡도는 O(nlogn)입니다.

트리 정렬 (tree sort)

• 트리 정렬은 이진 탐색 트리(BST)를 이용하여 데이터를 정렬하는 방식입니다. 원소들을 순서대로 이진 탐색 트리에 넣은 뒤, 중위 순회로 값을 모두 꺼내면 데이터가 오름차순으로 정렬됩니다. 시간 복잡도는 O(nlogn)입니다.

 

동적 프로그래밍 (DP: Dynamic Programming)

• 동적 프로그래밍이란 주어진 문제를 풀기 위해서 문제를 여러 개의 하위 문제로 나누어 푼 뒤 그것을 결합하여 해결하는 방식입니다. 동적 프로그래밍에서는 어떤 부분 문제가 다른 문제들을 해결하는 데 사용될 수 있기 때문에, 답을 한 번만 계산하고 그 결과를 재사용하는 memoization 기법으로 속도를 향상할 수 있습니다.
• 동적 프로그래밍을 적용하기 위해서는 중복 부분문제와 최적 부분 구조를 만족해야 합니다.
• 중복 부분문제는 문제가 순환적이라서 이전에 구한 작은 문제의 해가 더 큰 부분 문제의 해를 구할 때 여러 번 재사용되는 구조를 의미합니다.
• 최적 부분구조는 작은 부분 문제에서 구한 최적의 답이 합쳐져 큰 부분 문제의 최적의 답을 구할 수 있는 구조입니다.

분할 정복 vs 동적 프로그래밍

• 분할 정복 기법은 단순히 큰 문제를 작은 문제로 나누어 푸는 방법이고, 동적 프로그래밍은 작은 문제의 해가 중복해서 재사용된다는 점을 이용해서 푸는 방법입니다.

 

최단 경로

최단 경로는 네트워크의 양 끝을 연결하는 경로 중 가중치의 합이 최소인 경로를 의미합니다.

다익스트라 알고리즘

• 다익스트라 알고리즘은 하나의 시작점에서 다른 정점까지의 최단 경로를 구하는 알고리즘입니다.
• 최단거리를 여러개의 최단거리로 이루어져 있기 때문에 DP를 적용하여, 하나의 최단 거리를 구할 때 이전까지 구했던 최단 거리 정보들을 재사용하게 됩니다.
• 매 과정에서 아직 방문하지 않은 정점들 중 최단 거리가 가장 짧은 정점을 방문하게 되는데, 이때 우선순위 큐를 활용하면 더욱 효율적으로 처리할 수 있습니다.

플로이드 와샬 알고리즘

플로이드 와샬 알고리즘은 특정 시작점 없이 모든 정점에서 다른 모든 정점으로 가는 최단 거리를 구하는 알고리즘입니다. 두 정점 사이의 어떤 경유점이 존재할 때, 경유점을 거쳐가는 경우의 거리를 계산하여 기존까지 계산한 최단 거리와 비교하며 더 짧은 거리를 선택하는 방식입니다.

 

 

운영체제 면접 질문과 답변 정리

운영체제란?

운영체제는 컴퓨터 사용자와 컴퓨터 하드웨어 간의 인터페이스를 담당하는 프로그램입니다. 프로그램 실행 환경과 필요한 자원을 제공 및 관리해주며, 여러 가지 서비스들을 제공합니다.

메모리란?

메모리는 컴퓨터에서 작업을 수행하기 위해 처리 대상이나 결과 등을 저장하기 위한 공간입니다.

메모리 구조

• 메모리 구조는 Code, Data, Heap, Stack의 네 가지 영역으로 나누어져 있으며, 이들 각각을 세그먼트라고 합니다. 이중 Code와 Data 영역은 정적 세그먼트, Heap과 Stack 영역은 동적 세그먼트라고 합니다.
• Code 영역은 실행할 프로그램의 코드가 저장되는 영역입니다. 프로세스가 종료될 때까지 유지되는 영역입니다.
• Data 영역은 프로그램의 전역 변수와 정적 변수가 저장되는 영역입니다. Code 영역과 마찬가지로 프로세스가 종료될 때까지 유지됩니다.
• Heap 영역은 프로그래머가 동적으로 사용할수 있는 영역으로, Heap 영역에 메모리를 할당하는 것을 동적 할당이라고 합니다. Java에서는 Grabage Collector가 자동으로 메모리를 관리해줍니다.
• Stack 영역은 지역 변수, 매개 변수, 복귀 주소 등이 저장되는, 프로그램이 자동으로 사용하는 임시 메모리입니다. 프로세스(스레드) 생성 시 생성되며, 종료 시 반환되는 영역입니다. 다른 영역들이 하위 영역부터 주소가 할당되는 것과는 달리, Stack 영역은 상위 영역부터 주소가 할당됩니다.

 

프로세스와 스레드

프로세스

프로세스는 메모리에 올라와 실행되고 있는 프로그램의 인스턴스입니다. 각각 독립적인 메모리 영역을 할당받으며, 다른 프로세스와 통신하기 위해서는 IPC(Inter-Process Communication)을 사용해야 합니다. 하나의 프로세스는 최소 1개의 스레드(메인 스레드)를 가지게 됩니다.

스레드

스레드는 프로세스 내에서 프로세스가 할당 받은 자원을 이용하는 실행 단위입니다.

프로세스 내에서 각각의 Stack 영역만 따로 할당받고, 나머지 영역은 서로 공유합니다.

 

멀티 프로세스와 멀티 스레드의 차이

• 멀티 프로세스는 여러 개의 프로세스가 서로 협력적으로 일을 처리하는 것을 말합니다. fork를 통해 프로세스를 여러 개로 복제하여 사용하기 때문에, 서로 통신을 하기 위해서는 IPC를 사용해야 합니다. 따라서 context switching을 위한 오버헤드가 발생합니다.
• 멀티 스레드는 하나의 프로세스 내에 여러개의 스레드를 생성하여 작업을 처리하는 것을 말합니다. 스레드는 서로 메모리를 공유하기 때문에 통신이 쉽고 자원을 효율적으로 사용할 수 있으며, context switching의 오버헤드를 줄일 수 있습니다. 그러나 하나의 스레드에 문제가 발생해도 프로세스에 영향을 주며, 자원을 공유하기 때문에 critical section 문제가 발생할 수 있습니다.

멀티 스레드 프로그래밍 작성 시 유의점

멀티 스레드 프로그램을 개발한다면, 다수의 스레드가 공유 데이터에 동시에 접근하는 경우 상호 배제 또는 동기화 기법을 통해서 동시성 문제 또는 데드락이 발생하지 않도록 주의해야 합니다.

 

Critical Section(임계 영역)

critical section은 한순간에 하나의 프로그램만 접근이 가능한 공유자원에 접근하는 코드 영역을 의미합니다. 프로세스가 공유 데이터를 액세스하고 있으면 해당 프로세스가 critical section 내에 있다고 표현하는데, 하나의 프로세스가 critical section 내에 있으면 다른 프로세스들이 접근하지 못하도록 상호 배제를 수행해야 합니다.

Context Switching(문맥 교환)

context switching은 현재 진행하고 있는 태스크의 상태를 저장한 뒤, 다음으로 진행할 태스크의 상태 값을 읽어서 적용하는 과정입니다.

 

Mutual Exclusion(상호 배제)

• 상호 배제는 특정 자원을 한 순간에 하나의 프로세스만 사용할 수 있도록 하는 것입니다. (한 프로세스가 특정 데이터를 액세스 하는 동안 다른 모든 프로세스들이 해당 데이터를 액세스 할 수 없도록 하는 것) 공유자원을 안전하게 관리하기 위한 상호 배제를 달성하는 기법에는 세마포어와 뮤텍스가 있습니다.
• 뮤텍스(Mutex: MUTual-EXclusion)
  • 뮤텍스는 locking 메커니즘을 이용하여 lock을 건 스레드만이 critical section을 나갈 때 lock을 해제할 수 있습니다.
  • 화장실이 1칸이고 열쇠를 이용해야 하는 경우. 화장실을 누가 사용 중이라 열쇠가 없다면 사용이 끝날 때까지 기다려야 함
• 세마포어 (Semaphore)
  • 세마포어는 Signaling 메커니즘을 이용하는데, lock을 걸지 않은 스레드도 signal을 이용해 lock을 해제할 수 있습니다.
  • 세마포어의 카운트를 1로 설정하면 뮤텍스처럼 활용할 수 있습니다.
  • 화장실 1칸 이상이며, 바깥의 전광판에 비어있는 화장실 수를 띄워놓음. 화장실 들어갈 때 1 빼고 나올 때 1 증가시킴. 따라서 숫자가 0이면 기다려야 함.

데드락 (Deadlock)

데드락(교착상태)은 한정된 자원을 여러 프로세스가 사용하고자 할 때 발생하는 상황으로, 프로세스가 자원을 얻기 위해 영구적으로 기다리는 상태를 말합니다. 예를 들어 자원 A를 가진 프로세스 P1과 자원 B를 가진 프로세스 P2가 있을 때, P1이 B를 필요로 하고 P2가 A를 필요로 한다면 두 프로세스는 서로 자원을 얻기 위해 무한정 기다리는 데드락 상태에 빠지게 됩니다.

 

CPU 스케줄링 기법

하나의 프로세스가 CPU를 점유 중일 때, 다른 프로세스가 CPU를 차지할 수 있는 방식은 선점 스케줄링, 차지할 수 없는 방식은 비선점 스케줄링이라고 말합니다.

• 선입 선처리 스케줄링 (FCFS: First-Come First-Served)
  • 가장 간단한 비선점 스케줄링 알고리즘으로, 프로세스들은 레디큐에 들어온 순서대로 CPU를 할당받습니다. 작업 완료 시간을 예측하기 용이하지만, 덜 중요한 작업이 중요한 작업을 기다리게 할 수도 있습니다.
• 우선순위 스케줄링
  • 프로세스에게 우선순위를 부여하여 우선순위가 높은 순서대로 처리하는 방식입니다. 선점 방식과 비선점 방식 모두 가능합니다. (선점 방식을 사용할 때) 우선순위가 높은 프로세스들이 계속 들어오게 되면 낮은 우선순위의 프로세스들은 무한정 기다려야 하는 문제가 발생합니다. 이때 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시키는 '에이징' 기법을 통해 이를 해결할 수 있습니다.
• SJF (Shortest Job First)
  • 수행 시간이 가장 짧은 프로세스를 먼저 수행하는 비선점 스케줄링 방식으로, 평균 대기시간을 감소시킬 수 있습니다.
• SRT (Shortest Remaining Time)
  • 수행 시간이 짧을 순서대로 프로세스를 수행하는 방식으로, SJF의 선점 방식입니다. 남은 수행 시간이 더 짧은 프로세스가 레디큐에 들어오면 그 프로세스가 바로 선점됩니다.
• Round-Robin
  • time slice(시간 할당량)을 정해놓고, 레디큐는 순환 큐(circular queue)로 설계합니다. 프로세서 스케줄러가 준비 큐를 돌아가면서 한 번에 한 프로세스에, 정의된 시간 할당량만큼 프로세서를 제공합니다. 시간량 내에 끝마치지 못한 프로세스는 다시 레디큐의 맨 뒤에 들어가게 됩니다.(선점 방식). 시간 할당량이 너무 크면 단순한 FCFS와 다를게 없어지며, 너무 작으면 context switching이 자주 일어나 오버헤드가 커지게 됩니다.
• 다단계 큐 (Multi-level Queue)
  • 레디큐를 여러 종류로 분할하여 사용하는 기법입니다. 각각의 큐는 자신만의 독자적인 스케줄링 알고리즘을 수행하며, 큐와 큐 사이에도 우선순위가 존재합니다.
• HRN (Highest Response-Ratio Next)
  • 수행 시간과 대기시간을 모두 고려하여 우선순위를 결정하는 기법입니다.
  • (우선순위) = (수행 시간 + 대기시간) / (수행 시간)

 

 

 

참고:

https://dct-wonjung.tistory.com/entry/%EB%A9%B4%EC%A0%91%EC%A4%80%EB%B9%84-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-1

[면접 준비-CS기초] 1. 자료구조와 알고리즘(1)

 

 

https://dct-wonjung.tistory.com/entry/%EB%A9%B4%EC%A0%91%EC%A4%80%EB%B9%84-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-2

 

[면접 준비-CS기초] 1. 자료구조와 알고리즘(2)

 

 

Database

데이터베이스 정의

공동의 데이터를 여러 사람이 공유하고 사용할 목적으로 통합 관리되는 데이터 집합이다. 기존에 사용하던 파일 시스템이 여러 사람이 공유하며 사용하기에 비효율적인 점이 많았기에 이를 개선하고 더욱 빠른 반응속도를 위해 사용되었다.
논리적으로 연관된 하나 이상의 자료의 모음으로, 그 내용을 고도로 구조화함으로써 검색과 갱신의 효율성을 높인다. 즉, 연관된 데이터끼리 모아 관리하고, 데이터의 중복을 최소화하며, 데이터의 무결성을 보장한다.

데이터베이스의 특징

1. 데이터의 독립성
   • 물리적 독립성
     데이터베이스의 사이즈를 늘리거나 성능 향상을 위해 데이터 파일을 늘리거나 새롭게 추가하더라도 관련된 응용 프로그램을 수정할 필요가 없다.
   • 논리적 독립성
     데이터베이스는 논리적인 구조로 다양한 응용 프로그램의 논리적 요구를 만족시켜 줄 수 있다.
2. 데이터의 무결성
   여러 경로를 통해 잘못된 데이터가 발생하는 경우의 수를 방지하는 기능이다. 데이터의 유효성 검사를 통해 데이터의 무결성을 유지한다.
3. 데이터의 보안성
   인가된 사용자들만 데이터베이스나 데이터베이스 내의 자원에 접근할 수 있도록 계정 관리 또는 접근 권한을 설정함으로써 데이터의 보안을 유지한다.
4. 데이터의 일관성
   연관된 정보를 논리적인 구조로 관리함으로써 어떤 하나의 데이터만 변경했을 겨우 발생할수 있는 데이터의 불일치성을 배제할 수 있다. 또한, 작업 중 일부 데이터만 변경되어 나머지 데이터와 일치하지 않은 경우의 수를 배제할 수 있다.
5. 데이터 중복 최소화
   데이터베이스는 데이터를 통합해서 관리함으로써 파일 시스템의 단점 중 하나인 자료의 중복과 데이터릐 중복성 문제를 해결할 수 있다.

데이터베이스 시스템의 구성요소

• 데이터베이스
• 스키마
• DBMS (DataBase Management System, 데이터베이스 관리 시스템)
• 데이터베이스 언어
• 데이터베이스 컴퓨터
• 데이터베이스 사용자

 

참고: https://velog.io/@deannn/CS-%EA%B8%B0%EC%B4%88-%EB%8D%B0%EC%9D%B4%ED%84%B0%EB%B2%A0%EC%9D%B4%EC%8A%A4-%EB%8D%B0%EC%9D%B4%ED%84%B0%EB%B2%A0%EC%9D%B4%EC%8A%A4-%EC%A0%95%EC%9D%98%EC%99%80-%ED%8A%B9%EC%A7%95

[CS 기초 - 데이터베이스] 데이터베이스 정의와 특징