개발일지

구현　위의 검색 / 삽입 / 삭제의 특성을 가지는 BST를 구현하는 시간을 가지도록 하자. #include using namespace std;struct Node{ int _data; Node* _left, * _right;};　트리에 사용될 노드 구조체 Node를 선언한다. class BST{ Node* _root;public: BST() : _root(nullptr) {}　이진 탐색 트리 클래스 BST를 선언하고, 기본 생성자를 통해 루트 노드를 nullptr로 초기화해 준다. class BST{ ... Node* Find_Implementation(Node* node, int value) { if (!node) // node가 존재하지 않는 경우 return NULL; if (node->_..

이진 검색 트리 (BST)개요　이진 검색 트리(Binary Search Tree - BST)는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 이진트리의 일종으로서, 특정한 규칙을 통해 검색을 하는 자료구조다. 각 노드는 하나의 값을 가지며, 다음과 같은 특징이 있다.왼쪽 노드의 값 ≤ 부모 노드의 값 ≤ 오른쪽 노드의 값중복된 값을 갖는 노드가 존재하지 않음이진 탐색 트리의 모든 서브 트리도 이진 탐색 트리따라서 BST는 부모 노드보다 작거나 같은 모든 원소는 항상 왼쪽에 있고, 부모 노드보다 크거나 같은 원소는 항상 오른쪽에 있다. 이를 그림으로 나타내면 다음과 같다. 　  　이러한 BST는 이름에 걸맞게 탐색 속도가 빠르다. BST는 높이에 따라 시간 복잡도가 결정되며, 이를 O(높이)로 표현할..

문제설명 입출력 예제 개념 M개의 카드 중에 N개의 숫자 카드와 같은 것이 몇 개 있는지 출력하는 문제다. map 자료 구조에 저장하여 개수를 출력하면 시간 초과 문제에 걸리게 되는데, 이는 map 자료구조는 연산이 O(logN)의 시간 복잡도를 가지기 때문이다. 즉, M개의 숫자를 하나씩 확인할 때마다 시간 복잡도가 O((N+M) logN)이 되므로 다른 방법을 찾아야 한다. 따라서 시간 복잡도를 줄이는 과정이 필요한데, 이진 탐색을 이용한 std::upper_bound() 함수와 std::lower_bound() 함수를 사용하거나 map의 멤버 함수인 find() 함수와 반복자를 적절하게 이용하면 해결할 수 있다. 풀이 (1) map #include #include #include int main()..

문제설명 입출력 예제 개념 key와 value로 이루어진 map 자료구조를 사용하면 쉽게 해결할 수 있는 문제다. leave가 되어 있는 사원은 map에서 제거하고, enter만 되어있는 사원만 출력하면 해결할 수 있다. 마지막에 사전의 역순으로 출력하라고 되어 있음에 유의하자. 풀이 #include #include #include int main() { std::map m; int N; std::cin >> N; 사원의 이름과 상태가 문자열로 되어 있으므로 key와 value 모두 문자열로 받는 맵을 초기화 한다. 그리고 로그 수 N을 초기화한다. while (N--) { std::string name, log; std::cin >> name >> log; m[name] = log; } 이름과 로그를 ..

