정의 및 특징 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질 - LIFO(후입선출) 재귀적인 함수, 알고리즘 및 웹 브라우저 방문 기록 등에 사용 주로 문자열 폭발, 괄호만들기, 짝찾기 키워드를 기반으로 이루어진 문제에서 사용 가능 "교차하지 않고" 라는 문장이 나오면 스택 사용 고려 시간 복잡도 삽입 및 삭제 -> O(1) 탐색 -> O(n) n번재 요소를 찾는다고 가정하면 계속해서 앞에 있는 요소를 끄집어내야하기 때문 예시 코드 #include using namespace std; stack stk; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); stk.push("엄"); stk.push("준"); stk.push("식")..

1. set 정의 및 특징 set은 고유한 요소만을 저장하는 컨테이너 중복 허용 xxxxxx map처럼 {key, value}로 집어넣지 않아도 되며 아래 코드처럼 pair나 int형을 집어넣어서 만들 수 있다. 중복된 값을 제거되며 map처럼 자동 정렬 method는 map과 동일 예시 코드 #include using namespace std; int main(){ set st; st.insert({"test", 1}); st.insert({"test", 1}); st.insert({"test", 1}); st.insert({"test", 1}); cout

1. map 정의 고유한 키를 기반으로 키 - 값 (key-value) 쌍으로 이루어져 있는 정렬된(삽입할 때마다 자동 정렬) 연관 컨테이너 레드 - 블랙트리로 구현 균형 이진 검색 트리 시간복잡도 레드 - 블랙트리로 구현되어 있어서 삽입, 삭제, 수정, 탐색 -> O(logN) 특징 고유한 키를 갖기 때문에 하나의 키에 중복된 값 xxx 자동으로 오름차순 정렬되기 때문에 넣은 순서대로 map을 탐색하는 것이 아닌 아스키코드순으로 정렬된 값들을 기반으로 탐색 대괄호 연산자 [] 로 해당 키로 직접 참조 가능 키와 value는 string이나 int 뿐만 아니라 다양한 값이 가능 iterator로 순회 가능 예시 코드 #include using namespace std; map mp; string a[] ..

list 연결리스트 요소가 인접한 메모리 위치에 저장 xxx인 선형 데이터 구조 요소들은 next, prev라는 포인터로 연결되어 이루어지고 중복을 허용 시간복잡도 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료구조 삽입과 삭제 O(1) k번째 요소를 참조한다 했을 때 O(k) 노드 노드는 아래와 같이 이루어져 있다. (싱글연결리스트 기준) data 노드와 노드를 잇게 만드는 next라는 포인터 class Node { public: int data; Node* next; Node(){ data = 0; next = NULL; } Node(int data){ this->data = data; this->next = NULL; } }; 분류 크게 3가지로 나뉜다. 싱글 연결 리스트(..

Vector 동적인 요소를 할당할 수 있는 동적배열 만약 컴파일 시점에 사용해야 할 요소들의 개수를 모른다면 vector를 사용해야 한다. 특징 연속된 메모리 공간에 위치한 같은 타입의 요소들의 모음 숫자인덱스를 기반으로 랜덤접근이 가능 중복을 허용 시간 복잡도 탐색과 맨 뒤의 요소를 삭제하거나 삽입하는데 O(1) 맨 뒤나 맨 앞이 아닌 요소를 삭제하고 삽입하는데 O(n) 선언 vector 변수명; 위와 같이 선언한다 예를 들어 int형 vector를 정의하고 싶다면 vector로 정의 이는 다른 자료구조도 동일 예시 코드 #include using namespace std; vector v; int main(){ for(int i = 1; i

Array 정적배열 선언 시 보통 크기를 설정해서 연산 진행 연속된 메모리 공간에 위치한 같은 타입의 요소들의 모음이며 숫자인덱스를 기반으로 랜덤접근이 가능하며 중복을 허용 선언 타입 c 스타일과 std 스타일이 존재 c 스타일 int a[10] 과 같이 선언 std 스타일 array a; 이렇게 선언 특징 vector와는 달리 메서드가 xxxxx 배열의 크기를 정해서 선언할 수도 있음 int a[3] 크기를 정하지 않고 선언하되 배열을 중괄호로 요소들을 할당할 수도 있음 int a2[] = {1, 2, 3, 4} 위 코드처럼 하게 되면 자동적으로 rvalue의 크기로 할당되어 int a2[] 는 int a2[4] 와 같은 의미를 가진다. 예시 코드 #include using namespace std; ..

황기태 저자의 명품 C++ Programming 개정판을 읽고 학습한 내용을 정리한 포스트입니다! https://search.shopping.naver.com/book/catalog/32436115747 C++ Programming : 네이버 도서 네이버 도서 상세정보를 제공합니다. search.shopping.naver.com auto를 이용한 쉬운 변수 선언 auto 키워드는 C++11 표준부터 의미가 수정되어, 변수 선언문으로부터 변수의 타입을 추론하여 결정하도록 지시 auto는 복잡한 형식의 변수 선언을 간소하게 해주며, 타입 선언의 오타나 번거로움을 줄이게 해준다 auto pi = 3.14; // 3.14가 실수이므로 pi는 double 타입으로 선언됨 auto n = 3; // 3이 정수이무로..

황기태 저자의 명품 C++ Programming 개정판을 읽고 학습한 내용을 정리한 포스트입니다! https://search.shopping.naver.com/book/catalog/32436115747 C++ Programming : 네이버 도서 네이버 도서 상세정보를 제공합니다. search.shopping.naver.com 개요 표준 템플릿 라이브러리(Standard Template Library, STL)는 템플릿으로 작성된 많은 제네릭 클래스와 함수 라이브러리이다. ISO/ANSI C++ 표준위에서는 STL을 C++의 표준으로 채택하여 현재 C++ 표준 라이브러리에 포함되게 되었다. STL에 포함된 제네릭 클래스와 함수들은 컨테이너, iterator, 알고리즘크게 3가지로 분류된다. 또한 이 세..

황기태 저자의 명품 C++ Programming 개정판을 읽고 학습한 내용을 정리한 포스트입니다! https://search.shopping.naver.com/book/catalog/32436115747 C++ Programming : 네이버 도서 네이버 도서 상세정보를 제공합니다. search.shopping.naver.com 제네릭 클래스 개요 template를 이용하면 제네릭 클래스(generic class)도 만들 수 있다. int 값을 저장하는 스택, double 값을 저장하는 스택, char 값을 저장하는 스택 등 다양한 스택이 필요할 수 있다. 다만 이들 스택 클래스는 데이터의 타입만 다를 뿐 알고리즘은 동일하기에, 템플릿을 이용하여 스택에 저장되는 데이터 타입을 일반화시킨 제너릭 스택 클래..