코딩 및 기타/어서와! 자료구조와 알고리즘 (34) 썸네일형 리스트형 9일차 스택 ∙ 스택이란? - stack : 물건을 쌓아 올린 더미 또는 쌓는 행위 - 자료 구조에서 스택은 데이터를 쌓아 올리듯이 저장하는 선형 자료 구조로서, 후입선출 원리에 따라 삽입과 삭제가 수행됨 - 후입선출 (LIFO, Last-in First-out) : 나중에 들어온 데이터가 먼저 출력됨 - 데이터의 입출력이 한쪽 방향에서만 수행되는 리스트 ex) 텍스트 편집기의 실행 취소 가능, 웹 브라우저에서 뒤로 가기, 함수 호출 시 복귀 주소 기억 ∙ 스택의 주요 연산 - push(e) : 스택의 맨 위에 원소 e를 추가 - pop() : 스택의 맨 위에 있는 원소를 삭제 - top() : 스택의 맨 위에 있는 원소를 참조. peek() - empty() : 스택이 비어 있으면 true를 반환 - size.. 8일차 향상된 이중 연결 리스트 클래스 ∙ DoublyLinkedList 클래스에 추가할 기능 - 반복자(iterator) 지원 - 데이터 검색 기능 - 범용 데이터 저장을 위한 클래스 템플릿 작성 ∙ DoublyLinkedList 클래스에 begin()과 end() 멤버 함수 추가 iterator begin() const { return iterator(header -> next); } iterator end() const { return iterator(trailer); } ∙ DoublyLinkedList 클래스에 find() 멤버 함수 추가 iterator find(cost int val) { Node* curr = header -> next; while (curr -> data != val && cur.. 캐스팅 (형변환) ∙ static_cast - 정적 캐스트 보통 정젹이라 함은 언어에서 컴파일시에 ~ 동적이라함은 런타임시에 ~ 를 의미한다. 즉, static_cast 연산자를 통해 형변환을 하면 컴파일(정적) 타입에 형변환이 가능한지 검사한다. // 사용방법 : double 형에서 int형으로 형변환 double num = 12.345; num = static_cast(num); // int형으로 형변환 7일차 이중 연결 리스트 ∙ 연결 리스트 종류 - 단순 연결 리스트 > 다음 노드에 대한 링크만 가지고 있는 연결 리스트 > 한쪽 방향으로만 순회가 가능 (단방향 연결 리스트) - 이중 연결 리스트 > 이전 노드와 다음 노드에 대한 링크를 가지고 있는 연결 리스트 > 양방향 순회가 가능 (양방향 연결 리스트) - 원형 연결 리스트 > 일반적인 연결 리스트의 마지막 노드 링크가 처음 노드를 가리키도록 구성된 자료 구조 > 처음 노드가 다시 나타나면 순회를 멈춤 ∙ 이중 연결 리스트의 구조 - 노드 구조체 struct Node { int data; Node* prev; Node* next; }; - 이중 연결 리스트 클래스 class DoublyLinkedList { //맴버 변수 private: int count.. 6일차 연결 리스트 ∙ 리스트 - 순서를 가진 데이터의 모임, 목록 - TO DO 리스트, 요일... - 리스트의 주요 연산 > 원소의 참조, 삽입(insert), 삭제(remove), 검색(search) - 대표적인 리스트 구현 방법 배열 연결리스트 저장공간 연속적인 메모리 공간 임의의 메모리 공간 원소의 삽입 & 삭제 비효율적 효율적 구현 쉬움 어려움 ∙ 연결 리스트 - 데이터와 링크로 구성된 노드(node)가 연결되어 있는 자료 구조 > 데이터(data) : 정수, 문자열, 복합 자료형 등 > 링크(link, next) : 다음 노드를 가리키는 포인터 > 노드(node) : 데이터와 링크로 이루어진 연결 리스트 구성단위 ∙ 연결 리스트 맨 앞에 노드 삽입하기 void push_front(int val) {.. 5일차 주요 모던 C++ 문법 ∙ 타입 추론 auto 키워드 - 변수 선언 시 타입 자리에 auto 키워드를 지정하면 컴파일 시간에 자동으로 타입을 추론하여 결정 - 복잡한 타입 또는 범용적인 코드 작성 시 유리 - const 또는 레퍼런스(&) 속성을 사용해 auto를 한정할 수 있음 auto a1 = 10; //int auto a2 = 3.14; //float auto a3 = "hello"; //const char* auto a4 = "hello"s; //std::string ∙ 타입 정의 (using) - C언어 또는 C++11 이전이라면 typedef를 사용하고, C++ 이후라면 using 사용을 권장 - using 문법이 읽기 더 쉽고, 템플릿 별칭도 지원함 ∙ 범위 기반 for문 - 배열 또는 ST.. 4일차 동적 배열과 std::vector ∙ 동적 메모리 할당(dynamic memory allocation) - 프로그램 실행 중 필요한 크기의 메모리 공간을 할당하여 사용하는 기법 - 동적으로 할당한 메모리는 사용이 끝나면 명시적으로 (할당된) 메모리를 해제해야 한다. - C언어 : malloc() 또는 calloc() 함수로 메모리 할당하고, free() 함수로 메모리 해제 - C++언어 : new 연산자로 메모리 할당하고, delete 연산자로 메모리 해제 ∙ 동적 메모리 할당을 이용한 동적 배열 생성 및 해제 - new [] 연산자를 이용하여 동적 배열을 위한 메모리를 할당하고, delete [] 연산자를 이용하여 동적 배열 메모리를 해제 - 동적 메모리 할당은 힙 메모리 영역을 사용하므로 대용량 배열.. 3일차 배열 : C에서 C++로 ∙ 배열이란? - 같은 종류의 데이터가 연속적으로 저장되어 있는 자료 구조 ex) 다섯 학생의 점수를 저장하려면? int score1, score2, score3, score4, score5; 만약 학생의 수가 더 많으면 하나하나 입력하기 힘듦,,,, int score[5]; 그렇기에 위처럼 배열을 선언하면 관리하기 편하다. ∙ 배열의 특징 - 인덱스(index)를 사용하여 원하는 원소(element)에 곧바로 접근 가능 : O(1) - 캐시 지역성 (cache locality) > 배열의 각 원소는 서로 인접해 있기 때문에 하나의 원소에 접근할 때 그 근방에 있는 원소도 함께 캐시로 가져옴 - 반복문에서 배열을 사용하면 효율적인 프로그래밍이 가능 - 상수 또는 상수표현식으로 크.. 이전 1 2 3 4 5 다음
