분류 전체보기 34

다중 상속과 가상 상속

멤버 함수와 가상 함수의 동작 원리 객체가 생성되면 멤버 변수는 객체 내에 존재한다. 멤버 함수는 메모리의 한 공간에 별도로 위치하고 이 함수가 정의된 클래스의 모든 객체가 이를 공유하는 형태를 취한다. 한 개 이상의 가상 함수를 포함하는 클래스에 대해서는 컴파일러가 가상 함수 테이블을 만든다. 가상 함수 테이블은 객체의 생성과 상관없이 main 함수가 호출되기전 메모리 공간에 할당된다. 가상 함수 테이블은 호출되어야 할 함수의 위치정보를 담고 있는 테이블이다. class A { public: virtual void Func() { cout

가상 함수

객체 포인터의 참조 관계 객체 포인터 변수 객체의 주소 값을 저장하는 포인터 변수 Person * ptr = new Person(); A형 포인터 변수는 A객체 또는 A를 직접 혹은 간접적으로 상속하는 모든 객체를 가리킬 수 있다. class Person{}; class Student : public Person{}; class PartTimeStudent : public Student{}; Person * ptr1 = new Student(); // Person형 포인터 변수 ptr Person * ptr2 = new PartTimeStudent(); // Person형 포인터 변수 ptr Student * ptr3 = new PartTimeStudent(); // Student형 포인터 변수 ptr ..

C++에서 상속에 대해 정리

상속이란? 기존에 정의해 놓은 클래스의 재활용을 목적으로 만들어진 문법적 요소이다. class Base{}; class Derived : public Base{}; 상속받은 클래스(파생 클래스)의 생성자 정의 파생 클래스의 객체 생성 과정에서 기초 클래스의 생성자는 무조건 호출된다. 파생 클래스의 생성자는 기초 클래스의 멤버까지 초기화 할 의무가 있다. 파생 클래스의 생성자는 기초 클래스의 생성자를 호출해서 부모 클래스의 멤버를 초기화 하는 것이 좋다. 파생 클래스의 생성자에서 기초 클래스의 생성자 호출을 명시하지 않으면, 기초 클래스의 void 생성자가 호출된다. 접근 제한의 기준은 클래스이므로 상속받은 private 변수는 그 클래스의 public 함수를 통해서 간접적으로 접근을 해야한다. 파생 클래..

백준 17143. 낚시왕

17143. 낚시왕 문제에서 주어진대로 진행하는 시뮬레이션 문제이다. 정렬을 편하게 하기 위해 상어 구조체를 만들고 크기순, 번호순으로 정렬하기 위한 compare함수를 선언하였다. 풀이 과정 낚시왕이 오른쪽으로 한 칸 이동한다. 낚시왕이 있는 열에 있는 상어 중에서 가장 땅과 가까운 상어를 잡는다. 이때, 상어를 잡으면 잡힌 상어는 격자판에서 사라진다. 상어를 이동시킨다. 1~3과정을 낚시왕이 맨 끝 자리로 이동할때까지 반복한다. 소스코드 #include #include #include using namespace std; int dx[] = { 0,-1,1,0,0 }; int dy[] = { 0,0,0,1,-1 }; int ans; int map[101][101]; int curDir; int mov..

자료구조 List에 대한 설명과 구현

리스트란? 각각의 데이터가 자신의 다음 데이터(또는 이전, 다음 데이터 모두)의 위치를 가지고 있는 자료구조 데이터가 메모리에서 연속적으로 위치하고 있지는 않다. 리스트 종류 Singly Linked List - 데이터가 자신의 다음 데이터의 위치만 가지고 있다. Double Linked List - 데이터가 자신의 이전과 다음 데이터의 위치를 가지고 있다. Circular Linked List - 마지막 데이터가 처음 데이터의 위치를 가지고 있다. 리스트 연산의 시간 복잡도 데이터를 추가(임의의 위치) - O(1) 데이터를 제거(임의의 위치) - O(1) 데이터 확인/변경 - O(N) 리스트 구현(Singly Linked List) #include using namespace std; template ..

백준 17135. 캐슬 디펜스

17135. 캐슬 디펜스 브루트포스 + 시뮬레이션 문제였다. 문제에 써있는 내용대로 궁수 3명의 위치를 선택 후 시뮬레이션을 진행하여 풀면 된다. 풀이 과정 궁수 3명의 위치를 선택한다. (go 함수) 적을 공격하고 적이 이동하도록 시뮬레이션해준다. (Simulate 함수) 궁수는 자신으로부터 거리가 D이하인 적 중에서 가장 가까운 적을 공격한다. 거리가 가까운 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 모든 적이 맨 아래로 이동하여 제외될때까지 반복한다. 1~3 과정을 반복한다. 소스코드 #include #include #include using namespace std; int map[16][16]; int n, m, d; int ch[3]; int ans; int endLine=-1; ..

const, friend, static, mutable, explicit

const const는 값을 상수로 선언할 수 있도록 도와주는 키워드다. const를 앞에 붙이면 값은 변경할 수 없게 된다. const의 선언 유무도 함수 오버로딩 조건에 해당이 된다. class Test { public: void Func() { } void Func() const { } }; 객체도 상수화 할 수 있다. 이 객체를 대상으로는 const 멤버 함수의 호출만 허용한다. class SoSimple { private: int num; public; SoSimple(int n) : num(n){ } // 생성자 SoSimple& NotConstFunc(int n) { num+=n; } void ConstFunc() const // const 함수 { cout

Stack

Stack 나중에 들어간 데이터가 제일 먼저 나오는 LIFO(Last In First Out) 구조 특정 위치(한쪽 끝)에서만 데이터를 넣거나 뺼 수 있다. Stack 연산의 시간복잡도 데이터를 추가(push) -> O(1) 데이터를 제거(pop) -> O(1) 제일 꼭대기의 데이터를 확인(top) -> O(1) Stack 응용 사례 수식의 괄호 쌍 후위 표기법 DFS Stack 구현 template class Stack { private: int* stack; int size, top; public: Stack(int size) : size(size), top(-1) { stack = new T[size]; } ~Stack() { delete stack; } // 데이터 삽입 bool Push(T da..

위상 정렬

TopologySort(위상정렬) TopologySort란? 순서가 정해져있는 작업을 수행해야 할 때 그 순서를 정하기 위해 사용하는 정렬 알고리즘이다. DAG(Directed Acyclic Graph : 사이클이 없는 방향 그래프)에만 적용이 가능하다. 정렬의 결과는 여러가지가 나올 수 있다. TopologySort의 시간 복잡도 시간 복잡도 : O(V+E) (정점의 개수 + 간선의 개수) TopologySort의 구현 진입차수가 0인 정점을 큐에 삽입한다. 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다. 간선 제거 후에 진입차수(특정한 노드가 있을때 그 노드로 들어오는 다른 노드의 개수)가 0이 된 정점을 큐에 삽입한다. 큐가 빌 때까지 2~3의 과정을 반복한다. 모든 원소를 방문하기 전에 큐가 비..

스택으로 큐 구현하기 / 큐로 스택 구현하기

스택과 큐의 상호 구현 면접 보면서 정말 많이 받은 질문 중 하나이다. 처음 질문받았을 때 어버버 하면서 아무것도 대답 못했던 기억이 있고 두 번째 받았을 땐 자신 있게 작성하다 틀린 기억이 있는 부끄러운 기억이 있다. 스택으로 큐 구현하기 이론은 간단하다. 2개의 스택을 이용해서 구현하면 된다. Enqueue(삽입) 그냥 첫 번째 스택인 a에 추가만 하면 된다. Dequeue(제거) 두 번째 스택인 b가 비어있지 않다면 b에 있는 값을 제거(반환) 하면 된다. 두 번째 스택인 b가 비었다면 첫 번째 스택인 a가 빌 때까지 a를 pop(제거)하면서 두 번째 스택인 b에 push(추가) 한다. class StackQueue { public: stack a; stack b; void Enqueue(int d..