대학원 면접질문 대비(알고리즘 / 운영체제)

• 가장 효율적인 정렬과 그것의 시간 복잡도
  
  퀵소트(quick sort)로 최소 및 평균으로는 O($n\log{n}$), 최악의 경우는 O($n^2$)의 시간복잡도를 가짐.
  퀵소트는 divide and conquer개념을 사용하는 알고리즘으로 기준점인 피벗(pivot)을 정하고, 피벗보다 작은값은 왼쪽으로 큰값은 오른쪽으로 정렬해 파티셔닝을 진행함.
  
  
  
• 탐욕알고리즘과 동적계획법
  
  탐욕알고리즘(Greedy Algorithm)
  최적의 값을 구해야 하는 상황에서 각 단계에서 최적이라고 생각되는 값을 선택해나가는 방식으로 최종적인 최적의 값에 도달하는 알고리즘임. (Top-down)
  이전의 선택이 이후에 영향을 주지 않고, 부분문제의 최적해가 전체문제에도 적용할 수 있어야 한다는 조건이 존재함.
  전체 문제에서 최적의 값을 보장하지 못하지만, 속도가 매우 빠름.
  (ex. 거스름돈, 회의 스케줄링 문제, 최대한 많은 놀이기구 타는 법)
  
  greedy 알고리즘의 종류로 kruskal's MST 알고리즘, Prim's MST 알고리즘, 허프만 코드 등이 있음.
  
  동적계획법(Dynamic Programming)
  하나의 문제를 여러 개의 작은 문제로 나누어 그 결과를 저장하고, 다시 큰 문제를 해결할 때 사용하는 방식임.
  Top-down방식(재귀)과 Bottom-up 방식(반복문)으로 구분할 수 있음.
  동일한 작은 문제들이 반복하여 나타나는 경우와 부분문제의 최적결과를 전체 문제에도 적용할 수 있어야 한다는 조건이 존재함.
  모든 결과를 확인하기 때문에 최적의 결과를 보장함.(ex.피보나치 수열, 배낭문제, 부분집합의 합)
  
  
  
• 병렬처리, 분산처리의 차이점
  
  병렬처리는 한개의 컴퓨터에서 작업을 여러 개로 분할하여 사용함.
  반면 분산처리는 여러개의 컴퓨터에서 작업을 여러개로 나누어 처리하는 방식이며, 그 내용이나 결과를 통신망을 통해 상호 교환함. 공유도와 연산속도, 신뢰도는 높지만 보안성이 낮고 개발비용이 많이 든다는 단점이 있음.
  
  
  
• 프로세스와 쓰레드 개념
  
  프로세스는 컴퓨터에서 연속적으로 수행되고 있는 프로그램을 의미함.
  프로세스는 code, data, queue, stack과 같은 메모리영역을 독립적으로 할당받음.
  
  쓰레드는 프로세스 내의 작업단위를 의미하며, stack을 제외한 메모리영역을 공유함.
  따라서, 쓰레드는 자연공유가 용이하며 동시성 향상시킬 수 있음. 하지만, 두 개 이상의 스레드가 하나의 데이터에 접근할 때 병행성 관련 문제가 발생할 수 있음.
  
  프로세스와 쓰레드는 여러흐름이 동시에 진행된다는 공통점이 있지만, 프로세스는 독립적으로 실행되며, 각각 별개의 메모리를 차지하며, 쓰레드는 프로세스 내 메모리를 공유해 경제적으로 사용하고 문맥교환 속도가 빠르다는 차이가 있음.
  
  
  
• 데드락이란?
  
  데드락(교착상태)는 2개 이상의 프로세스나 쓰레드가 서로 무한하게 다음 자원을 기다리게 되는 상태임.
  시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생함. 
  
  
  
• 깊이우선탐색(DFS) / 너비우선탐색(BFS)
  
  깊이우선탐색(DFS)
  루트노드에서 시작하여 다음 branch로 넘어가기 전에 해당 branch를 완벽하게 탐색하는 방식임.
  최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 때 옆으로 탐색을 진행함.
  현재 위치를 스택에 넣어 기억함.
  
  너비우선탐색(BFS)
  인접한 꼭지점을 순서대로 방문하며, 최대한 넓게 이동한 후 더 이상 갈 수 없을 때 아래로 이동하는 순차진행 방식임.
  인접한 지점을 순서대로 방문하기 때문에 큐를 사용함.
  
  
  
