본문 바로가기

전체 글

 (291)
2.2 알고리즘 분석 2.2 알고리즘 분석 알고리즘을 실행 시, 필요한 자원 예측 메모리 통신대역 하드웨어 계산시간 RAM 모델 단일 프로세서 + RAM 캐시나 가상메모리는 고려하지 않는다. 명령어는 동시에 수행되지 않고 차례로 하나씩 실행된다. 명령어 한 행당 상수시간 소요 산술연산(덧셈, 뺄셈, 곱셈, 나눗셈, 나머지, 내림, 올림) 데이터이동 연산(읽기, 저장하기, 복사하기) 제어 연산(조건 분기, 무조건 분기, 함수 호출과 리턴) 입력크기는 수행시간에 비례한다. 최악의 경우 : 크기가 n인 입력 중 가장 오래걸리는 수행 시간 평균적인 경우 : n개의 숫자 무작위 하지만 무엇이 평균적인 입력인지 불확실한 경우, 랜덤화된 알고리즘을 사용한다. 연습문제 2.2-1 θ(n³) 2.2-2 for s = 1 to A.length..
백준, 이모티콘 백준, 이모티콘 문제 https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 풀이 set 자료구조를 이용해 방문표시를 해 이미 계산한 적있는 (screen, clipboard)는 또 계산하지 않도록 했다. 계산하는 순간 시간이 늘어나므로! (문제에서 원하는 건 최소 시간이므로) 또한 작업 순서를 순차적으로 하기 위해 queue 자료구조에에 작업 순서 저장해 popleft해가면서 차례로 계산해 나갔다. 분류 30분동안, dp로 접근해 규칙을 찾아내려고 애..
제한적 직접 실행 원리 제한적 직접 실행 원리 Limited Direct Execution 운영체제 개발자들은 프로그램을 빠르게 실행하기 위해 이 기법을 개발했다. 프로그램을 CPU상에서 그냥 직접 실행시키는 것! feat. user mode, kernel mode, system call 📌 배운 것 CPU 가상화 한 프로세스를 잠시 동안 실행하고 다른 프로세스를 또 잠깐 실행하고.. CPU 시간을 나누어 쓰므로써 가상화를 구현 해결해야 할 문제 성능저하, 시스템에 과중화 오버헤드 주지 않아야 함. 제어 문제, 자원을 효율적으로 관리 OS는 제어권을 유지하면서 성능 저하가 없도록 하는것이 궁극적인 목표이다. 제어권을 상실하게 된다면 어떤 문제가 발생할까? 한 프로세스가 영원히 실행을 계속해 컴퓨터를 장악 접근해서는 안되는 정보..

티스토리툴바