LCA(Lowest Common Ancestor) 알고리즘이란? 두 개의 노드의 가장 가까운 공통된 부모를 찾는 알고리즘을 말한다. 어떻게 찾을 수 있을까? 위의 트리에서 9와 13의 공통 부모는 둘의 바로 위에 있는 2이다. 물론 9와 13과 같이 같은 Level에 있는 노드인 경우에 두 노드의 Level을 동시에 하나씩 줄여가며 찾을 수 있겠지만 만약 서로 다른 Level에 있는 경우 동시에 거슬러 올라간다 한들 공통 부모를 찾을 수 없다. 따라서 Level이 다른 경우에는 하나의 노드를 거슬러 올라가도록 하여 같은 Level로 맞춰줘야만 한다. 정리하자면, 더 깊은 Level에 있는 노드의 Level을 줄여 얕은 Level에 있는 노드와 동일하게 맞춰줘야 한다. Level과 부모 노드 구하기 우선 ..

운영체제의 구조 커널 핵, 관리자 프로그램, 상주 프로그램, 제어 프로그램이라고도 부른다. 한국어로 알맹이라는 뜻, 핵심을 의미한다. 자주 쓰이는 기능(프로세스 관리, 메모리 관리...)들을 모아놓았기에 항상 메모리에 적재되어 있다. 유틸리티 운영체제에서 커널을 제외한 모든 부분을 말한다. 가끔 쓰이는 기능들이기에 필요할 때 메모리에 적재된다. 시스템 콜 커널에게 무엇인가를 요청하기 위한 API 운영체제의 기능 프로세스 관리 생성/삭제, 상태 관리 자원 할당 프로세스 간 통신 및 동기화 교착상태 해결 PCB를 가짐으로써 프로세스 정보를 관리 프로세서 관리 프로세스가 CPU를 어떻게 사용할지 관리(처리 순서 관리, CPU 할당) 메모리 관리 프로세스에 대한 메모리 할당 및 회수 각 프로세스의 메모리 영역 ..

운영체제와 하드웨어의 관계 프로세서에게 처리할 작업 할당 및 관리 (프로세스 생성 및 관리) 프로그램의 프로세서 사용 시간 관리, 복수 프로그램간 사용 시간 조율 프로그램의 요청에 따른 메모리 할당 및 회수, 할당된 메모리 관리 가상 메모리 생성 및 관리, 논리주소 -> 물리주소 변환 주변 장치 사용을 위한 인터페이스 제공 (장치드라이버 관리) 인터럽트 처리 파일 생성 및 삭제, 디스크 공간 관리 컴퓨터 하드웨어는 크게 프로세서, 메모리, 주변장치로 분류할 수 있다. 프로세서 연산 수행(연산장치)이 가능하며 컴퓨터의 모든 장치의 동작을 제어(제어장치)한다. 레지스터 한마디로 말하면 메모리 중 하나이다. 일반적인 메모리와 다른 점은 프로세서 내부에 있는 메모리라는 점이다. 컴퓨터에서 가장 빠른 메모리이다...

외부 정렬(External Sort)이란? 데이터들의 크기가 주기억장치보다 커 정렬 할 데이터들을 주기억장치에 온전히 입력할 수 없는 경우 사용되는 정렬 방법을 의미한다. 예를 들어 주기억장치가 1GB고, 데이터 파일이 총 100GB라고 했을 때 내부 정렬 알고리즘을 사용하여 정렬할 수 없다. 외부 정렬 과정 분할 외부 정렬은 주기억장치에서 수용할 수 있는 데이터에 대해서만 읽어, 내부정렬을 수행 그 결과를 보조 기억 장치에 다시 저장한다. 여기서 내부 정렬은 상황에 맞는 정렬을 사용하면 된다. 1. 메모리 만큼 데이터를 읽어온다. 2. 활용할 내부 정렬을 이용하여 데이터를 정렬한다. 3. 정렬된 데이터를 보조 기억 장치에 기록한다. 정복 정렬되어 나눠진 블록들을 하나의 블록으로 만들기 위해 Merge ..

정렬 알고리즘 비교 Reference https://d2.naver.com/helloworld/0315536