전체 글304 알고리즘 7 그래프_2 최소 신장 트리 (Minimum Spanning Tree)- 그래프에서, 루프를 형성하는 간선만 제거하면 트리가 됨 - 각 구성 요소가 서로 연결되어 있고, 간선에 가중치가 실려 있는 연결된 가중치 그래프 최소 신장 트리 만드는 알고리즘- 프림 알고리즘- 크루스칼 알고리즘 프림 알고리즘 - 그래프와 최소신장트리준비- 임의의 정점을 시작 정점으로 -> 최소신장트리의 뿌리 노드로 삽입- 정점의 간선 가중치를 조사 -> 가장 가중치가 작은 인접접점 -> 최소 신장트리에 삽입 - 사이클이 생성되지 않도록 이를 반복 - 모든접점 순회가 끝나면 종료 - 우선순위 큐를 통해서, 정점 추가 시 마다, 조사 대상을 추가할 수 있음 - Vertex를 조회하면서, Vertex 별 가장 웨이트가 낮은 간선 정보를 수집 .. 2025. 3. 4. 운영체제 5 교착 상태 식사하는 철학자 문제 -> 영원히 생각하면서 아무도 식사하지 못하는 상태 -생각을 하다가 왼쪽 포크가 사용가능하면 집는다- 생각을 하다가 오른쪽 포크가 사용가능하며 집는다- 왼쪽과 오른쪽 포크를 모두 집으면 정해진 시간동안 식사를 한다- 오른쪽 포크를 내려놓는다- 왼쪽 포크를 내려놓는다- 이를 반복한다 철학자 = 프로세스 또는 스레드포크 = 자원이런 상태가 교착상태 1. 교착상태의 상황이란? 2. 교착상태가 일어나는 근본적인 원인은? 자원 할당 그래프 1. 프로세스는 원 / 자원은 사각형 2. 사용할 수 있는 자원의 갯수는 사각형 내의 점의 갯수3. 프로세스가 자원을 할당받으면 자원에서 프로세스를 향해 화살표 표시 4. 프로세스가 어떤 자원을 기다리면, 프로세스에서 자원으로 화살표를 표시-> 교착 상태.. 2025. 3. 4. 운영체제 4 프로세스 동기화 동기화란? 실행 순서 제어 ; 프로세스를 올바른 순서대로 실행하기 상호 배제 ; 동시에 접근해서는 안되는 자원에 하나의 프로세스만 접근하게 하기 동시에 접근해서는 안되는 자원? 공유 자원 ; 전역변수가 될 수도, 파일, 입출력장치, 보조기억장치가 될 수도예시) 잔액 / 총합 등 특정 프로세스가 완료되지 않았는데 다른 프로세스가 접근하면 값이 어긋난다 임계 구역 ; 동시에 실행하면, 문제가 발생하는 자원에 접근하는 코드 영역 레이스컨디션 ; 동시 다발적으로 임계구역의 코드를 실행하여 문제가 발생하는 경우 -> 저급언어를 실행하는 과정에서 문맥교환이 일어나는 경우 깨질 수 있다 상호배제 동기화 3원칙- 상호배제 ; 임계구역에 진입했을 때 다른 프로세스가 들어올 수 없다- 진행 ; .. 2025. 2. 27. 운영체제 3 CPU 스케줄링 프로세스 종류입출력 집중 프로세스 ; 입출력을 위한 대기 상태에 더 많이 머무름CPU 집중 프로세스 ; 대기 상태보다 실행 상태에 더 많이 머무름 두 개가 동시에 들어오면, 입출력 집중 프로세스를 먼저 처리하고CPU 집중 프로세스를 처리하는 게 효율적 우선순위 ; 운영체제는 PCB에 우선순위를 명시 - 우선순위 높은 프로세스 ; 실시간 프로세스 / 백그라운드 프로세스 등 스케쥴링 큐 ; 우선순위 큐로 작동한다 - 준비 큐 ; CPU 이용하는 프로세스의 큐 - 대기 큐 ; 입출력장치 이용하는 프로세스의 큐 선점형/비선점형 스케쥴링 선점형 ; 다른 프로세스가 CPU를 사용하고 있어도, 자원을 강제로 뺏어서 프로세스에 할당 -> 타이머 인터럽트가 발생하면 운영체제가 다른 프로세스를 실행시키는 일반적 경.. 2025. 2. 26. 운영체제 2 프로세스 포그라운드 프로세스 -> 사용자와 상호작용 하는 프로세스 백그라운드 프로세스 -> 사용자와 상호작용 하지 않는 프로세스 유닉스 ; 데몬 / 윈도우 ; 서비스 PCB ; 프로세스 제어 블록 - 프로세스와 관련 정보를 저장하는 자료 구조 - 커널 영역에 생성됨 - 프로세스 생성 시에 만들어지고, 종료 시 폐기됨 - 프로세스에 CPU를 비롯한 자원을 배분 - 프로세스 ID / 레지스터 값 / 프로세스 상태 / CPU 스케줄링 정보 / 메모리 관리 정보 / 사용한 파일과 입출력장치 문맥 Context - 문맥 교환 ; 기존 프로세스 문맥을 PCB에 백업 / 세로운 프로세스 실행의 문맥을 PCB로부터 복구 실행 프로세스의 메모리 영역 - 커널영역 - 사용자영역 - 스택 영역 ; 매.. 2025. 2. 25. 알고리즘 6 그래프_1 그래프란? 정점의 모음과 간선의 모음이 결합 G= G(V,E) 인접/이웃관계 Adjacent ; 간선으로 연결되 두 정점 경로 ; 길이 ; 정점과 정점 사이의 간선의 숫자 사이클 ; 정점을 두 번 이상 거치도록 되어 있을 경우 방향성 ; 간선에 방향성이 있는 경우와 없는 경우 연결성 ; 두 정점 사이에 간선이 있는 경우 정점의 집합 -> 배열 또는 리스트로 나타냄 간선의 집합 -> 행렬 또는 리스트로 나타냄 = 인접행렬 또는 인접리스트 인접행렬 vs 인접리스트 - 정점 간의 인접 인식 속도 ; 행렬 > 리스트- 필요한 메모리 양 ; 행렬 > 리스트 - 정점과 간선 삽입 속도 ; 행렬 그래프 순회 기법 - 깊이 우선 탐색 - 너비 우선 탐색 GitHub - Sukmin-LanternK/Algor.. 2025. 2. 24. 알고리즘 5 해시 테이블 해시테이블- 데이터의 해시값을 테이블 내 주소로 이용하는 탐색 알고리즘 예 ) 엄청 크기가 큰 배열 -> 주소 다수 / 특정 데이터를 조회하는 시나리오에서-> 통상적으로, 순차탐색 / 이진탐색 등 사용 -> 시간 오래 걸림조회하고자 하는 데이터를 해시함수를 통해 바로 테이블 내 주소값으로 그라운딩 ex) 123817을 조회하고자 할 때, 123817 해싱 -> 3819 얻음해시테이블 Table[3819] = 123817 해시함수 나눗셈법 ; 주소 = 입력값 % 테이블 크기 -> 테이블 안의 범위에 그라운딩 되는 걸 보장 자릿수접기 ; 숫자의 각 자릿수를 더해 해시값을 만드는 것 - 한계 : 나머지 값이 같은 경우, 충돌이 일어날 가능성 - 클러스터링 ; 일부 지역 주소들을 집중적으로 반환하여 한 곳.. 2025. 2. 22. 알고리즘 4 우선순위 큐와 힙 우선순위 큐 ; 큐의 각 요소가 우선순위를 갖는 큐 -> 삽입 시, 우선순위에 맞게 큐가 다시 정렬된다-> 제거 시, 가장 앞의 노드가 제거된다 힙 ; * 여기서 힙은 힙 순서 속성을 만족하는 이진 트리를 말하는 것으로, 프로그래밍 언어에서 말하는 자유저장소 힙이 아니다 힙순서속성; 트리 내의 모든 노드가 부모 노드보다 큰 완전 이진트리 * 힙은 단순히 힙순서속성만 만족하므로 이진트리+이진트리탐색을지원하지않는다 * 힙의 존재가치는 루트 노드가 항상 최솟값 노드라는 점! 힙의 두 가지 연산1. 새 노드 삽입- 완전이진트리를 만족하는 가장 낮은 곳으로 새 노드 삽입 판단 - 부모노드와 비교 - 부모보다 우선순위 높을 경우, 부모와 교환 -> 반복 2. 최솟값 삭제 - 최솟값 삭제 = 루트 노드 삭제 .. 2025. 2. 22. 운영체제 1 메모리 영역 커널영역(운영체제) + 사용자영역(프로그램 ) 운영체제 역할 ; 시스템 자원을 프로그램에 할당 - 커널 + 사용자인터페이스 2가지 역할을 담당한다 이중모드 ; 사용자모드 / 커널 모드로 구분하여 운영체제 역할이 구분됨 - 사용자 모드 ; 운영체제 서비스를 제공받을 수 ㅇ벗는 실행 모드 - 커널 모드 ; 운영체제 서비스를 제공 받을 수 있는 실행 모드 - 시스템 호출 ; 사용자 모드로 실행되는 프로그램이 커널모드 전환할 때 -> 소프트웨어 인터럽트 일종 운영체제 핵심 서비스 1 프로세스 관리 2 자원 접근 및 할당 3 파일 시스템 관리 2025. 2. 21. 컴퓨터 구조 8 입출력장치 장치 컨트롤러 ; 입출력 장치를 다루기 위한 제어기 - 입출력장치는 종류가 너무 많고 / 전송률이 CPU 대비 너무 낮기 때문 - 전송률 ; 데이터를 얼마나 빨리 교환하는 지 - 입출력 제어기 / 입출력 모듈 등으로 불림 장치 컨트롤러 역할 1 CPU-입출력 장치 간의 통신 중개 2 오류 검출 3 데이터 버퍼링 ; CPU와 장치 사이의 데이터를 버퍼에 임시저장하여 전송률을 맞추는 방법 장치 컨트롤러 레지스터 - 데이터 레지스터 ; 버퍼 역할 / 데이터가 많은 입출력장치는 RAM을 쓰기도 함 - 상태 레지스터 ; 작업 할 준비가 되었는지 / 작업이 완료되었는지 / 오류 있는지 상태 정보 저장 - 제어 레지스터 ; 입출력 장치가 수행할 제어 정보와 명령을 저장 장치 드라이버 ; 장치 컨트롤러의 동.. 2025. 2. 19. 이전 1 2 3 4 5 ··· 31 다음 반응형