• 가상주소 / 물리주소
  
  가상주소
  프로세스가 사용하는 논리적 주소공간으로 물리주소로 변환하기 위해 MMU(Memory Management Unit)을 사용
  물리적 메모리와 무관하게 사용할 수 있어 메모리를 효율적으로 관리할 수 있고, 응용 프로그램의 이동성을 높임.
  IP address(3계층)가 해당
  
  물리주소
  하드웨어 메모리 주소로 데이터를 처리하는 실제 메모리 위치를 의미함. CPU는 가상주소를 물리주소로 변환한 뒤에 실제 메모리에 접근할 수 있음. MAC address(2계층)가 해당
  
  
• 인터럽트 발생 시 우선순위 판별법
  
  폴링
  S/W방식으로, 인터럽트 요청대로 순서대로 검사하며 프로그램이 어떤 상태인지 지속적으로 체크, 응답속도 느림
  
  데이지 체인
  H/W방식으로, 인터럽트 우선순위에 따라 직렬 연결(:데이지 체인)하는 방식, 응답속도 빠름
  
  
  
• 캐시 메모리
  
  메모리에 고려해야 할 문제는 속도 문제와 용량문제가 존재함.
  캐시 메모리는 메모리 속도문제를 개선하기 위한 방식임.
  CPU와 메모리 사이에 위치하는 데이터 저장소로 시스템 속도를 개선하기 위해 사용됨.
  CPU가 필요로 하는 데이터를 캐시에서 임시적으로 저장한 후, 빠르게 제공해 CPU가 데이터를 기다리는 시간을 최소화함. (캐시가 메모리보다 5~10배 빠름)
  CPU가 원하는 정보가 캐시메모리에 있는 경우 문제가 없지만, 캐시메모리에 없는 경우 교체알고리즘을 통해 캐시 메모리의 페이지를 교체함.
  페이지 교체 알고리즘으로 LRU, LFU, FIFO 등이 있음.
  
  
  
• 페이징 기법
  
  메모리에 고려해야 할 문제는 속도 문제와 용량문제가 존재함.
  페이징 기법은 메모리 용량문제를 개선하기 위한 방식임.
  
  페이지는 프로그램을 동일한 크기로 나눈 단위를 의미하며,
  페이징 기법은 페이지를 블록으로 사용하는 기법을 의미함.
  
  페이지 크기는 작을수록 내부 단편화가 적어 메모리의 효율은 늘어날 수 있으나, 페이지 수가 많아져 자주 접근해야 하기 때문에 입출력 효율이 낮음. 페이지 크기가 크면, 내부 단편화가 커지고 불필요한 내용까지 적제될 수 있지만,  페이지 교체 횟수가 줄어들기 때문에 입출력 효율이 높아질 수 있음.
  
  페이지 부재가 발생하는 경우 페이지 교체 알고리즘을 사용함.
  
  OPT(OPTimal replacement): 앞으로 가장 오래 사용하지 않을 페이지를 예측하여 교체
  FIFO: 먼저 들어온 순서대로 교체
  LRU (Least Recently Used): 최근에 가장 오랫동안 사용되지 않은 페이지를 교체, 오버헤드 발생, 어려운 구현
  LFU (Least Frequently Used): 사용빈도가 가장 적은 페이지를 교체
  
  
  
• 바인딩
  
  프로그램 소스의 각종 내부요소나 속성을 확정지는 과정으로 함수 호출과 실제함수를 연결하는 방법임.
  정적바인딩과 동적바인딩으로 구분되며, 기본적으로는 정적바인딩으로 실행됨.
  
  정적바인딩(Static Binding)
  컴파일 시 컴파일 타임에 호출될 함수를 결정함.
  실행속도가 빠르며, 값이 변하지 않아 안정적임.
  (ex. 자료형, 변수명)
  
  동적바인딩(Dynamic Binding)
  프로그램 실행 중에 호출될 함수를 결정함.
  값이 변할 수 있어 유연하지만, 들어올 값보다 메모리 공간을 많이 차지하여 메모리공간이 많이 소요되며, 실행시간이 느림.
  (ex. 변수값)
  
   
