CS

[C++] STL 연관 컨테이너(associative container), set, multiset

set 세트set 컨테이너는 요소가 그 값에 따라 정렬되는 형태이다 즉, key라 불리는 원소(value)의 집합이다. 또한 이 원소들에 중복을 허용하지 않는다는 것이 특징이다.#include#includeusing namespace std;int main(){ set is; is.insert(55); is.insert(7); is.insert(23); is.insert(61); is.insert(7); is.insert(9); is.insert(58); set::iterator it; for(it = is.begin(); it != is.end(); it++) { cout 그냥 제멋대로 insert를 해도 알아서 정렬이 된다.​실제 트리구조는 항상 균형 이진 트리로 구성된다.이 ..

[C++] STL 연관 컨테이너(associative container), map, multimap

map, 맵 맵은 앞서 보았던 set과 거의 동일한 자료 구조다. 다만 차이점이 있다면 set은 key값만 저장하였고, map의 경우 key와 value로 구성되어 저장된다. 한마디로 key와 value 한 쌍을 이루어 자료를 보관할 수 있다. 그림은 추상적으로 map의 자료형태를 나타낸 것이다. 실제로 set과 동일하게 트리구조형태로 정렬되어 저장된다. #include #include using namespace std; int main() { map name; name.insert(pair(4, "kim")); name.insert(pair(1, "kim")); name.insert(pair(3, "lee")); name.insert(pair(5, "park")); name.insert(pair(4,..

[C++] STL list(리스트), 시퀀스 컨테이너

리스트는 대충 위그림 처럼 생겼다. 각 요소들은 앞 뒤 노드를 가지고 있어서 이중 연결 리스트로 구현된다. 리스트는 랜덤 액세스가 불가능하다. 즉, 중간에 3번째에 자료에 접근하려면 처음부터 두번째, 세번째 이런식으로 거쳐가야한다. 반면에 장점은 어떠한 위치의 자료를 삭제, 삽입 하더라도 그 속도가 빠르다는 것이다. 배열 구조와는 달리 연결된 링크만 끊어내고 다시 이어붙이는 작업만 하면 되기 때문이다. #include #include using namespace std; int main() { list alpha_list; for(char c = 'a'; c

[C++] 프로토타입 패턴, Prototype Pattern

