분류 전체보기335 알고리즘 10 알고리즘 성능 분석 알고리즘 성능 측정 기준 1. 정확성 2. 작업량 3. 메모리 사용량 4. 단순성 5. 최적성 알고리즘 수행 시간 분석 - 최악의 경우 수행 시간 ; 보장 되는 알고리즘 성능 - 평균의 경우 - 최선의 경우 ; 알고리즘이 낼 수 있는 최적 성능 한계 점근 표기법 ; 최고차항만으로 표기 - Big O 표기법; 최악의 경우 수행 시간 표기 / 점근적 상한 - Big Omega 표기법 ; 최선의 경우 수행 시간 표기 / 점근적 하한 - Big Theta 표기법 ; 점근적으로 자신의 증가율과 같은 증가함수 포함 2025. 3. 19. 알고리즘 9 문자열 탐색 1. 고지식한 탐색의 동작 방식 -문자 바이 문자로 등호 검증 2. 카프 라빈 알고리즘 - 해시함수 계산을 가볍게 단축시켜서 검증하는 방법 3. KMP 알고리즘 - 접두부와 접미부가 같은 경우, (Border = 경계) 접두부-접미부 일치한 탐색이 한 차례 끝나고 나면, 그 다음 탐색은 바로 접미부부터 시작하면 된다 - 정확히는 -> 일치하는 부분 문자열의 길이 - 경계의 길이만큼 이동 - 경계 정보 사전 계산 방법 4. 보이어-무어 알고리즘 - 불일치 발생 -> 불일치 문자가 본문에 없을 때 -> 일치한 패턴만큼 이동 - 나쁜 문자 이동 ; 불일치 발생 시, 패턴에서 본문 불일치 문자를 오른쪽에서 부터 찾음 -> 본문과 패턴의 불일.. 2025. 3. 18. 알고리즘 8 그래프_3 데이크스트라 알고리즘 ; 최단 경로 탐색 정점들과 정점의 연결 여부만 따짐 ; 프림 / 크루스칼 경로의 길이를 감안하여 연결 ; 데이크스트라 - 각 정점에, '시작점으로부터' 자신에게 이르는 경로의 길이를 저장할 변수를 준비 - 각 정점의 경로 길이 무한대로 초기화 / 시작 정점의 경로 길이 = 0 - (최단 경로에 새로 추가된 정점)의 인접 정점에 대해 경로 길이를 갱신 - 그래프 내 모든 정점이 최단 경로에 소속될 때가지 반복 Algorithm/Graph at main · Sukmin-LanternK/AlgorithmContribute to Sukmin-LanternK/Algorithm development by creating an account on GitHub.github.com 2025. 3. 10. 운영체제 7. 파일 시스템 파일 ; 보조기억장치에 저장된 관련 정보의 집합 -> 이름/실행정보/ 부가정보(속성/메타데이터) 파일 속성 - 유형/크기/보호/생성날짜/마지막접근날짜/마지막수정날짜/생성자/소유자/위치 - 유형 ; 운영체제가 인식하는 파일의 종류- 보호 ; 어떤 사용자가 해당 파일을 읽고 쓰고 실행할 수 있는지 - 위치 ; 보조기억장치 상의 현재 위치 파일 연산을 위한 시스템 호출 - 운영체제는 아래의 시스템 호출을 제공한다 - 파일 생성 > 파일 삭제 > 파일 열기 > 파일 닫기 > 파일 읽기 > 파일 쓰기 - 디렉터리 - 윈도우는 이를 폴더라고 부른다 경로 ; 절대 경로와 상대 경로 - 같은 디렉토리에는 같은 이름 파일이 존재 X / 다른 디렉토리에는 같은 이름 파일 존재 가능- 절대 경로 : 루트 디렉토리에서 자.. 2025. 3. 7. 운영체제 6 가상 메모리 연속 메모리 할당 ; 프로세스에 연속적인 메모리 공간을 할당하는 방식 스와핑 ; 현재 실행되지 않는 프로세스에 다른 프로세스를 적재하여 실행 -> 스왑 영역 ; 프로세스들이 쫓겨나는 보조기억장치 일부 영역 -> 스왑 아웃 ; 메모리에서 스왑영역으로 쫓겨나는 것 -> 스왑 인 ; 스왑 영역 프로세스가 다시 메모리로 옮겨 오는 것 메모리 할당 - 최초 적합 ; 빈 공간을 순서대로 검색하다고 적재 가능 공간 발견 시, 배치 - 최적 적합 ; 프로세스가 적재될 수 있는 가장 작은공간에 할당 - 최악 적합 ; 프로세스가 적재될 수 있는 가장 큰 공간에 할당 외부 단편화 ; 프로세들이 종료되기를 반복하면서 빈 공간들 발생 -> 큰 프로세스 적재가 어려운 작은 빈 공간 다수일 때 외부 단편화 해결 방.. 2025. 3. 6. 알고리즘 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. 이전 1 2 3 4 5 6 7 8 ··· 38 다음 반응형