📝 Computer Science

알고리즘 성능 분석

알고리즘을 평가하는 데 있어 수행 시간과 메모리 사용량을 평가기준으로 두는데, 수행 시간에 해당되는 것이 시간 복잡도, 메모리 사용량에 해당되는 것이 공간 복잡도이다. 보통 알고리즘의 성능 분석은 복잡도를 계산하여 점근적 표기법으로 나타낸다. 점근적 분석 입력 값의 개수에 따라 알고리즘의 수행 시간을 바탕으로 알고리즘의 효율성을 평가한다. 1) 빅오 표기법 O 점근적 상한선으로 점근적 증가율이 f(N)을 넘지 않는 모든 함수들의 집합이다. 즉, 최고 차항의 차수가 f(N)과 같거나 더 작은 함수들의 집합이다. f(N)

캐시 메모리(Cache Memory)

캐시 메모리 주기억장치에 저장된 내용의 일부를 임시로 저장해두는 기억장치로 속도가 빠른 장치와 느린 장치 간의 속도차에 따른 병목 현상을 줄이기 위한 범용 메모리이다. 1. 지역성(Locality) 프로세스가 실행되는 동안 주기억장치를 참조할 때 일부 페이지만 집중적으로 참조하는 성질로 캐시의 적중률(Hit rate)을 극대화시키기 위해 지역성의 원리를 사용한다. 시간 지역성: 최근에 참조된 주소의 내용은 곧 다음에 다시 참조되는 특성 공간 지역성: 대부분의 실제 프로그램이 참조된 인접한 주소의 내용이 다시 참조되는 특성 2. 캐싱 라인(Caching line) 캐시에 데이터를 저장할 때, 데이터의 메모리 주소 등을 기록해 둔 태그를 달아 기록한다. 이때 이러한 태그들의 묶음을 캐싱 라인이라 한다. 캐싱..

[C++] 비트마스크(BitMask)

비트마스크(BitMask) 집합 요소들의 구성 여부를 표현할 때 유용한 테크닉이다. 기본 원리 {1, 2, 3, 4, 5}라는 집합이 있고 이 집합의 부분집합을 구해야 한다. {1}, {2}, ..., {1, 2}, ..., {1, 2, 5}, ..., {1, 2, 3, 4, 5} 물론 간단히 반복문을 통해 경우의 수를 구할 수 있다. 하지만 비트 마스킹을 하면 각 요소를 인덱스처럼 표현하여 효율적인 접근이 가능하다. {1, 2, 3, 4, 5} → 11111 {2, 3, 4, 5} → 11110 {1, 2, 5} → 10011 {2} → 00010 1) 삽입 i번 째 비트 값을 1로 변경하려고 한다. 이때 OR 연산을 활용한다. i = 3일 때, 10101 | (1 machine[i][j]; cin >..

MVC 패턴

MVC(Model-View-Controller) 패턴 소프트웨어에서 매우 널리 사용되는 디자인 패턴으로 크게 모델, 뷰, 컨트롤러로 구조화한다. 비즈니스 로직과 프레젠테이션 로직을 나누어서 처리한다. 쉽게 말해 연산을 하는 업무와 사용자가 보는 화면을 만드는 업무를 분리해서 처리하는 방식이라고 볼 수 있다. 코드의 양이 많아져도 유지 보수가 편하고 확장이 용이하다. 여러 개의 뷰를 만들 수 있으므로 대화형 애플리케이션에 적합하다. 대화형 애플리케이션이란 사용자의 요구가 발생하면 시스템이 이를 처리하고 반응하는 소프트웨어를 말한다. 1. 구성 요소 1) 모델(Model) 응용 프로그램에서 데이터를 처리하는 부분이다. DB에 연결하고 데이터를 추출하거나 저장, 삭제, 갱신 등의 작업을 수행한다. 내부 비즈니..

싱글톤 패턴(Singleton Pattern)

싱글톤 패턴(Singleton Pattern) 전역 변수를 사용하지 않고 인스턴스를 하나만 생성하도록 하며 생성된 인스턴스를 어디서든 사용할 수 있는 패턴이다. 인스턴스를 여러 개 만들면 자원을 낭비하거나 버그를 발생시킬 수 있으므로 오직 하나만 생성한다. 구현 하나의 인스턴스만 유지하기 위해 생성자에 private 접근 제어자를 지정하고 유일한 단일 객체를 반환할 수 있도록 정적 메소드를 지원해야 한다. #include using namespace std; // 다이나믹 싱글톤(Dynamic Singleton) // 게으른 초기화: 싱글톤을 실제로 필요로 할때까지 초기화를 미룬다. class DynamicSingleton { private: DynamicSingleton() {} static Dynam..

디자인 패턴(Design Pattern)

디자인 패턴(Design Pattern) 소프트웨어를 설계할 때 특정 맥락에서 자주 발생하는 고질적인 문제들이 또 발생했을 때 재사용할 할 수 있는 훌륭한 해결책이다. 각기 다른 소프트웨어 모듈이나 기능을 가진 다양한 응용 소프트웨어 시스템들을 개발할 때도 서로 간에 공통되는 설계 문제가 존재하며 이를 처리하는 해결책 사이에도 공통점이 있다. 이러한 유사점을 패턴이라 한다. 패턴은 공통의 언어를 만들어주며 팀원 사이의 의사소통을 원활하게 해주는 아주 중요한 역할을 한다. GoF 디자인 패턴 23가지의 디자인 패턴을 정리하고 각각의 디자인 패턴을 생성, 구조, 행위 3가지로 구분했다. 생성 패턴: 객체 생성에 관련된 패턴으로 객체의 생성과 조합을 캡슐화해 특정 객체가 생성되거나 변경되어도 프로그램 구조에 ..