트리 순회개요　앞선 포스팅에선 트리에 원소를 삽입하는 방법에 대해 알아보았다. 이번 포스팅에선 트리의 원소를 순회하는 방법에 대해 알아보도록 하자. 여기서 순회란 모든 노드를 한 번씩 방문하는 것을 의미한다.본문　트리를 순회하는 방법은 크게 4가지가 존재한다.전위 순회(Preorder traversal): 현재 노드를 먼저 방문하고, 그다음은 현재 노드의 왼쪽 하위 노드, 마지막으로 현재 노드의 오른쪽 하위 노드를 재귀적으로 방문하는 방식.중위 순회(In-order traversal): 왼쪽 노드를 먼저 방문하고, 그다음에는 현재 노드, 마지막으로 오른쪽 노드를 방문하는 방식.후위 순회(Post-order traversal): 두 자식 노드를 먼저 방문한 후, 현재 노드를 방문하는 방식.레벨 순서 순회(..

트리(Tree)  개요　지금까지 다룬 자료 구조는 순방향과 역방향을 지원하는 선형 자료 구조였다. 이러한 구조는 특정 데이터를 검색할 때 순서대로 자료를 찾아나가야 하는 문제점과, 데이터를 저장하기 위해 일정한 공간을 미리 할당해야 하는 등 제한적인 구조를 갖고 있어 복잡한 문제를 해결하는 데 어려움이 있다. 대표적인 문제로는 계층적 문제와 순환 종속성 문제가 있다. 　계층적 문제(Hieararchy Problem)란 계층적 속성을 갖는 자료를 선형 구조로 표현하기 어렵다는 것을 의미한다. 다음과 같은 조직도를 표현한다고 해보자.  　이러한 조직을 표현하기 위해서, 기존에 배운 선형 자료 구조인 배열과 벡터, 리스트를 이용해 표현하기는 어려워 보인다. 　순환 종속성(Cyclic Dependency) 문제..

문제설명 입출력 예제 개념 이 전의 포스팅된 문제와 유사하게 해결할 수 있는 문제다. M개의 문자열 중에 N개의 문자열과 겹치는 게 있는지 개수를 카운팅 하는 문제다. 이진 탐색을 이용하여 개수를 늘리는 식으로 해결할 수 있다. 풀이 #include #include #include int main() { int N, M, count = 0; std::string str; std::vector v; std::cin >> N >> M; 문자열의 개수 N, M과 겹치는 문자열의 개수 count를 초기화한다. 그리고 입력으로 받을 문자열 str과 문자열을 저장할 컨테이너 v를 초기화한다. while (N--) { std::cin >> str; v.push_back(str); } std::sort(v.begin(..

문제설명 입출력 예제 개념 이 문제는 M개의 숫자 카드 중에서 N개의 숫자 카드와 겹치는 카드가 있는지 찾는 문제다. find 함수를 사용하면 최악의 경우, 시간 복잡도가 O(MN)이 되므로 시간 초과 문제에 걸리기 십상이다. 따라서 이진 탐색을 이용해 시간 복잡도를 O(M logN)으로 개선하여 해결하면 된다. 풀이 #include #include #include int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); int N, M, n; std::vector v; 카드의 개수 N, M, 숫자 카드 n을 초기화하고, 숫자 카드들을 담을 컨테이너 vector v를 초기화한다. std::cin >> N; for (int i =..

문제설명 입출력 예제 개념 좌표 압축은 주로 좌표 알고리즘에서 사용되는 기법 중 하나로, 입력으로 받은 좌표 값들을 작은 범위의 정수로 압축하는 것이다. 이를 사용하면 좌표 값이 매우 크거나 작은 경우에도 작은 범위의 정수로 압축해서 사용할 수 있어서, 메모리 사용량과 연산 시간을 줄일 수 있다. 예를 들어, 입력으로 10^5개의 좌표 값이 주어졌을 때, 이 값들이 10^9 이상의 큰 수라면, 메모리를 많이 사용하게 된다. 하지만 좌표 압축 개념을 사용하면, 이 값을 10^5 이하의 작은 수로 압축해서 사용할 수 있다. 문제를 푸는 데 핵심적인 요소는, 입력으로 받은 좌표 값들을 정렬해서 작은 값부터 차례대로 번호를 매길 수 있다는 것이다. 이때 각 값의 번호는 정렬된 배열에서의 인덱스 값과 일치하는데,..

문제설명 입출력 예제 개념 회원의 이름과 나이, 그리고 가입한 순서를 저장하는 구조체를 선언하고, 아래의 조건에 맞게 정렬하여 출력하는 문제다. 앞선 정렬 문제들과 같이 구조체와 연산자 오버로딩을 이용하여 풀었지만, 람다식도 이용하여 풀어보았다. 나이 순으로 정렬 나이가 같다면 가입한 순으로 정렬 풀이 (1) #include #include #include struct User { int _age, _index; std::string _name; }; int main() { int N; std::cin >> N; std::vector v; User라는 구조체 안에 나이에 관한 _age, 순서에 관한 _index, 이름에 관한 _name을 선언한다. 그리고 메인 함수에서 회원의 수를 N으로 초기화하고, U..