[C_C++]이론 공부

[알고리즘 공부] 힙 정렬, 계수 정렬 (C언어)

힙 정렬 힙을 이용해 데이터를 정렬 전체 시간 복잡도: O(N*logN) - 데이터 개수가 N개일 때 N/2개의 데이터에만 힙생성 알고리즘(Heapify)를 적용해주면 최대힙이 만들어짐. 사실상 O(N*logN) ≓ O(N/2*logN) => 병합 정렬과 퀵 정렬만큼 빠른 정렬 알고리즘. 고급 프로그래밍 기법으로 갈수록 힙의 개념이 자주 등장하기 때문에 반드시 알고 넘어가야 함. 힙 트리 구조를 이용하는 정렬 방법. 병합정렬과 달리 별도로 추가적인 배열이 필요하지 않기 때문에 메모리 측면에서 몹시 효율적. 항상 O(N*logN)을 보장할 수 있다는 점에서 강력한 정렬 알고리즘. 이론적으로는 퀵/병합 정렬보다 효율적이라고 할 수 있음. 하지만 속도만 가지고 비교하면 평균적으로 퀵 정렬이 더 빨라서 힙 정렬..

[알고리즘 공부] sort (C++ STL)

C++ STL ❯❯ sort() #include #include using namespace std; int main() { int a[10] = {9,3,5,4,1,10,8,6,7,2}; sort(a, a+10);// 메모리 주소를 넣어주면 됨 for (int i = 0; i 내림차순 bool compare1(int a, int b) { return a > b; } int main() { int a[10] = {9, 3, 5, 4, 1, 10, 8, 6, 7, 2}; sort(a, a + 10, compare1);// 1 2 3 4 5 6 7 8 9 10 sort(a, a + 10, compare2);// 10 9 8 7 6 5 4 3 2 1 ..

[알고리즘 공부] 정렬 - 선택/버블/삽입/퀵 정렬 (C언어)

선택 정렬 가장 작은 것을 선택해 앞으로 보낸다. 시간복잡도: n(n+1)/2 => O(N^2) => 다른 알고리즘과 비교했을 때 비효율적인 편 #include int main() { int i, j, min, idx, tmp; int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9}; for (i = 0; i array[j]) { min = array[j]; idx = j; } } tmp = array[idx]; array[idx] = array[i]; array[i] = tmp; } for (i = 0; i < 10; ++i) { printf("%d ", array..

[C++ STL] set 사용법 위주 공부

set 은 노드 기반 컨테이너로, 이진 균형 트리다. 때문에 삽입, 삭제, 검색 등의 작업이 용이하다. 숫자든 문자든 원소의 중복을 알아서 없애준다는 이점이 있어 사용법을 익혀두면 좋다. 원소는 insert 멤버 함수로 삽입되면 자동으로 정렬(오름차순)된다. set 헤더( #include )에 들어있고, vector랑 겹치는 멤버함수들이 있어 vector 공부 후 보니 좀 더 편한 것 같다. Set 초기화 set 변수명 기본 선언 set 변수명(복사할 변수) 선언 후 복사한 값으로 초기화 set 변수명 = 복사할 변수 선언 후 복사한 값으로 초기화 set 변수명(복사할 변수.begin(), 복사할 변수.end()) 선언 후 복사한 값으로 초기화 Set 반복자(iterator) s.begin() / s.e..

[C++ STL] vector(벡터) 공부

STL : 표준 템플릿 라이브러리; Standard Template Library 사용하려면 #include 가 필요하다. C++에서는 동적 배열 구조를 vector로 구현할 수 있다. vector vec, vector vec처럼 선언해주면 자동으로 배열의 크기 조절과 객체의 추가, 삭제가 가능하다. 단, 한번에 한 타입만 저장이 가능하다. 요소에 접근하거나, 앞 or 뒤에 요소를 추가/삭제하거나, 크기를 알 수 있는 멤버 함수 등을 제공한다. 다음은 vector를 이용해 문자열을 추가, 삭제해 각각 출력하는 코드다. #include #include #include // vector 헤더파일 추가 using namespace std; int main() { vector vec; // 비어있는 벡터 생성 ..

[C++] 클래스(class) 기본

클래스(Class) C++의 클래스는 C의 구조체에서 확장된 C++의 구조체와 기본(default) 접근제한자만 다른 것이라고 볼 수 있다. 접근제한자 접근 제한자는 3가지로 나뉘며, 멤버들의 접근 권한을 정한다. private: 같은 클래스(또는 friend) 안에서 접근 가능 클래스 내(클래스 내에 정의된 함수)에서만 접근 허용 protected: 같은 클래스 또는 상속된 자식 클래스(또는 friend) 안에서 접근 가능 - 상속관계에 놓여있을 때, 유도 클래스에서의 접근 허용 public: 어디서든 접근 가능 C++에서 클래스의 기본 접근 제한자는 private이다. C에서 구조체나 C++에서 구조체의 기본 접근 제한자가 public인 것과 다르다. 클래스는 쉽게 말하면 변수와 함수 등을 포함하는 ..

OOP(객체지향 프로그래밍)의 주요특징

객체지향 프로그래밍(Object-Oriented Programming; OOP)의 주요 특징으로는 캡슐화, 추상화, 상속, 다형성이 있다. 정보은닉을 추가하여 5가지라고 보는 경우도 있으니, 캡슐화와 정보은닉의 차이점에 유의하며 주요 특징들을 알아보자. 1. 캡슐화(Encapsulation) 변수와 함수를 캡슐처럼 하나의 단위로 묶는 것을 의미한다. 즉 데이터의 번들링(Bundling)이다. 이처럼 객체의 속성(data fields)과 행위(메서드)를 하나로 묶기도 하고, 실제 구현 내용 일부를 외부로부터 감춰 은닉한다는 특징이 있어 캡슐화라고 한다. 대개 프로그래밍 언어에서 이 번들링은 클래스를 통해 구현되고, 해당 클래스의 인스턴스(객체) 생성을 통해 클래스 안에 포함된 멤버 변수와 메소드에 쉽게 접..

[C++] 데이터 타입(자료형)

C++의 데이터 타입은 크게 아래와 같이 구분짓고 있다. bool형 문자형 정수형 부동소수(실수)형 다음은 C++ 32비트 및 64비트를 기준으로 한 자료형의 크기 및 범위다. 구분 데이터 타입 크기 (byte) 범위 bool형 bool 1 true or false 문자형 (signed) char 1 -128 ~ 127 unsigned char 1 0 ~ 255 wchar_t 2 0 ~ 65,535 정수형 (signed) short (int) 2 -32,768 ~ 32,767 unsigned short (int) 2 0 ~ 65,535 (signed) int 4 –2,147,483,648 ~ 2,147,483,647 unsigned int 4 0 ~ 4,294,967,295 (signed) long (i..