Brute force Study

배열 기반 스택배열 기반 스택데이터만 담는 구조체로 노드를 표현스택 구조체의 경우 용량, 최상위 노드의 위치, 노드 배열 총 3가지 필드를 가지고 있어야 함typedef struct tagArrayStack { int Capacity; int Top; Node* Nodes; // 자유 저장소에 할당된 배열을 가리키는 용도로 사용(첫 번째 요소)} ArrayStack;배열 기반 스택의 함수생성void AS_CreateStack(ArrayStack** Stack, int Capacity){ // 스택을 자유저장소에 생성 (*Stack) = (ArrayStack*)malloc(sizeof(ArrayStack)); // 입력된 Capacity만큼의 노드를 ..

환형 링크드 리스트(Circular Linked List)a.k.a 원형 연결 리스트싱글 링크드 리스트나 더블 링크드 리스트와 노드 구성은 동일하지만, 헤드와 테일이 연결되어 있음테일의 nextNode는 헤드를 가리키고, 헤드의 prevNode는 테일을 가리킴리스트의 시작과 끝을 미리 알 수 있다 (시작을 알면 끝을 알 수 있고, 끝을 알면 시작을 알 수 있다)DLL의 삽입 함수와 같은 부분의 성능을 많이 개선할 수 있다. (테일에 접근하는 비용이 거의 없으므로)노드를 뒤에서 역순으로 찾아나갈 수 있는 탐색도 구현할 수 있다.환형 더블 링크드 리스트의 주요 연산추가 / 삭제 연산 이외 함수들은 링크드 리스트와 더블 링크드 리스트 함수와 동일함노드 추가 연산비어있는 리스트에 새 노드를 추가하면 이 노드는 ..

이중 연결 리스트(Doubly Linked List)링크드 리스트의 탐색 기능을 개선한 자료구조양방향 탐색이 가능함 (vs 싱글의 단방향)자신 앞에 있는 노드를 가리키는 포인터를 가짐으로써 양방향 탐색이 가능함구조체typedef int ElementType;typedef struct tagNode{ ElementType data; // 저장할 데이터 struct tagNode* prevNode; // 앞 노드의 주소와 데이터 struct tagNode* nextNode; // 뒤 노드의 주소와 데이터} Node; 더블 링크드 리스트의 주요 연산기존 링크드 리스트의 연산과 동일(명세는 구현방식과 상관없이 동일함)노드의 생성/소멸 연산노드의 생성Node* ..

Singly Linked List(SLL) 구현구조체typedef int ElementType; // 필요할 때 원하는 타입으로 바꿔 쓰자typedef struct tagNode { ElementType Data; // 데이터 struct tagNode* NextNode; // 다음 노드} Node;연결 리스트의 주요 연산노드 생성 / 소멸힙(자유 저장소)에 새로운 노드를 생성Node* SLL_CreateNode(ElementType newData) { Node* NewNode = (Node*)malloc(sizeof(Node)); // 새로운 노드 동적할당으로 생성 NewNdoe->Data = newData; // 데이터 저장 NewNode->NextNode = NULL; /..

대입 연산자 오버로딩대입 연산자(=)는 객체에 다른 객체의 값을 할당하는 데 사용됨대입 연산자 오버로딩을 통해 자신이 정의한 클래스에 대해 대입 연산자의 동작을 사용자 지정하거나 확장함기본적으로 C++ 컴파일러는 멤버변수 단위로 얕은 복사(shallow copy)를 수행하지만, 깊은 복사(deep copy)를 수행하도록 지정할 수 있음/* 생략 */// 대입 연산자 오버로딩String &operator=(const String &rhs) { // 참조로 선언하지 않으면 rhs(s1)이라는 복사 생성자가 작동해서 복잡해짐. if (this != &rhs) { // 자기 자신을 대입하는 경우를 막기. // 만약 strData에 어떤 값이 존재한..

복사 생성자 오버로딩복사 생성자란 객체를 다른 객체로 복사하는 데 사용되는 특별한 생성자동일한 클래스의 다른 객체로부터 호출되며, 그 결과로 현재 객체가 다른 객체와 동일한 상태로 초기화됨/* 생략 */// 복사 !!!생성자!!!의 작동 String(const String &rhs) { // String s2(s1); 사용시 발생하는 일. // const String rhs 로 선언하면 안된다(무한 루프에 빠짐) cout String(const String &rhs) 에서 rhs가 아닌 &rhs를 사용해야 함레퍼런스로 선언하지 않으면 매개변수가 전달되는 과정에서 rhs(전달된 매개변수) 가 일어남이는 다시 복사 생성자를 호출하므로, 무한 루프에 빠지게 됨따라서 매개변수를 ..

깊은 복사와 얕은 복사(Deep Copy, Shallow Copy) 깊은 복사 / 얕은 복사란 얕은 복사 : 복사된 객체가 원본 객체의 요소들을 참조 예시 int *a = new int(5); int *b = new int(3); a = b; delete a; delete b; 3이 저장된 공간을 두 번 지움 5가 저장된 공간이 안지워짐 위와 같은 복사를 얕은 복사라 한다.(참조만 복사) 객체 내부에 참조 타입이 있는 경우에는 얕은 복사로 인해 문제가 발생할 수 있음 깊은 복사 : 원본 객체의 완전한 복사본을 생성, 복사된 객체는 완전히 독립적인 새로운 객체를 가지게 됨 내부에 있는 모든 객체들까지 재귀적으로 복사함 예시 int *a = new int(5); int *b = new int(3); *a =..

상속과 접근제어자상속(inheritance)기존의 클래스를 재사용하여 새로운 클래스를 작성하는 것class 이름 뒤에 상속받고자 하는 클래스의 이름을 키워드 'extends'와 함께 써 주기만 하면 된다class Child extends Parent { // ...}조상 클래스 : 상속해주는 클래스 (a.k.a 부모, 상위(super), 기반(base) 클래스)자손 클래스 : 상속 받는 클래스 (a.k.a 자식, 하위(sub), 파생된(derived) 클래스)생성자와 초기화 블럭은 상속되지 않음. 멤버만 상속됨자손 클래스의 멤버 개수는 조상 클래스보다 항상 같거나 많다class Tv { boolean power; // 전원상태(on/off) int channel; // 채널 void power() ..

클래스와 객체클래스와 객체의 정의클래스의 정의 : 객체를 정의해 놓은 것클래스의 용도 : 객체를 생성하는데 사용된다객체와 인스턴스클래스의 인스턴스화(instantiate) : 클래스로부터 객체를 만드는 과정인스턴스 : 어떤 클래스로부터 만들어진 객체ex) Tv클래스로부터 만들어진 객체를 Tv클래스의 인스턴스라고 함인스턴스의 생성과 사용클래스명 변수명; // 참조변수 선언변수명 = new 클래스명();Tv t;t = new Tv();객체 배열객체 배열을 다루기 위한 참조 변수 배열을 생성객체를 생성해서 배열의 각 요소에 저장Tv[] tvArr = new Tv[3]; // 참조변수 배열을 생성// 객체를 생성해서 배열의 각 요소에 저장tvArr[0] = new Tv();tvArr[1] = new Tv();t..

배열배열 생성 방법타입[] 변수이름 = new 타입[길이]길이가 0인 배열을 생성할 수 있다JVM이 모든 배열의 길이를 별도로 관리하고, '배열이름.length'를 통해서 배열의 길이에 대한 정보를 얻을 수 있다.배열은 한 번 생성하면 길이를 변경할 수 없다.공간이 부족해 배열의 길이를 변경해야 하는 경우 더 큰 길이의 새로운 배열을 생성한 다음 기존 배열의 값을 새로운 배열에 복사한다유효한 인덱스 범위를 넘어서면 ArrayIndexOutOfBoundsException이라는 예외가 발생한다코드를 변경해 배열의 길이가 바뀔 때, '배열이름.length'는 for문에서 알아서 값을 update 해준다.배열의 초기화배열 생성과 동시에 자동적으로 자신의 타입에 해당하는 기본값으로 초기화 됨선언과 생성을 동시에 ..