노는 게 제일 좋아

사실 그래프의 연결 상태를 표현할 때 우리는 배열로 많이 하곤 한다. 하지만 행렬을 이용했을 때 가장 큰 문제점은 노드의 개수의 제곱에 비례하는 메모리를 사용하기 때문이다. 노드의 개수 범위가 만약 100000이라면 십만의 제곱은... 우선 0이 10개다. 10억이다. int로 저장했다면 10억 * 4byte = 40억 byte 다. 그러면.. 약 3기가 바이트.. 그래서 우리는 굳이 연결되지 않은 부분까지 저장하기는 그래서 인접리스트로 저장하기로 했다. 그렇게 되면 실제로 연결된 부분만 저장할 수 있다. 즉, vector을 원소로 하는 vector 또는 array를 만들어 해당 인덱스랑 연결된 노드들의 정보를 넣는 것이다. 실제로 이는 문제풀이할 때 노드의 수로 초과하는 것을 막아주기 때문에 유용하다고..

BST를 구현해보고 기본적인 함수들을 구현해보자 BST는 이진 탐색 트리로 루트노드보다 작은 값은 항상 왼쪽에 큰 값은 항상 오른쪽에 존재하는 트리다. #include //노드에 대한 정의 이진 트리이기 때문에 자식은 2개가 최대임 struct node { int data; node* left; node* right; } struct bst { node* root = nullptr; //초기 값은 널 node* find(int value) { return find_implement(root, value); } private: node* find_implement(node* current, int value) { //현재노드가 NULL이라면 if(!current) { std::cout data == val..

배열에서 중요한 것은 배열의 크기와 해당 배열의 접근 방법이다. 때문에 생성자에서 배열의 크기와 해당 배열을 가리키는 포인터를 항상 알고 있어야 한다. 이를 염두한 채 구현해보자 #include #include //필요한 헤더파일 포함시키고 //동적 배열 클래스를 만들어보자 (임의의 타입을 위해 템플릿 선언) template class dynamic_array { T* data; // 해당 배열을 가리키는 포인터 (동적할당 받음) size_t n; // 배열 사이즈 public: //배열의 크기를 인수로 받는 생성자. dynamic_array(int n) { this->n = n; // 이 함수를 call한 객체의 n을 설정 data = new T[n]; // 해당 n만큼 배열 동적할당받음 } //복사 ..

비트는 아주 유용하다. 이 문제를 풀 때 차원을 어떻게 표현하지? 라고 생각했지만 누군가가 비트라고 속삭여서 풀 수 있었다. [문제풀이(Problem Solving)] - 백준, BOJ, 1194번, 달이 차오른다 가자 4 : C++ [CPP] ****** 이러한 비트에 대해 알아보도록 하자. 우선 bitset이라는 STL부터 알아보자 A bitset stores bits (elements with only two possible values: 0 or 1, true or false, ...) 0, 1의 값을 보통 가진다. **false, true 로도 사용함. 비트셋(Bitset) 함수들 bitset 이름; bitset 선언 bit.set() 모든 비트 1로 초기화 bit.reset() 모든 비트 0으..

이나 에 다 들어있더라. 1. copy ( ) -> 이터레이터가 지시하는 위치에 복사 1-1. copy_n() -> 해당 이터레이터부터 n개 요소 복사 2. fill ( ) -> 범위에 있는 값을 지시된 값으로 설정 2-1. fill_n ( ) -> n개의 연속적인 원소들을 하나의 값으로 설정 3. unique ( ) -> 범위 내에서 중복된 요소 제거 4. rotate ( ) -> 해당 범위를 왼쪽으로 한 칸 회전 (1,2,3,4) -> (2,3,4,1) 5. lower_bound ( ) -> 하나의 값이 주어지면, 소팅된 범위 내에서 소팅된 순서를 유지를 하면서 그 값이 삽입될 수 있는 위치를 리턴 다시 말하면 범위를 처음부터 탐색하면서 value 이상의 숫자가 처음으로 나오는 위치의 iterator..

