문제 링크 https://www.acmicpc.net/problem/6064 시간, 공간 제한 시간 : 1초 공간 : 256mb 문제 접근 방향 - M, N 이 주어 졌을 때 마지막 해는 M과N의 최소 공배수 라는 것을 파악함 - 최소 공배수와 최대 공약수를 어떻게 구하는지 찾아 봄 // 유클리드 호제법을 사용한 최대 공약수 찾기 int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a%b); } // 최소 공배수 // a x b = gcb(a, b) x lcm(a, b) // lcm = a /gcb * b int lcm(a, b) { return a / gcb(a, b) * b; } - 라면 어떤 해를 M으로 나눴을 때 x가 남고 N으로 나눴을 때 ..

문제 링크 https://www.acmicpc.net/problem/1620 시간, 공간 제한 시간 : 2초 공간 : 256MB 문제 접근 방향 - key와 value 값을 저장하고 해당 자료구조를 탐색하여 적절한 값을 찾는 문제 - 단순히 배열을 자료구조로 선택할 경우 인덱스접근은 O(1)이지만 string을 찾기 위해서는 선형 탐색시 O(n)이된다. - 입력 최대 값이 100,000이고 선형 탐색을 통한 문제 해결시 전체 시간 복잡도는 O(n^2)으로 시간초과 발생한다. - string을 찾기 위해 O(logn)정도의 탐색 시간 복잡도가 필요하고 해당 시간 복잡도를 가진 map 자료 구조를 사용한다. - map은 key, value 한쌍을 저장할 수 있는 자료 구조이고 내부는 레드블랙트리라는 균형 이..

"운영체제 : 아주 쉬운 세가지 이야기"를 읽으면서 핵심 내용을 정리하였습니다. 이화여대 반효경 교수님의 운영체제 강의를 듣고 복습 차원에서 책 한권을 완독해 보고자 합니다. 잘못된 정보가 있다면 댓글 남겨주시면 감사하겠습니다! 주소 변환의 원리 운영체제는 효율성, 제어, 유연성을 추구하면서 주소변환을 하려고 한다. 효율성 : 레지스터, TLB 등의 하드웨어의 도움을 받는다 제어 : 하드웨어의 도움을 받아 응용프로그램이 자기 자신의 메모리 이외의 공간에 접근하지 못하도록 막는다. 유연성 : 프로그래머가 원하는 대로 주소공간을 사용할 수 있어야 한다 주소 변환의 핵심 기법은 하드웨어 기반 주소 변환이다. 이러한 주소 변환을 통해 가상 주소를 정보가 실제 존재하는 물리 주소로 변환한다. 즉, 프로그램의 모든..

"운영체제 : 아주 쉬운 세가지 이야기"를 읽으면서 핵심 내용을 정리하였습니다. 이화여대 반효경 교수님의 운영체제 강의를 듣고 복습 차원에서 책 한권을 완독해 보고자 합니다. 잘못된 정보가 있다면 댓글 남겨주시면 감사하겠습니다! 주소 공간의 개념 초기의 컴퓨터는 한번에 하나의 프로세스만 실행 할 수 있었기 때문에 아주 간단한 주소 공간을 가지고 있었다. 물리 메모리에 운영체제가 항상 상주하고 있었고 나머지공간은 프로세스를 위한 공간이었다. 하지만 사용자가 컴퓨터를 더 효과적으로 사용하기를 원하게 되면서 멀티 프로그래밍과 시분할 시스템이라는 개념이 등장하게 되었고 발전된 개념이 등장함에 따라 주소 공간의 개념도 발전할 필요가 생겼다. 운영체제는 메모리를 어떻게 가상화를 하여 프로세스에게 전용 메모리 공간이..

문제 링크 https://www.acmicpc.net/problem/2559 시간, 공간 제한 시간 : 1초 공간 : 128Mb 초기 문제 접근 방향 시간 복잡도 생각 - 일단 최대 들어 올수 있는 입력이 10,0000 이고 완전 탐색으로 모든 경우의 수를 구해 비교하는 것은 O(n^2) 이기 때문에 dp 풀이를 시도함 - ans[i] 값을 i번째 input에서 연속된 k일동안 온도의 합이라고 한다면 - ans[i] = ans[i - 1] - input[i - 1] + input[i + (k - 1)] 이라는 점화식을 도출함 - max_element를 사용하여 ans 범위안의 최댓값을 찾아냄 #include #include #include using namespace std; int main(void) ..

문제 링크 https://www.acmicpc.net/problem/9996 시간, 공간 제한 시간 : 1초 공간 : 128MB 초기 문제 접근 방향 문자열 파싱 문제라고 생각하고 c++ string 다루는 방법을 공부해야 겠다고 생각 string 내에서 특정 문자를 찾는 method : find string 내에서 특정 인덱스 범위의 문자열 추출 : substsr * 가 맨앞이나 맨뒤에 올수 없기 때문에 * 기준 앞뒤 문자열을 추출하여 저장 입력받은 문자열의 prev 부분과 last 부분을 저장한 문자열과 비교해서 같으면 ok 아니면 no 문제 접근 다른 방향

"운영체제 : 아주 쉬운 세가지 이야기"를 읽으면서 핵심 내용을 정리하였습니다. 이화여대 반효경 교수님의 운영체제 강의를 듣고 복습 차원에서 책 한권을 완독해 보고자 합니다. 잘못된 정보가 있다면 댓글 남겨주시면 감사하겠습니다! 멀티 레벨 피드백 큐(Multi-level Feedback Queue, MLFQ) 이전까지 스케줄러를 설계를 위해 먼저 핵심 가정들을 세우고 어떤 지표로 스케줄러를 평가할지 선정한 후 가정들을 하나씩 완화해 나가면서 스케줄러를 발전시켜 보았다. 아직 "각 작업의 실행 시간은 사전에 알려져있다" 는 가정을 완화 하지 못했고 이를 해결하는 멀티 레벨 피드백 큐라는 스케줄링 알고리즘에 대해 알아보고자 한다. 멀티레벨 피드백 큐 알고리즘의 목적은 아래와 같다. 반환시간의 최적화 응답시간..

스케줄링 정책 지금까지는 CPU 가상화를 구현하는 저수준의 기법인 “제한적 직접 실행”에 대해 알아 보았다. 제한적 직접실행을 통해 프로세스간 전환이 되는 과정(문맥 교환)을 이해하고 어떻게 운영체제의 주도하에 시스템(물리 장치들)을 관리 할 수 있는지 알 수 있었다. 그렇다면 운영체제는 어떤 원칙을 통해 프로세스를 전환할까? A 프로세스 실행중 타이머 인터럽트가 발생 했다. 수많은 프로세스중 어떤 프로세스로 전환할까? 운영체제는 특정한 원칙을 가지고 있고 이를 “스케쥴링 정책” 이라고 한다. 아래의 질문을 통해 어떻게 정책들이 발전해 왔는지 알아보고자 한다. 핵심 가정은 무엇일까? 어떤 평가 기준으로 정책을 평가할 수 있을까? 핵심 가정 아래의 가정들은 비현실적이긴 하지만 차차 가정을 줄여 나가면서 최..