• 프로세스 스케줄링
  
  CPU나 자원을 효율적으로 사용하기 위해 진행하며, 선점 스케줄링과 비선점 스케줄링으로 구분됨.
  
  선점 스케줄링(Preemptive)
  대화식 시분할 시스템으로 하나의 프로세스가 CPU를 할당받아 실행 중일때 우선순위가 높은 다른 프로세스가 CPU를 강제로 뺴앗아 사용 가능함.
  우선순위가 높은 프로세스를 빠르게 처리할 수 있다는 장점이 있지만, 많은 오버헤드가 초래된다는 단점이 존재함.
  
  비선점 스케줄링(Non-preemptive)
  일괄처리 시스템으로, 이미 프로세스에 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없음.
  3가지 방법이 존재함.(FCFS, SJF, 우선순위)
  

 

FCFS(First Come First Service): 큐에 들어온 순서대로 처리, 공평성 유지되나 효율성 떨어짐
SJF(Shortes Job First): 실행시간 짧은 프로세스 먼저 처리, 긴 프로세스는 무한 연기 될 수도 있음.
우선순위(Priority): 우선순위가 가장 높은 프로세스가 먼저 할당됨. 우선순위 낮은 프로세스는 무한연기됨.
(무한연기를 막기위해 aging 기법을 통해 프로세스의 우선순위를 높이는 방식을 추가로 사용) 

 

 

• 디스크 스케줄링
  
  사용할 데이터가 디스크 상의 여러 곳에 저장되어 있을 때 데이터에 접근하기 위해 디스크 헤드의 경로를 설정하는 기법임.
  탐색시간의 최적화가 가능하며, 처리량을 최대화할 수 있고 응답시간을 최소화 시킬 수 있음.
  FCFS, SSTF, SCAN 방식 등이 존재함.

FCFS : 큐에 들어온 순서대로 처리하며 데이터 서비스의 공평성 보장, 효율성 떨어짐
SSTF(Shortest Seek Time First): 일괄처리 시스템에 유영하나 응답시간의 편차가 커서 대화형시스템에는 부적합
SCAN: 오버헤드가 적을 때 가장 효율적임.

• 병행 프로세스(Concurrent Process)
  
  2개 이상의 프로세스가 동시에 존재하고 실행 상태에 있는 프로세스를 의미함. 
  문제점으로는 한정된 자원에 대한 사용순서 관련 문제가 발생함 (ex. 프린터 출력물 순서 충돌)
  병행 프로세스에서 발생할 수 있는 문제를 해결하기 위해 4가지 개념이 사용됨.
  (임계구역, 상호배제, 세마포어, 모니터)
  
  임계구역(Critical Section)
  병행 프로세스가 공유자원에 안전하게 접근하기 위해 고려하는 개념으로 여러 프로세스나 쓰레드가 동시에 접근하면 안되는 공유자원이나 코드부분을 의미함.
  
  상호배제( Mutex : Mutual Exclusion)
  한 프로세스가 임계구역을 사용하고 있을 때 다른 하나의 프로세스 혹은 쓰레드가 사용하지 못하게 배제시키는 동기화 기법임.(임계구역에 하나의 프로세스만 들어갈 수 있음)
  
  세마포어(Semaphore)
  정수값을 통해 임계 구역에 진입할 수 있는 프로세스 수를 제어하는 동기화 기법으로,
  여러 프로세스나 쓰레드가 접근하는 것을 막아줌.
  
  모니터(Monitor)
  상호배제 기법과 조건변수를 결합한 고수준의 동기화 기법으로 하나의 프로세스 내에서 다른 스레드 간 동기화에 사용됨.
  
  
  
• Sort 시간 복잡도 정리
  
  

  Algorithm	시간 복잡도 (Average)	시간 복잡도 (Best)	시간 복잡도 (Worst)
  Quick Sort	O($n\log{n}$) (실제로 가장빠름)	O($n\log{n}$)	O($n^2$)
  Heap Sort	O($n\log{n}$) (실제는 퀵보다 2배 느림)	-	-
  Merge Sort	O($n\log{n}$)	-	-
  Bubble Sort	O($n^2$)	-	-
  Insertion Sort	O($n^2$)	-	-
  Selection Sort	O($n^2$)	-	-

  
  
