스터디 22

[C++] 절댓값 빠르게 구하기

C++ 에는 절댓값을 구할 수 있는 함수 abs 함수가 있습니다. abs - C++ Reference 12345678910111213 /* abs example */ #include /* printf */ #include /* abs */ int main () { int n,m; n=abs(23); m=abs(-11); printf ("n=%d\n",n); printf ("m=%d\n",m); return 0; } www.cplusplus.com 이 함수를 이용하게 되면 함수 호출에 대한 페널티를 받기 때문에 if 혹은 수의 특성을 이용해서 구해 시간을 줄일 수 있습니다. #define bit_abs(x) ~x + 1 정수형인 int, long long의 경우 왼쪽 끝의 비트가 부호를 나타내므로 0x80..

스터디/C++ 2021.02.20

[운영체제] Scheduling

스케줄링 스케줄링은 보통 멀티프로그래밍을 가능하게 하는 운영 체제의 동작 기법이며 어느 프로세스를 CPU에 얼마큼 할당할지를 결정하는 기법입니다. CPU 외에 자원을 할당할 때 스케줄링 작업을 거치기도 합니다. 스케줄링 용어 멀티프로그래밍 : CPU의 활용 극대화, 많은 프로그램이 동시에 실행 시간 공유 : 프로세스들이 자원을 공유 프로세스 스케줄링 : CPU에서 실행될 프로세스를 선택 Job Queue : 실행할 프로세스들의 PCB들의 모임 Ready Qeueu : 실행을 위해 모든 준비가 완료된 프로세스들의 PCB 모임 Device Qeueu(=waiting queue) : 자원을 사용 중이거나 사용하기 위해 기다리는 프로세스들의 모임, 각 장치들이 각자 고유의 큐를 가짐 스케줄링의 종류 장기 스케줄..

[운영체제] Context Switch

Context Switch Context란 CPU가 해당 프로세스를 실행하기 위한 정보로 지난 시간에 배운 PCB에 저장되어 있는 프로세스의 상태 정보를 의미합니다. 우리가 사용하는 컴퓨터에서 여러가지 프로그램을 동시에 동작할 수 있도록 만들어 주기 위해 현재 Context를 저장해 두고 다른 프로세스의 Context를 불러와 실행시켜 마치 실시간으로 여러 개의 프로그램이 동작하는 것처럼 보여줍니다. 이러한 일련의 과정을 Context Switch로 부릅니다. 보통 프로세스에 주어진 CPU 시간이 다 되거나 입출력 등을 위해 스스로 인터럽트를 발생, 우선순위가 높은 프로세스가 CPU를 점유하기 위해 인터럽트 요청을 했을 경우 발생합니다. Context Switch의 과정 프로세스 상태 변화에서 ready..

[운영체제] 프로세스

