본문 바로가기

학교 강의32

분할 정복 알고리즘 분할 정복 알고리즘 주어진 문제의 입력을 분할하여 문제를 해결하는 방식의 알고리즘- 분할한 입력에 대하여 동일한 알고리즘 적용해 해 계산- 이들의 해 취합하여 원래 문제의 해 얻음 분할 1이 되어 더 이상 쪼개질 수 없을 때까지 분할 : 총 분할 횟수=k일 때 정복 대부분의 문제는 분할만 해서 해를 구할 수 없다.부분해를 찾아 정복해야 하는데, 정복하는 방법은 문제에 따라 다르다.일반적으로 부분 문제들의 해를 취합하여 보다 큰 부분 문제의 해를 구한다.(정렬의 경우 혼자 있는 것만으로 정복 완료) 분할되는 부분문제의 수와 부분문제의 크기에 따라 다음과 같이 분류문제가 a개로 분할되고, 부분 문제 크기가 1/b로 감소하는 알고리즘1. a=b=2인 경우: 합병 정렬, 최근접 점의 쌍 찾기, 공제선 문제2.. 2025. 4. 23.
알고리즘 intro.. 알고리즘이란? - 문제를 해결하는 단계적 절차 또는 방법- 컴퓨터를 이용하여 해결할 수 있어야 한다.- 해를 출력 1. 정확성: 주어진 입력에 대해 올바른 해를 주어야 함2. 수행성: 알고리즘의 각 단계는 컴퓨터에서 수행 가능해야 함3. 유한성: 알고리즘은 유한 시간 내에 종료되어야 함4. 효율성: 알고리즘은 효율적일수록 그 가치가 높아진다. 최초의 알고리즘 : 유클리드의 최대공약수 알고리즘 2개의 자연수의 최대공약수는 큰 수에서 작은 수를 뺀 수와 작은 수와의 최대공약수와 같다. ex. 최대공약수(24, 14) = 최대공약수(10, 14)= 최대공약수(14-10, 10) = 최대공약수(4, 10)= 최대공약수(10-4, 4) = 최대공약수(6, 4)= 최대공약수(6-4, 4) = 최대공약수(2, 4).. 2025. 4. 23.
[Chapter 4] Process Management process를 생성하는 부분에 대해 중점적으로 볼 것임 process 생성(fork -> exec) : process 생성한다 = Parent process(원래 존재하는 process)가 children process(자식 프로세스)를 생성하는 것부모는 자식이 종료될 때까지 기다릴 수도 있고, 둘이 경쟁 관계일 수도 있다.But, parent process와 children process는 관계만 이럴 뿐 독립적으로 작동한다. 프로세스는 자원을 부모 프로세스로부터 받거나 운영체제로부터 받는다.- process는 thread와 달리 주소 공간 공유하지 않기 때문에 복사해줘야 함.- PCB도 별도로 만들어주고 부모꺼 복사.(code+data+stack 모두 복사)- 자식은 복사본에 자신의 프로그램 올림 .. 2025. 4. 19.
[Chapter 3] Process interrupt 별로 어떤 루틴을 처리해야 하는지 적어놓음 컴퓨터시스템 구조의 흐름 알고 있을 것 A, B, C프로그램이 있다고 할 때 세 프로그램이 돌아가면서 써야 공평함. round loading 방식 2번 interrupt가 들어오면 - 정해진 시간이 흐른 뒤 운영체제에게 제어권이 넘어가도록 인터럽트를 발생시킴 => 타이머에서 신호가 왔다고 판단- 타이머 값이 0이 되면 타이머 인터럽트 발생- CPU를 특정 프로그램이 독점하는 것으로부터 보호(round robing) -> 스케줄링=> time sharing을 구현하기 위해 널리 이용=> 현재 시간을 계산하기 위해서도 사용됨 Memory부분이 ISR CPU 로 들어가기 전 interrupt line에는 스케줄러가 존재.스케줄러에 따라 device.. 2025. 4. 19.

티스토리툴바