![]()
그래프 관련 문제를 풀 때는, 문제 상황을 그래프로 모델링한 후 푸는 것이 보편적이다. 이 때, 모델링한 그래프의 연결관계를 나타내는 두 가지 방식이 있다. 👉 1. 인접 행렬 2. 인접 리스트 🟩 인접 행렬 그래프의 연결 관계를 이차원 배열로 나타내는 방식 인접 행렬을 adj[][]라고 한다면, adj[i][j]에 대해서 다음과 같이 정의 가능 adj[i][j] : 노드 i에서 노드 j로 가는 간선이 있다면 1, 아니면 0 cf. 만약 간선에 가중치가 있는 그래프라면 1 대신에 가중치의 값을 직접 넣어주는 방식으로 구현 가능하다. 🌟 예시 유향 그래프가 아닌 무향 그래프에서는, 노드 i 👉 노드 j 라는 말은, 노드 j 👉 노드 i라는 의미이다. 따라서, 인접 행렬이 대각성분(i=j인 원소들)을 기준으..
🟩 생성자 객체가 생성되는 시점에 자동으로 호출되는 멤버 함수로 클래스 이름과 동일한 멤버 함수이다. 또, 함수 특유의 리턴 타입을 지정하면 안된다. class Circle { Circle(); Circle(int radius); }; Circle::Circle() { radius = 10; cout
멤버변수의 외부접근을 허용하면(public 사용), 잘못된 값이 저장되는 문제가 발생할 수 있다. 따라서, 멤버변수의 외부접근을 막게 되는데, 이를 가리켜 정보 은닉이라 한다. EX) public int x; // 0이상 100이하 조건에 맞는 값이 들어온다는 법이 없다. 👉 클래스의 멤버변수를 private으로 선언하고, 해당 변수에 접근하는 함수를 별도로 정의해서, 안전한 형태로 멤버변수의 접근을 유도하는 것이 바로 '정보 은닉'이며, 이는 좋은 클래스가 되기 위한 기본 조건이다. 👉 별도로 정의된 함수에서 조건에 맞는 값을 불러오도록 조건을 설정할 수 있다. 👉 함수만 한 번 잘 정의되면 잘못된 접근은 원천적으로 차단된다. 🟩 const 함수 const 함수 내에서는 동일 클래스에 선언된 멤버변수의..
🌟 객체에 대한 간단한 정의 사전적 의미 : 물건/대상 🟩 객체 중심의 프로그래밍 "나는 과일장수에게 두 개의 사과를 구매했다" 객체 👉 나, 과일장수, 사과 데이터 👉 두 개 행위, 기능 👉 구매했다. 객체지향 프로그래밍에서는 나, 과일장수, 사과라는 객체를 등장시켜 두 개의 사과 구매라는 행위를 실체화한다. 현실에 존재하는 사물과 대상, 그리고 그에 따른 행동을 있는 그대로 실체화시키는 형태의 프로그래밍 🟩 객체 = 데이터 + 기능 🌟 객체 표현 (행위) 과일장수는 과일을 판다. (상태) 과일장수는 사과 20개, 오렌지 10개를 보유하고 있다. 🌟 데이터 표현(변수 선언) 보유하고 있는 사과의 수 : int numOfApples; 판매 수익 : int myMoney; 과일 값 : const int A..
연관있는 데이터를 하나로 묶으면 프로그램의 구현 및 관리가 용이하다. 👉 구조체는 연관있는 데이터를 하나로 묶는 문법적 장치 연관있는 데이터들은 생성 및 소멸의 시점이 일치하고, 이동 및 전달의 시점, 방법이 일치하기 때문에 하나의 자료형으로 묶어서 관리하는 것이 용이하다. struct Car{ char gamerID[ID_LEN]; int fuelGauge; int curSpeed; }; 🟩 구조체 변수 선언, 생성 // 구조체 선언 Car basicCar; // cf. struct Car basicCar; // 구조체 생성 Car run99 = {"run99", 100, 0}; struct 키워드의 생략을 위한 typedef 선언 불필요 구조체 변수마다 함수가 독립적으로 존재하는 구조는 아니지만, 논..
int num = 2010; 변수의 선언으로 num1이라는 이름으로 메모리 공간이 할당된다. int &num2 = num1; 참조자의 선언으로 인해 num1의 메모리 공간에 num2라는 이름이 추가로 붙게된다. num1이 하는 모든 연산은 num2로 하는 것과 동일한 결과를 보인다. 🟩 참조자는 기존에 선언된 변수에 붙이는 '별칭', 변수의 이름과 사실상 차이가 없다. 🟩 참조자의 수에는 제한이 없으며, 참조자를 대상으로 참조자를 선언할 수도 있다. int num1 = 2579; int& num2 = num1; int& num3 = num2; int& num4 = num3; 🟩 참조자의 선언 가능 범위 int &ref = 20; (X) 상수 대상으로의 참조자 선언은 불가능 int &ref; (X) 참조자..
🟩 실행중인 프로그램은 운영체제로부터 메모리 공간을 할당받는다. 🌟 데이터 : 전역변수 저장 🌟 스택 : 지역변수, 매개변수 저장 🌟 힙 : 동적으로 할당이 이뤄지는 영역 🟩 c를 더하고 .h를 빼라 #include 👉 #include #include 👉 #include #include 👉 #include #include 👉 #include
![]()
✏️const = 변수를 상수화 시킨다 (변하지 못하게 만든다) 🟩 const int * ptr = &a 상수에 대한 포인터, 포인터가 가리키는 대상을 상수화 값 변경X 주소 변경O 가리키는 원본 변수 자체를 상수화X (상수 취급) 🟩 int * const ptr = &a 상수 포인터, 포인터 자체를 상수화 값 변경O 주소 변경X 🟩 const int * const ptr = &a 상수에 대한 상수 포인터 값 변경X 주소 변경X 🌟 값 변경 *ptr = 1; 🌟 주소 변경 ptr = &b; 🟩 const로 선언된 객체를 대상으로 const로 선언되지 않은 멤버함수의 호출은 불가능 함수의 const 선언 유무는 함수 오버로딩의 조건이 된다. const int a; void Func(){} void Func..
🟩 key만 있는 map 혹은 정렬된 집합 set은 map과 구조가 매우 유사하다. 단, key만 있고 value가 없는 map이라고 볼 수 있다. 따라서, 사용법도 map과 크게 다르지 않다. 정렬된 집합이라고 정의한 이유는 set이 갖는 값들이 중복을 허락하지 않고 정렬되어 있기 때문이다. 🟩 특정 값에 대해 검색을 빠르게 하고 싶은 경우 🟩 #include s.size() s의 노드 개수를 리턴 s.empty() s의 사이즈가 0인지 아닌지를 확인 s.begin() s의 첫 번째 원소를 가리키는 iterator 리턴 s.end() s의 마지막 원소를 가리키는 iterator 리턴 s.insert(k) s에 값이 k인 노드 추가 s.erase(k) s에 값이 k인 노드 삭제 s.find(k) s에서 ..
🟩 인덱스로 int가 아닌 다른 자료형을 사용할 수 있는 배열 (편의상) map의 내부적인 구조는 각 노드가 key와 value의 쌍으로 이루어진 '트리'이다. 특히 검색, 삽입, 삭제 등의 속도를 빠르게 하기 위해 균형 이진 트리 중의 하나인 '레드-블랙 트리'로 구현되어 있다. 검색 속도가 특히 빠른데 이는 key를 기준으로 정렬된 상태이기 때문이다. 🟩 연관있는 두 값을 함께 묶어서 관리하되, 검색을 빠르게 하고 싶은 경우 🟩 #include map은 중복 불가한 key와 value 쌍으로 이루어진 노드의 트리라고 할 수 있다. 같은 key 값을 갖는 노드를 추가하면 어떻게 될까? 해당 key 값을 갖고 있던 원래 노드의 value 값에 덮어 씌워지게 된다. map의 요소에 접근할 때, 반복자(it..
![]()
🟩 균형 탐색 트리 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조 키의 개수 (t-1)~(2t-1) 개 자식 노드의 개수 t~2t 개 🟩 성질 1. 노드에는 2개 이상의 데이터가 들어갈 수 있으며, 항상 정렬된 상태로 저장된다. 2. 내부 노드는 ceil(m/2) ~ m 개의 자식을 가질 수 있다. 최대 m개의 자식을 가질 수 있는 B트리를 m차 B트리라 한다. ceil() 함수는 올림 함수이다. 즉, ceil(3/2) = 2이다. 즉, 3차 B트리의 리프 노드와 루트노드를 제외한 내부 노드는 2-3개의 자식을 가질 수 있다. 3. 특정 노드의 데이터(key)가 K개라면, 자식 노드의 개수는 K+1개여야 한다. 특정 노드의 데이터가 2개라면, 자식 노드는 ..
![]()
🟩 일종의 자기 균형 이진 탐색 트리 이진 탐색 트리의 조회는 O(logn) 시간이 걸리게 되는데, 문제는 균형이 무너질 경우 O(n)까지 시간이 증가할 수 있다는 것이다. 👉 레드-블랙 트리의 가장 큰 특징은 삽입, 삭제 동안 트리의 모양이 "균형 잡히도록" 각 노드들은 red or black 색상을 가진다는 것이다. 검색, 삽입, 삭제 시 최악의 경우에서도 모두 O(logn)이 보장되는 자료구조 🌟 예1. map map은 중복을 허용하지 않는 (key, value) 쌍으로 이루어진 트리 map의 내부 구현은 검색, 삽입, 삭제가 O(logn)으로 동작하는 레드-블랙 트리로 구성되어 있다. 🟩 성질 리프 노드는 따로 key나 data를 포함하지 않으며, 실제 코드에서도 구현되지 않는 "완전 가상의 노드..
