알고리즘 트레이닝

문제 Given the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Example 1: Input: root = [3,9,20,null,null,15,7] Output: 3Example 2: Input: root = [1,null,2] Output: 2Example 3: Input: root = [] Output: 0Example 4: Input: root = [0] Output: 1Constraints: The number of ..

문제 Given anon-emptyarray of digits representing a non-negative integer, plus one to the integer. The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit. You may assume the integer does not contain any leading zero, except the number 0 itself. Example 1: Input: [1,2,3] Output: [1,2,4] Explanation: The array repre..

문제 (요약) 주어진 수열이 문제에서 정의한 순열인지 판단하라. 길이 N인 순열은 1부터 N까지의 자연수를 중복 없이 순서에 상관없이 모두 사용하여 만든 수열을 의미한다. 접근 입력된 수열을 검사하여 모두 1회씩 출현했는지 확인한다. 풀이 #include #include using namespace std; string fnSolve(vector &v, int N) { for (int i = 1; i > T; for (int t = 1; t > N; vector v(N+1); for (int i = 0; i > idx; v[idx] += 1; } cout

개요 단일 연결 리스트는 한쪽 방향으로 연결된 노드로 구성됩니다. 따라서 액세스 및 순회는 첫 번째 노드인 Head에서 시작하여 한번에 한 노드씩 확인하며 진행해야 합니다. 만약 역순으로 액세스 및 순회를 하고자 한다면 이를 효율적으로 할 수는 없을 것입니다. 순회를 위하여 매번 Head에서 시작하여 이전 순회보다 한 노드씩 앞에서 중단하는 방식으로 여러 차례 반복적으로 순회를 수행해야 하기 때문입니다. 따라서 만약 역순으로 순회를 해야 하는 경우가 필요하다면 이번 포스트에서 소개하는 이중 연결리스트(Doubly Linked List)를 도입하는 것이 좋습니다. 구현 (C++) 이중 연결 리스트 각 노드는 3가지 멤버변수를 가지고 있습니다. 두 가지는 각각 이전 노드와 다음 노드를 가리키는 링크 값(포인..

문제 You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself. Example: Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 ..

문제 Given two binary trees, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical and the nodes have the same value. Example 1: Input: 1 1 / \ / \ 2 3 2 3 [1,2,3], [1,2,3] Output: trueExample 2: Input: 1 1 / \ 2 2 [1,2], [1,null,2] Output: falseExample 3: Input: 1 1 / \ / \ 2 1 1 2 [1,2,1], [1,1,2] Output: false풀이 class ..

문제 Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Note: The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. Example: Input: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6]풀이 ..

문제 Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. Example: Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4 풀이 Divide & Conquer 전략에 따라 작은 문제를 해결하고, 이를 조합하여 큰 문제를 해결한다. class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: if l1 is None : return l2 if l2 is None : return l1 if..