• Quick Sort
  
  기준값(pivot)을 중심으로 분할 후 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 정렬함. (Divide and Conquer)
  크기가 1이 될때까지 파티션을 재귀적으로 반복하여 분할함.
  멀리 떨어져 있는 요소르 교환할 수 있어 효율적임.
  최적의 케이스는 분할을 위한 pivot이 정확히 절반씩 나누어 질때임.
  pivot을 잘 정하기위해 중위값을 사용하는 방식이 있음. 
  
  
  
• Heap Sort
  
  힙 자료구조를 사용해 배열을 정렬하는 알고리즘임.
  키 값의 크기를 우선순위로 힙을 구축하며, 힙에서 최대값인 루트노드를 제거하고, 힙을 재구성하여 정렬된 배열에 값을 추가하는 방식임.
  힙소트는 정렬에 추가적인 메모리를 사용하지 않는다는 장점이 있음.
  

  

 

• Merge Sort
  
  배열을 반으로 분할 후, 각 부분 배열을 재귀적으로 정렬함. 정렬된 부분 배열을 병합하여 전체 배열을 정렬함.
  2개 이상의 정렬된 자료집합을 하나의 정렬된 자료집합으로 합치는 것을 의미함. (Divide and Conquer)
  자료집합이 이미 정렬된 상태이기 때문에 병합 대상과 순차적으로 비교해서 작은 자료를 뽑음.
  병합결과를 저장하기 위한 N개의 공간이 필요하며, 순차적 접근만 가능하기 때문에 random access 성능이 떨어지는 경우에 효과적으로 사용됨 (ex, tape와 같은 외부정렬)
  
  
• Bubble Sort
  
  인접 요소의 비교와 교환을 통해 최대값을 제일 끝으로 보냄.
  뒷부분터 완전정렬이 되는 방식이며, 비효율적이라 잘 사용하지 않음.
  
  
  
• Insertion Sort
  
  현재 레코드를 일부 정렬된 부분의 적절한 위치로 옮겨 현재 수와 바로 앞의 수를 비교함.
  앞부분부터 상대적으로 정렬하는 방식임.
  
  
  
• election Sort
  
  정렬되지 않은 부분에서 최소값을 찾아 정렬된 부분 뒤에 더함.
  앞부분부터 완전정렬하는 방식이며, 교환횟수가 적기 때문에 큰 레코드에 적합함.
  
  
  
• Quick Sort와 Merge Sort의 차이
  
  Quick Sort는 분할,정복(정렬)과정만 수행하지만, merge sort는 분할, 정복(정렬),결합 과정까지 거침.
  
  Quick sort
  pivot선택방식에 따라 시간복잡도가 달라지고 불안정하나, 평균적으로 매우 빠름. 추가적인 배열공간이 필요하지 않음. 내부정렬 알고리즘에 적합함
  
  Merge sort
  항상 안정적인 시간복잡도를 가지며, 일정한 성능을 보장함. 하지만, 병합을 위해 추가적인 배열공간이 필요하며 quick sort보다 공간적으로는 비효율적임. 외부정렬 알고리즘에 적합하며, 대규모 데이터 정렬에 사용됨.
  (ex. 데이터베이스)
  
  
• Sequential Search
  
  검색하고자 하는 값을 처음부터 차례대로 비교해서 검색함.
  
  시간복잡도 (배열)
  삽입: O(1)
  검색: O(N)
  제거: O(N)
  
  시간복잡도 (리스트) → 배열보다 효율적
  삽입: O(1)
  검색: O(N)
  제거: O(1)
  
  
  
• Binary Search
  
  정렬된 자료집합에서 구간크기가 1 이상일 때 사용, 키 값과 중앙값을 비교해서 검색함.
  
  키 값 = 중앙값 : 검색완료
  키 > 중앙값 : 오른쪽으로 이동
  키 < 중앙값 : 왼쪽 이동
  
  시간 복잡도
  삽입: O(N)
  검색: O($\log N$)
  제거: O(N)
  
  
  
• Interpolation Search (보간탐색)
  
  자료집합이 linear하게 정렬된 선형분포를 가졌을때, 내분법(interfpolation)으로 중앙값을 찾는 방식으로,
  나머지 과정은 binary search와 동일함. 정수와 실수만 가능함.
  
  시간 복잡도
  삽입: O(N)
  검색: O($\log(\log N)$)
  제거: O(N)