전체 글
-
[LeetCode] 897. Increasing Order Search Tree c++Coding Test/LeetCode 2022. 9. 27. 12:49
문제 Given the root of a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only one right child. 이진탐색트리의 값들을 node.right로 오름차순으로 정렬하는 문제이다. 주어진 이진탐색트리들은 node.left → node.val → node.right 순으로 값들이 오름차순으로 정렬되어 있다. 문제 해결 1. root노드의 left 먼저 탐색 2. 최하위 까지 탐색했다면 ans노드의 right에 root값을 저장 3. ans노드를 right로 ..
-
[LeetCode] 617. Merge Two Binary Trees c++Coding Test/LeetCode 2022. 9. 27. 11:10
문제 You are given two binary trees root1 and root2. Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of t..
-
[LeetCode] 2331. Evaluate Boolean Binary Tree c++Coding Test/LeetCode 2022. 9. 26. 21:43
문제 You are given the root of a full binary tree with the following properties: Leaf nodes have either the value 0 or 1, where 0 represents False and 1 represents True. Non-leaf nodes have either the value 2 or 3, where 2 represents the boolean OR and 3 represents the boolean AND. The evaluation of a node is as follows: If the node is a leaf node, the evaluation is the value of the node, i.e. Tru..
-
[LeetCode] 938. Range Sum of BST c++Coding Test/LeetCode 2022. 9. 26. 18:11
문제 Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high]. 이진탐색트리의 node중에 low와 high사이에 있는 값을 모두 더한 값을 구하는 문제이다. 문제 해결 class Solution { public: int nSum = 0; int rangeSumBST(TreeNode* root, int low, int high) { if(root == NULL) return nSum; if(root->val >= low && root-> val val; } rangeSumBST..
-
[LeetCode] 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree c++Coding Test/LeetCode 2022. 9. 26. 15:17
문제 Given two binary trees original and cloned and given a reference to a node target in the original tree. The cloned tree is a copy of the original tree. Return a reference to the same node in the cloned tree. Note that you are not allowed to change any of the two trees or the target node and the answer must be a reference to a node in the cloned tree. original 트리에 target노드를 찾는 문제이다. 문제 해결 Tree..
-
[프로그래머스] 양궁대회 c++Coding Test/programmers 2022. 9. 26. 13:30
문제 설명 카카오배 양궁대회 결승전에 라이언과 어피치가 대결한다. 어피치가 먼저 화살을 모두 쏜 후, 라이언이 화살을 모두 쐈을 때, 라이언이 큰 점수 차이로 이기는 방법을 구하는 문제이다. (방법이 여러개라면, 가장 낮은 점수를 더 많이 맞히 경우가 정답이다.) 점수 계산법 - k점을 여러 발 맞혀도 k점 보다 많은 점수를 가져가는 게 아니고 k점만 가져감. 10점에 어피치가 3발, 라이언이 2발 쐈다면 어피치가 10점을 얻게 되고 라이언은 0점을 얻게된다. 라이언이 점수를 획득하기 위해서는 어피치보다 +1개를 쏴야 점수도 얻고 불필요한 화살 소모를 줄일 수 있다. 효율적으로 점수를 획득해야 한다. 불필요한 화살 소모는 다음과 같다. 1) K점 과녁에 a개 이하의 화살을 쏘는 경우 2) K점 과녁에 a..
-
[codility] MinAbsSum c++Coding Test/codility 2022. 9. 23. 21:15
문제 문제 해결 각 원소로 만들 수 있는 합의 개수 구하고, 그 합들을 이용해 전체 합에서 가장 작은 수가 구해질 때 까지 빼나간다. 1. A행렬의 원소를 모두 양수로 전환한다. A원소에 1 or -1 곱한 뒤 합을 구하는 거라 A의 원소가 양수여도 상관없다. 2. 양수로 변환된 A행렬의 원소의 합을 구하고 최댓값도 구한다. 최댓값을 구하는 이유는 각 원소의 개수를 구하는 것이고, 전체 합을 구하는 이유는 답의 가장 최악의 경우는 전체 합이기 때문 3. 각 원소마다 돌면서 가능한 부분 합들을 구한다. 이전에 가능한 부분합이 있었다면, 단순히 현재 원소의 개수를 넣어준다. 처음 만들어진 부분합이라면, 재사용한 것을 표기하기 위해 -1 한다. 4. 부분 합들을 전체합의 절반까지 계산하면서 전체 합에서 2배만..
-
[자료구조] Linked list (연결리스트)Computer Science/Data Structure 2022. 9. 23. 21:11
Linked List 란? node라는 객체로 이루어져 있다. 여러개의 node를 연결함으로써 데이터 표현 가능 시작(주소) - 연결(link) - 끝(null pointer or circular) 코드로 아래와 같이 구현할 수 있다. typedef struct Node{ int data; Node *next; }Node; Linked list 장점 동적으로 메모리 사용가능 메모리 효율적 사용 데이터 재구성 용이 대용량 데이터 처리 적합 Linked list 단점 특정 위치 데이터 검색 느림 메모리를 추가적으로 사용해야 함 Singly Linked list Circularly Linked list : 마지막 노드가 다시 처음 노드를 가리킴.