본문 바로가기

Algorithm

 (26)
[C++] 이분 탐색(Binary Search) - lower_bound, upper_bound 핵심 요약 이진 탐색이라고도 불리는 이 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 그러므로, 배열 내부의 데이터가 정렬이 되어있어야 한다. 시간 복잡도는 logN이다. STL 라이브러리 사용 #include //stl 라이브러리 사용을 위함. lower_bound(begin(), end(), value); upper_bound(begin(), end(), value); lower_bound란? begin()에서 end()의 범위 중에서 value값 이상이 나타나는 가장 작은 이터레이터를 반환하는 것입니다. value가 존재 하지 않는다면 value보다 큰 값 중 가장 작은 값이 나타나는 이터레이터를 반환합니다. algorithm 헤더 안에 존재합니다. v..
[C++] 이분 탐색(Binary Search) - while문 핵심 요약 이진 탐색이라고도 불리는 이 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 그러므로, 배열 내부의 데이터가 정렬이 되어있어야 한다. 시간 복잡도는 logN이다. 코드로 구현 변수 3개(start, end, mid)를 사용하여 탐색한다. 주로 while문을 통해 구성된다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다. [예제] N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 key라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 찾을 경우 1을 출력, 없을 경우 0을 출력하라. #include #include #include using namespace std; int n..
애드혹(AD-HOC) 핵심 요약 해당 문제를 풀기 위해서 잘 알려진 정교한 알고리즘을 적용하지 않고 해결할 수 있는 유형 즉, 하드 코딩(hard-coding)을 뜻함. 구현, 그리디, 수학 등의 유형의 문제들 이 유형의 문제는 창의적인 아이디어가 필요하다!
[C++] 페어(PAIR) 핵심요약한 공간에 2개의 값을 저장할 수 있게 해주는 클래스2개의 값이 묶여서 이동하면 좋겠다고 생각할 때 사용하면 좋다. 헤더파일#include //1번 방법#include //2번 방법, vector 헤더파일 안에 유틸리티가 들어있다.pair 변수명; 데이터 생성 및 참조pair p;p = make_pair(data1, data2); // 첫 번째 방법p = {data1, data2}; // 두 번째 방법p.first //첫 번째 data값 = data1p.second //두 번째 data값 = data2 정렬 관련 tip#include //STL의 sort함수를 사용하기 위해//first값을 기준으로 할 때sort(vec.begin(), vec.end()); //vec이라는 자료구조의 정..
[C++] 데큐(DEQUE) 핵심요약 앞뒤로 원소의 삽입, 삭제가 가능한 자료구조 원형큐 관련 문제에서 유용 기본 정의 vector와 같이 배열 기반의 구조이지만 vector의 단점을 보완 메모리가 부족할 때 새로운 메모리 블럭을 할당 ⇒ 삽입 시 성능 저하 X 헤더파일 및 선언 #include deque 변수명; 생성자 deque dq; //비어있는 deque dq를 생성 deque dq(10); //default(0) 값으로 초기화 된 10개의 원소를 가진 dq를 생성 deque dq(10, 4); //4의 값으로 초기화된 10개의 원소를 가진 dq를 생성 deque dq2(dq1); //dq1을 복사한 dq2를 생성. 삽입 및 삭제 관련 멤버함수 dq.clear(); //모든 원소를 제거합니다. dq.push_front(), ..
[C++] 우선순위 큐(PRIORITY_QUEUE) 핵심 요약우선 순위에 따라 정렬된 queue이다.heap으로 구현되어 있어, 특정 원소를 push할 때 생기는 정렬의 시간 복잡도는 logN에 실현된다.헤더파일 및 선언#include //라는 헤더파일을 따로 사용하지 않는다.priority_queue 변수명; //선언한 자료형 변수들을 비교함수에 따라 정렬.priority_queue, greater> pq; //올림차순, 가장 앞에 제일 작은 수가 오게된다.priority_queue pq; //내림차순, 가장 앞에 제일 큰 수가 오게된다.관련 함수(삽입, 삭제 등)priority_queue pq;pq.push(변수); //변수를 넣는다.pq.pop(); //맨 앞의 원소를 제거.pq.top(); //맨 앞의 원소를 반환.pq.empty(); //비어있..
[C++] 스택(STACK) 핵심요약 FILO(First In Last Out) 구조 괄호 문제와 같이 짝을 이루는 입력이 있을 때 주로 사용됨. 사용법 #include stack 변수명; //선언 문자열(string)? c++에서의 문자열(string)도 스택과 동일하게 사용이 가능하다.
[C++] 자료형에 따른 숫자 범위 핵심요약 1바이트 char: -128 ~ 127 unsigned char: 0 ~ 255 2바이트 short: -32,768 ~ 32,767 unsigned short: 0 ~ 65,535 4바이트 int, long: -2,147,483,648 ~ 2,147,483,647 unsigned int, unsigned long: 0 ~ 4,294,967,295 8바이트 long long: -9,222,372,036,854,775,808 ~ 9,222,372,036,854,775,807 unsigned long long: 0 ~ 18,446,744,073,709,551,615

티스토리툴바