원형이 되는 인스턴스를 사용하여 생성할 객체의 종류를 명시하고, 이렇게 만든 견본을 복사해서 새로운 객체를 생성합니다. (GoF의 디자인 패턴 169p) 위와 같이 같은 게임을 만든다고 생각해보자. 몬스터들은 영웅을 잡아먹기 위해 떼지어 다닌다. 이 몬스터 들은 스포너(spawner)를 통해 게임 레벨에 등장하는데, 몬스터 종류마다 스포너가 따로 있다. 게임에 나오는 몬스터마다 Ghost, Demon, Sorcerer 같은 클래스를 만들어보자. lass Monster { // 기타 등등.. }; class Ghost : public Monster {}; class Demon : public Monster {}; class Sorcerer : public Monster {}; 한 가지 스포너는 한 가지 몬..

[C++] 관찰자 패턴, 옵저버 패턴, Observer Pattern

객체 사이에 일 대 다의 의존 관계를 정의해두어, 어떤 객체의 상태가 변할 때 그 객체에 의존성을 가진 다른 객체들이 그 변화를 통지 받고 자동으로 업에이트될 수 있게 만듭니다. (GoF의 디자인 패턴 382p) 모델-뷰-컨트롤러(MVC) 구조를 쓰는 프로그램이 발에 차일 정도로 MVC패턴은 많이 사용되는데, 그 기반에는 관찰자 패턴이 있다. 업적 달성 좀비 100마리 죽이기 다리에서 떨어지기 위와 같은 특정 기준을 달성하면 배지를 얻을 수 있는데, 배지 종류는 수백 개가 넘는다고 하자. 업정 종류가 광범위하고 달성할 수 있는 방법도 다양하다 보니 깔끔하게 구현하기가 어렵다. 조금만 방심해도 업적 시스템 코드가 암세포처럼 구석구석 퍼져 나갈 것이다. '다리에서 떨어지기'는 어떻게든 물리 엔진이랑 연결해야..

[C++] 경량 패턴, Flyweight Pattern

공유를 통해 많은 수의 소립 객체들을 효과적으로 지원합니다. (GoF의 디자인 패턴 265p) '오래된 숲이 모습을 드러낸다.' 게임에서 흔히 볼 수 있는 설정이다. 일반적으로 이런 장면은 '경량패턴'으로 종종 구현한다. 숲에 들어갈 나무들 나무들이 화면을 가득 채운 빽뺵한 숲을 볼 때, 그래픽스 프로그래머는 1초에 60번씩 GPU에 전달해야 하는 몇백만 개의 폴리곤을 본다. 수천 그루가 넘는 나무마다 각각 수천 폴리곤의 형태로 표현해야 한다. 설사 메모리가 충분하다고 해도, 이런 숲을 그리기 위해서는 전체 데이터를 CPU에서 GPU로 버스를 통해 전달해야 한다. 나무마다 필요한 데이터는 다음과 같다. 줄기, 가지, 잎의 형태를 나타내는 폴리곤 메시 나무 껍질과 잎사귀 텍스처 숲에서의 위치와 방향 각각의..

[C++] 명령 패턴, 커맨드 패턴, Command Pattern

요청 자체를 캡슐화 하는 것입니다. 이를 통해 서로 다른 사용자(client)를 매개변수로 만들고, 요청을 대기시키거나 로깅하며, 되돌릴 수 있는 연산을 지원합니다. (GoF의 디자인 패턴 311p) 명령 패턴은 메서드 호출을 실체화 한 것이다. 실체화는 '실제하는 것으로 만든다'라는 뜻으로, 프로그래밍에서는 무엇인가를 '일급(first-class)'으로 만든다는 뜻으로 통한다. 즉, 어떤 개념을 변수에 저장하거나 함수에 전달할 수 있도록 데이터, 즉 객체로 바꿀 수 있다는 걸 의미한다. 다시 요약한다면 명령 패턴은 함수 호출을 객체로 감싼다는 것이므로 콜백을 객체지향적으로 표현한 것이다. 입력 키 변경 모든 게임에는 버튼이나 키보드등 유저 입력을 읽는 코드가 있고, 이런 코드는 입력을 받아서 의미있는 ..

이상적인 스레드 풀의 적정 크기에 대하여, 스레드 풀 크기 공식, 리틀의 법칙

스레드 풀의 크기를 적절히 설정해야 하는 이유 스레드를 생성하는 것은 비용이 드는 작업이다. 플랫폼마다 오버헤드는 다르지만, 스레드가 생성될 때 요청이 처리되는 지연시간(latency)과 OS에 의한 추가적인 처리 과정에 드는 시간 등 자원이 소모된다. 이러한 스레드 생성 비용을 줄이기 위해 스레드 풀이 필요하다. 스레드 풀에서 미리 생성해둔 스레드를 재사용함으로써 자원 낭비를 막을 수 있기 때문이다. 단, 스레드를 많이 생성해둔다고 그 스레드를 다 사용할 수 있는 것은 아니다. 쓸데없이 스레드를 많이 생성한다면 생성하는 데에 드는 자원과 비용이 낭비된다. 그렇다고 스레드를 부족하게 만들어둔다면 CPU 사용률이 낮아지게 될 것이다. 따라서 스레드 풀의 크기를 적절히 설정하는 것은 매우 중요한 일이다. 하..

CPU 스케줄링(Scheduling) 알고리즘 정리 및 요약 | FCFS, SJF, Round Robin

CPU 스케줄링이란 CPU 이용률을 극대화하기 위해서는 멀티프로그래밍(multiprogramming)이 필요하다. 하지만 만약 CPU core가 하나라면 한 번에 하나의 프로세스만 실행 가능할 것이다. 이때 필요한 것이 CPU 스케줄링이다. 즉, CPU 스케줄링은 언제 어떤 프로세스에 CPU를 할당할지 결정하는 작업이라고 할 수 있다. CPU 스케줄러(CPU Scheduler)와 선점형(Preemptive), 비선점형(non-preemptive) 스케줄링 CPU 스케줄러는 메모리에 있는 프로세스들 중 어떤 프로세스를 실행할지 선택하고 CPU를 할당해주는 역할을 한다. CPU 스케줄러는 프로세스들이 다음과 같은 상황에 있을 때 스케줄링을 결정한다. 실행(running) 상태에서 대기(waiting) 상태로..

멀티 스레드(Thread)의 장점과 문제점

쓰레드(Thread)의 개념 쓰레드는 프로세스를 여러 개로 나눈 조각과 갖다고 설명할 수 있다. 워드를 사용하는 경우를 예로 들자. 워드에서 글자를 입력하는 동안 파일을 주기적으로 자동저장하고, 내용을 프린터에 출력하고 있고, 입력하는 동안 자동으로 맞춤법 검사를 수행한다. 사용자의 입력을 받는 동안 행하는 이 모든 작업들은 각각의 쓰레드에 의해서 이루어진다. 글자를 입력 받는 쓰레드, 파일을 디스크에 저장하는 쓰레드, 출력할 내용을 프린터에 보내는 쓰레드, 입력하는 동안 맞춤법 검사를 수행하는 쓰레드 등이 있다. 즉, 워드라는 큰 프로세스 하나에 여러 개의 쓰레드가 모여있는 것이다. 실제로 프로세스는 하나의 어드레스 공간을 갖고 있고, 모든 응용 프로그램은 메인 응응 프로그램을 위한 하나의 쓰레드를 갖..