나는 C/C++/C#/Java/Python을 다 맛보고 특히 Python을 깊게 맛봤지만 문자열 처리만큼은 Python이 최고라고 생각했다. 하지만 언어는 찰흙과 같아서 자기가 만드는 대로 만들어진다. 좀 더 잘 뭉개지는 찰흙이라 쉽게 만들어지느냐 딱딱해서 만들기 어렵냐 차이지.. 결국 뭐든 만들 수 있다. 그래서 이번엔 C++에서도 문자열 처리가 가능한데.. 어떤 식으로 해야 유용한가를 탐구해보려고 한다. 알아보자 기본적으로 유용한 라이브러리(정의된)이 많다. 가장 대표적인 2가지 #include // 정규표현식 -> 필터링할 때 무지 많이 쓰인다. #include // 문자열을 다루려면 거의 필수 정규표현식과 문자열 라이브러리다. 우선 string 클래스부터 알아보자. 우선 문자열 클래스를 다루기 위..

정의는 정점의 집합 V와 가중치를 갖는 간선의 집합 E로 구성된 그래프 G = 가 주어질 때, 모든 정점을 연결하고 연결된 에지의 가중치 합이 최소인 트리 T를 구하시오 다시 쉽게 말하면 최소 비용으로 모두를 잇는 방법이라고 볼 수 있다. 아래 그림을 보자 어떤 알고리즘에 의해 만들어졌을까? **이 아이디어는 Kruskal's Algorithm이라고도 부른다. 매 반복마다 최소 값을 꺼내기 때문에 Greedy라고도 부른다. 1. 그래프의 주어진 모든 간선을 최소힙(Min Heap) H 에 추가한다. 2. H로부터 간선, e을 하나 꺼낸다. 3. 해당 간선의 양 끝점이 T에 있는 경우 e 때문에 cycle이 발생할 수 있으니 e를 버리고 다시 2 단계로 돌아간다. 4. 해당 간선을 T, 트리에 추가시키고 ..

Example에서 그냥 의미있는 것들만 남김 1. binary_search() https://en.cppreference.com/w/cpp/algorithm/binary_search int main() { std::vector haystack {1, 3, 4, 5, 9}; std::vector needles {1, 2, 3}; for (auto needle : needles) { std::cout

앞서 나온 자료구조보다 해시 테이블은 비교적 빠른 탐색 속도를 가지고 있다. 어떻게 그렇게 될 수 있는지 알아보고 어떤 자료를 표현하기에 적합한지 생각해보자 또한 여기선 lookup 이라는 용어를 알 수 있다. lookup은 조회로 해석되는데 특정 원소가 컨테이너에 있는지 확인하거나 컨테이너 키 값에 해당하는 value를 찾는 작업을 말한다. 단적으로 배열에선.. 어떠한 것이 있는지 알려면 O(N)의 시간이 걸린다. 왜냐하면 모든 것을 살펴봐야 하기 때문이다. 그렇다면 얘는 어떤 방식이길래 그것보다 빠를 수 있을지 생각해보자 앞서 배운 이진 탐색을 생각했다면 똑똑한 사람이다. [문제풀이(Problem Solving)/C++ 문제풀이에 유용한 것들] - 이진탐색, Binary Search 하지만 여기서 알..

[CS Interview] - 비선형 자료구조를 사용하는 이유 우리는 선형구조만으로 모든 것을 표현하지 못한다. 그래서 Tree를 그려내었고 Tree는 하나의 노드에서 다른 노드로 이동하는 경로가 하나만 존재하기 때문에 순환 또는 원형의 종속성을 표현할 수 없다. 때문에 우리는 또 다른 자료구조인 Graph를 구현하고자 한다. 즉, 노드 간의 더 자세한 경로의 표현을 하고싶다면 Tree 보다는 Graph가 더 적합한 자료구조라고 할 수 있다. Graph는 우선 노드에 대한 데이터를 가지고 있을 뿐만 아니라 노드 간의 간선 데이터도 가지고 있어야 한다. 즉, 해당 노드의 값과 해당 노드와 연결된 노드에 대한 정보를 가지고 있어야 한다는 것이다. edge, 간선은 무방향, 일방향 이 존재하고 해당 edge에..