Algorithm Insertion Sort 영역을 2개로 나누어서 정렬을 수행하는 알고리즘 정렬된 영역 정렬되지 않은 영역 정렬되지 않은 영역에서 데이터를 하나씩 꺼내서 정렬된 영역 내의 적절한 위치에 삽입하여 정렬하는 알고리즘 시간 복잡도 : O(n^2) 장점 구현이 간단하고 이해하기 쉬움 추가적인 메모리 소비가 적다. 단점 데이터의 상태에 따라 성능 ...
운영체제 1. 메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요. 레지스터 가장 빠른 기억장소 CPU 내에 존재 휘발성 메모리 CPU를 나타내는 값에서 32bit, 64bit가 레지스터의 크기를 의미한다. CPU는 계산을 수행할 때 메인 메모리에 있는 값을 레지스터로 가져와서 계산한다. 캐시 휘발성 메모리 레지스터와 메인 메모리 사이의...
Algorithm 재귀가 성능에 영향을 미치는 경우 Call Stack 중복되는 연산 → 중복되는 연산을 저장하고, 같은 계산이 필요할 때 저장된 결과를 사용한다. → 함수 호출 수가 줄어듦. → 성능이 좋아진다. Memoization 계산 결과를 저장해서 여러 번 계산하지 않도록 하는 기법 단점 속도를 위해서 메모리(저장 공간)를 사용한다. 재귀 함수이기...
Algorithm 한 번 정렬이 진행될 때마다 피벗이 정렬되고 정렬될 배열을 좌우로 나눠 재귀호출하여 모든 원소를 정렬한다. Quick Sort 구현 방법 피벗 선택 배열에서 피벗으로 사용할 요소를 선택 일반적으로 첫 번째, 마지막, 또는 중간 요소를 선택 분할 (Partition) 피벗을 기준으로 배열을 두 부분으로 나눈다. 피벗보다 작은 요소들은 왼쪽으...
Algorithm Merge Sort 재귀로 구현하는 정렬 알고리즘 Divide and Conquer 복잡한 문제를 더 작고 관리하기 쉬운 하위 문제들로 나누어 해결하는 알고리즘 설계 기법 구현 방법 분할(Divide): 정렬할 배열을 거의 같은 크기의 두 부분 배열로 나눈다. 정복(Conquer): 각 부분 배열을 재귀적으로 정렬한다. 결합(Combine...
Algorithm 영역을 2개로 나누어서 정렬을 수행하는 알고리즘 정렬된 영역 정렬되지 않은 영역 정렬되지 않은 영역에서 데이터를 하나씩 꺼내서 정렬된 영역 내의 적절한 위치에 삽입 하여 정렬하는 알고리즘 시간 복잡도 O(n^2) : 배열이 역순으로 정렬되어 있는 경우 장점 구현이 간단하고 이해하기 쉽다. 추가적인 메모리 소비가 적다. 단점 시간 복잡도가 ...
Algorithm Recursion(재귀) 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 의미한다. 재귀함수 : 재귀적으로 정의된 함수 재귀함수는 콜스택 이라는 메모리 가득차게 되는 경우 자동으로 종료된다. 기저 조건 : 재귀함수가 종료될 수 있는 탈출 조건 기저 조건이 반드시 있어야 정상적으로 수행할 수 있다. 재귀함수는 함수를 호출할 때마다 Call...
운영체제 FIFO 스케줄링의 장단점이 뭔가요? 장점 구현이 간단하고 이해하기 쉽다 공정성이 보장된다 - 모든 프로세스가 동등하게 처리된다. 기아 현상이 발생하지 않는다. 기아 현상 : 특정 프로세스의 우선 순위가 낮아서 원하는 자원을 계속 할당받지 못하는 상태 단점 긴 대기 시간을 초래할 수 있다. CPU 사용률이 낮아질 수 있다 Burst Time이 짧은...
Algorithm 참고 : https://visualgo.net/en/sorting Bubble Sort 인접한 두 원소를 비교하여 두 원소의 위치를 교환한다. 과정 배열을 처음부터 끝까지 순회하며 인접한 두 원소를 비교한다. 왼쪽 원소가 오른쪽 원소보다 크면 두 원소를 교환한다. 이 과정을 배열이 정렬될 때까지 반복한다. 시간 복잡도 O(n^2) 장점 이...
Algorithm 하노이의 탑 하향식 계산 방식의 좋은 예시 → 재귀함수의 좋은 예시 제약 조건 한 번에 하나의 원반을 움직일 수 있다. 가장 위에 있는 원반만 옮길 수 있다. 아래에 작은 원반이 올 수 없다. OS 교착상태 여러 프로세스가 서로 다른 프로세스의 작업이 끝나길 기다리다가 아무 작업도 수행되지 않는 상태 발생 원인 상호 배제 : 공유 자원은 ...
