본문 바로가기
알고리즘 분석 | 최악의 경우, 평균, 최상의 경우 Worst cases, Average cases, and Best cases 알고리즘을 분석 할 때 세 가지 경우로 나눌 수 있다. 워스트 케이스, 에버리지 케이스, 베스트 케이스 세 가지가 있다. 선형 탐색(Linear search)을 예로 들어보자. 최악의 경우 최악의 경우는 알고리즘이 실행되는 시간의 상한을 결정한다. 프로그램을 실행 할 때 연산이 수행되는 횟수가 최대가 되는 경우이다. 선형 탐색의 경우 찾으려는 원소가 배열에 존재하지 않거나 배열의 끝에 존재하는 경우이다. 배열에 찾으려는 원소가 존재하지 않으면 배열의 전체 원소와 모두 비교를 한다. 따라서 선형 탐색의 최악의 경우 시간 복잡도는 $\large \theta (n)$ 이다. 평균적인 경우 평균적인 경우를 계산하는 방법은 다음과 같다... 2019. 5. 23.
알고리즘 분석 방법 | 점근적 분석 성능(Performance) 분석을 하는 이유 프로그램을 작성할 때 고려해야하는 사항이 많다. 사용자 편의성이 좋아야하며, 모듈성, 보안, 유지 관리 등이 중요하다. 이 뿐만 아니라 성능도 중요하다. 그렇다면 성능은 왜 중요한 것일까? 답은 간단하다. 성능이 좋아야 앞서 언급한 것들을 이룰 수 있다. 성능을 공부하는 이유 중 또 다른 하나는 재미있기 때문이다. 조금 더 실용적인 예를 들어보자. 만약 워드나 한글 같은 텍스트 에디터가 100페이지를 로드하는데 한시간이 걸린다면 어떨까? 동영상을 재생하기 위해 1시간이 걸린다면 어떨까? 이러한 경우 퍼포먼스, 즉 성능은 필수적이다. 성능 분석은 어떻게 할 수 있을까? 하나의 문제 혹은 태스크를 풀 수 있는 두 가지 알고리즘이 있다고 생각해 보자. 어느 것이 .. 2019. 5. 22.
티스토리에 Github Gist 이용하여 소스코드 snippet 붙여 넣기 Github Gist 사용하기 2 3 4 5 6 Hello Gist!! 확장자 명을 .c .cpp .py .java 와 같이 맞추어 주면 코드 하이라이트 기능이 자동으로 적용된다. 진짜 마지막 테스트... 2019. 5. 17.
C++ STL Maps 사용하는 방법 C++ STL Maps Maps은 associative container이다. key value와 mapped value의 조합으로 구성되는 원소를 저장하는 associative container이다. std::map 선언하기 map m; // creates a map m where key_type is of type string and data_type is of type int map의 길이 int length = m.size(); // gives the size of the map map에 삽입하기 m.insert(make_pair("hello", 9)); // here the pair is inserted into the map where the key is "hello" and the value.. 2019. 4. 23.
C++ STL Sets 사용하는 방법과 멤버 함수 C++ STL Sets 집합은 C++ 표준 템플릿 라이브러리 중 하나이다. 집합(Sets)은 특정한 순서로 특정 원소를 저장하는 컨테이너(container)이다. 주로 사용되는 함수들은 아래와 같다. 선언은 다음과 같이 한다. sets s; // creates a set of integers집합의 크기는 다음과 같이 구할 수 있다. int length = s.size(); // gives the size of the set.집합에 새로운 원소는 insert() 함수를 이용한다. s.insert(x); // inserts an integer x into the set s원소를 지울 때는 erase() 함수를 이용한다. s.erase(val); // erases an integer val from the s.. 2019. 4. 23.
C++ Lower Bound-STL 사용하는 방법 C++ STL Lower Bound 사용하기 lower_bound( begin(), end(), value)[ begin(), end() ) 범위 중에서 value 값이 나타나는 하한을 반환한다. 만약 value가 없다면, value보다 큰 값중에서 가장 작은 값을 반환한다. 즉, value 와 같거나 큰 값이 처음 나타나는 위치를 반복자로 반환한다. 예제 1 #include #include #include using namespace std; int main() { vector v; // vector v.push_back(10); v.push_back(20); v.push_back(30); v.push_back(22); //sort(v.begin(), v.end()); vector::iterator i.. 2019. 4. 23.
C++ 반복자란 무엇인가? 반복자 iterator의 개념 반복자는 포인터와 상당히 비슷하다. 컨테이너에 저장되어 있는 원소들을 참조할 때 사용한다. 포인터와 비슷한 객체이다. 반복자는 컨테이너에 저장된 원소를 순회하고 접근하는 일반화된 방법을 제공한다. 반복자는 컨테이너와 알고리즘이 하나로 동작하게 묶어주는 인터페이스 역할을 한다. 알고리즘마다 다른 방식으로 컨테이너를 순회할 수 있기 때문에 반복자에도 여러 종류가 있다. An iterator is an object that can "iterate" (navigate) over elements. - The C++ Standard Library 반복자는 컨테이너 내부의 원소(객체)를 가리키고 접근할 수 있어야 한다. 반복자는 다음 원소로 이동하고 컨테이너의 모든 원소를 순회할 수 있.. 2019. 4. 23.

티스토리툴바