프로세스란? 프로세스는 실행 중에 있는 프로그램을 의미합니다. 프로그램은 디스크나 다른 저장소에 저장되어 있는 코드로 된 실행 가능판 것을 의미하고 프로세스는 프로그램을 실행시켜 메모리에 올려진 상태를 말합니다. 같은 프로그램을 여러 번 실행시키면 프로그램은 하나지만 프로세스는 여러 개가 생깁니다. 프로그램이 동작하러면 운영체제가 프로세스들을 관리하기 위하여 각 프로세스마다 정보를 매깁니다. 이 정보에는 PC, 레지스터, 메모리, 프로세스 IP, 부모 프로세스, 프로세스의 현재 상태 등이 있습니다. 프로세스의 메모리 형태 프로세스는 자기만의 고유 메모리를 가지고 있습니다. 이 고유 메모리는 논리적으로 형성되어 있으며 각 영역에 해당되는 정보들이 실제 물리적 메모리 공간에 할당이 됩니다. Stack 영역(..

[운영체제] OS 디자인과 구현

운영체제는 사용될 환경, 자원 등에 의해 다르게 디자인됩니다. 일반 사용자들이 많이 사용하는 윈도우, 개발자들이 많은 기능을 사용하기 위하여 리눅스 등 사용자에 따라 바뀌기도 합니다. 디자인의 목적 : 보통 관점에 따라 2가지로 분류합니다. 사용자 입장 : 사용하기 편함, 배우기 쉬움, 빠른 속도, 신뢰성 등 시스템 입장 : 적용하기 쉬움, 호환성, 유지보수, 유연성, 장애 복구 능력 등 목적은 운영체제를 설계하기 나름이므로 환경, 자원 등에 맞춰 적절하게 맞추도록 합니다. 디자인 시 사용하는 2가지 용어가 있습니다. Mechanisms : 수행하는 방법 Policy : 수행에 의해 나오는 결과 이렇게 2가지로 나누는 이유는 매커니즘을 통해 결과를 만들어 내는 구조는 잘 변하지 않지만 만들어 내는 결과물..

[운영체제] 시스템 콜과 인터럽트

시스템 콜 정의를 보면 운영체제의 커널이 제공하는 서비스에 대해, 응용 프로그램의 요청에 따라 커널에 접근하기 위한 인터페이스라고 합니다. 간단하게 말하자면 운영체제 서비스를 접근하기 위한 유일한 수단입니다. 프로그램을 실행하거나 프로그램이 컴퓨터 자원을 사용하기 위해서는 시스템 콜을 통해 커널에 자원 사용을 요청을 해야 합니다. 시스템 콜의 주요 세 가지 기능은 다음과 같습니다. 사용자 모드에 있는 응용 프로그램이 커널의 기능을 사용할 수 있도록 한다. = 운영체제 서비스에 접근을 할 수 있게 해 줍니다. 시스템 호출을 하면 사용자 모드에서 커널 모드로 바뀐다. 커널에서 시스템 호출의 작업이 끝나면 사용자 모드로 돌아간다. 여기서 말하는 사용자 모드와 커널 모드의 의미를 조면 사용자 모드는 사용자가 프..

[운영체제] Intro

운영체제란? 운영체제의 정의를 보면 시스템 하드웨어를 관리, 응용 소프트웨어를 실행하기 위하여 하드웨어 추상화 플랫폼, 공통 시스템 서비스를 제공하는 시스템 소프트웨어입니다. 간단하게 풀어 설명하자면 하드디스크, CPU, GPU 등 하드웨어를 관리하고 사용자가 이를 활용할 수 있게 해 주며, 사용자가 작성한 프로그램이 하드웨어를 사용하고, 시스템 서비스 등을 활용할 수 있게 만들어주는 하나의 큰 소프트웨어입니다. 주요 목적은 다음과 같습니다. 사용자가 프로그램을 쉽게 작성, 실행할 수 있도록 도움을 줍니다. 컴퓨터 시스템을 효율적으로 관리, 사용할 수 있도록 합니다. 하드웨어, 장치 등을 효율적으로 관리, 사용할 수 있도록 합니다. 사용자, 응용 소프트웨어가 시스템 서비스를 활용할 수 있게 해 주며, 하..

[자료구조] Lazy Propagation

세그먼트 트리 : latter2005.tistory.com/28?category=946518 [자료구조] 세그먼트 트리 자료구조 설명 : www.acmicpc.net/blog/view/9 세그먼트 트리 (Segment Tree) 문제 배열 A가 있고, 여기서 다음과 같은 두 연산을 수행해야하는 문제를 생각해봅시다. 구간 l, r (l ≤ r)이 주어졌을 때, A[l] + A.. latter2005.tistory.com 세그먼트 트리에서 자주 업데이트가 발생할 때 이를 더욱 효율적으로 처리하기 위한 알고리즘입니다. 간단하게 설명하자면 구간 a~b의 값을 변경할 때 모든 트리구조, 배열을 변경하지 않고 접근 시 차근차근 변경해 나가겠다는 의미입니다. 예시를 들어 설명하도록 하겠습니다. ary = {0, 1,..

[C++] struct, pair 비교

활용 문제 : www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 백준 문제와 테스트 케이스를 이용해서 속도 비교를 해 보았습니다. pair의 경우 객체 메서드 생성에 의해 조금 느린 것을 볼 수 있지만 거의 차이가 보이지 않아 간단한 벤치마킹 코드를 작성해서 비교해 보았습니다. 백준 테스트 케이스를 얻을 수 없어서 std::sort 함수를 통해 성능을 비교하도록 하겠습니다. sort 함수에서 2차원 배열을 사용하기 위해서는..

스터디/C++ 2020.12.17

[자료구조] 세그먼트 트리

자료구조 설명 : www.acmicpc.net/blog/view/9 세그먼트 트리 (Segment Tree) 문제 배열 A가 있고, 여기서 다음과 같은 두 연산을 수행해야하는 문제를 생각해봅시다. 구간 l, r (l ≤ r)이 주어졌을 때, A[l] + A[l+1] + ... + A[r-1] + A[r]을 구해서 출력하기 i번째 수를 v로 바꾸기. A[i www.acmicpc.net 백준 사이트에서 설명을 잘해 두었습니다. 배열에서 부분합, 부분 최대/최소 등 범위 참조 연산이 자주 일어날 때 자주 사용하는 자료구조입니다. 미리 배열에 대하여 세그먼트 트리를 생성해 둔 후 미리 계산해둔 값을 참고하여 O(n)의 시간을 O(log n) 만큼으로 줄여줍니다. 일반적으로 세그먼트 트리에서 노드들은 다음과 같은..