FuJi Graphics

[#12] Binary Search : 이진 탐색

이진 탐색 이진 탐색은 정렬된 데이터 집합에서 사용할 수 있는 고속 탐색 알고리즘중 하나이다. 이진 탐색 순서 데이터 집합의 중앙에 있는 요소를 선택한다. 중앙 요소의 값과 찾고자 하는 목표 값을 비교한다. 중앙 요소값보다 작으면 중앙 기준으로 왼쪽, 그 반대면 오른쪽을 재 탐색한다. 데이터 집합의 마지막 인덱스까지 1~3번을 반복한다. 코드 백준에 있는 다음 문제를 이진 탐색으로 풀었다. 코드 #include #include #include using namespace std; void Input(int& v) { cin >> v; } void Output(int& v) { cout n; vector card(n); for_each(card.begin(), card.end(), Input); // 숫자..

[#3] STL :: iterator (이터레이터), for_each, istream_iterator, ostream_iterator

iterator 선언 및 초기화 // #1 std::vector::iterator pd; // 이터레이터 선언 std::vector scores; // 벡터 선언 pd = scores.begin(); // 이터레이터 pd는 scores의 시작주소를 가리킨다 *pd = 22; // 이터레이터가 가리키고 있는 주소의 값을 22로 설정한다. ++pd; // 인덱스를 다음칸으로 이동한다 // #2 std::vector::iterator pd = scores.begin() // 선언과 동시에 초기화 // #3 auto pd = scores.begin() // C++11 자동 형변환 for문 루프 및 Range 루프 // #1 이터레이터를 활용한 출력 for문 for(pd = score.begin(); pd != ..

[#20] 교착 상태(dead lock) : 교착 상태 필요조건, 해결 방법, 다중 자원과 교착 상태 검출 -요약-

교착 상태란? 2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태를 말한다. 컴퓨터 시스템에서 교착 상태는 시스템 자원, 공유 변수(또는 파일), 응용 프로그램 등을 사용할 때 발생할 수 있다. 자원 할당 그래프 프로세스가 어떤 자원을 사용중이고 어떤 자원을 기다리고 있는지를 방향성이 있는 그래프로 표현한 것이다. 자원 할당 그래프를 사용하면 자원의 할당과 대기 상태를 한눈에 파악할 수 있다. 교착 상태 필요조건 상호 배제 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 한다. 비선점 한 프로세스가 사용 중인 자원은 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 한다. 점유와 대기 프로세스가 어떤 자원을 할당받은 상태..

[#19] 프로세스의 동기화 : 프로세스간 통신(IPC), 임계구역, 임계구역 해결법, 파일, 파이프, 소켓 프로그래밍 -요약-

프로세스간 통신의 개념 프로세스가 다른 프로세스와 데이터를 주고받는 것을 말하며 프로세스 내부 데이터 통신, 프로세스 간 데이터 통신, 네트워크를 이용한 통신이 있다. (원격 프로시저 호출: Remote Procedure Call, RPC도 통신의 한 종류이다.) 프로세스 간 통신의 분류 분류 방식 종류 예 통신 방향에 따른 분류 양방향통신 일반적 통신, 소켓 반양방향 통신 무전기 단방향 통신 전역 변수, 파일, 파이프 통신 구현 방식에 따른 분류 대기가 있는 통신(동기화 통신) 파이프, 소켓 대기가 없는 통신(비동기화 통신) 전역 변수, 파일 프로세스 간 통신의 종류 전역 변수를 이용한 통신 공동으로 관리하는 메모리를 사용하여 데이터를 주고 받는 것 파일을 이용한 통신 저장장치에 파일을 읽고 쓰는 방법..

[#2] header <algorithm> - sort 함수

sort 함수 원형 // #1 templatevoid sort(RandomAccessIterator first, RandomAccessIterator last); // #2 templatevoid sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp); #1 배열의 시작 주소, iterator의 begin(), 배열의 끝 주소인 end()를 매개변수로 받는다. #2 iterator의 begin, end와 추가로 Compare 함수를 매개변수로 넘겨받는다. Compare 함수란? Sort 라이브러리의 참 거짓 관계를 재정의하는 사용자 정의 함수이다 오름차순 정렬 // 2차원 벡터 선언 vector v(5, vector(2)); /..

[#18] CPU 스케줄링 :: Q/A

시스템 내 전체 프로세스의 수를 조절하는 것으로, 장기 스케줄링 또는 작업 스케줄링이라 불리는 스케줄링 수준은 무엇인가? 더보기 고수준 스케줄링 전체 시스템의 부하를 고려하여 작업을 시작할지 말지를 결정하는 단계. 시스템의 전체 프로세스 수가 결정된다. 이를 멀티프로그래밍 정도(degree of multiprogramming)이라 한다. 어떤 프로세스에 CPU를 할당하고 어떤 프로세스를 대기 상태로 보낼지 등을 결정하는 스케줄링 수준은 무엇인가? 더보기 저수준 스케줄링 실제로 작업이 이루어지는 단계이며, 프로세스를 실행 상태로 옮기기도 하고, 대기 상태로 보내기도 하며, 타임 아웃으로 준비 상태로 돌려보내기도 한다. 어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 ..

[#2] STL :: Vector Template Class

목차 초기화 인터페이스 vector 초기화 vector 템플릿 객체를 생성하려면 헤더 파일을 추가해야한다. 그리고 사용할 데이터형을 나타내기 위해 통상적으로 type 표기를 사용한다. vector 템플릿은 동적 할당을 이용해 초기화한다. allocator allocator는 메모리 관리에 사용되는 클래스다. STL 컨테이너 템플릿의 vector 템플릿의 원형은 다음과 같다. template class vector { ... 만약 vector 객체를 초기화할 때 템플릿 매개변수를 위한 값을 생략하게 되면, vector는 allocator 클래스를 디폴트로 설정한다. 코드 설명 vector v; 비어있는 vector v를 생성한다 vector v(5); 디폴트값 (0)으로 초기화 된 5개의 원소를 가지는 v..

[#1] 표준 템플릿 라이브러리(STD; Standard Template Library)

표준 템플릿 라이브러리(STL; Standard Template Library)는 컨테이너(container), 이터레이터(iterator), 함수 객체(function object), 알고리즘(algorithm)을 나타내는 템플릿들의 집합을 제공한다. 컨테이너(container) 배열과 같이 여러 개의 값을 저장할 수 있는 구성 단위를 뜻한다. STL container는 동질적(homogeneous)이다 즉, 그들은 같은 종류의 값들을 저장한다. 알고리즘(algorithm) 배열을 소트하거나 리스트에서 특정한 값을 검색하는 것과 같은 특별한 작업을 수행하기 위해 사용하는 방법이다. 이터레이터(iterator) container안에서 위치를 옮길 수 있도록 도와주는 객체들이며 포인터의 일반화이다. STL..