난쟁이 개발자

개념1. 백트래킹(Backtracking) 알고리즘의 작동 원리를 설명하고, 상태 공간 트리(State Space Tree) 개념과 연관 지어 설명해주세요. 주로 어떤 방식으로 구현되며 (예:재귀), 그 이유는 무엇인가요?더보기백트래킹 알고리즘은 어떤 가능성이 없는 곳을 알아보고 되돌아 가는 것입니다. 책을 살펴보면, 시작점(루트)은 빈 리스트로 시작을 한다. 숫자가 4개가 포함되어 있으니, level 0 -> 1로 내려가면, 빈 리스트에 하나의 숫자씩 차지하게 된다. res = [[1], [2], [3], [4]]숫자 2개의 조합을 완성해야 하므로, 이 아래로 선택한 숫자를 제외한 3개씩 노드를 가지게 되면 총 12개 조합이 완성되고, 이를 모두 통과하게 되면 O(12)이 될 것이다. ($O(N^{2}..

개념 문제BFS(너비 우선 탐색) 알고리즘의 작동 원리를 설명하고, 어떤 자료구조를 사용하는지, 그리고 그 이유는 무엇인지 설명해주세요.더보기BFS(너비 우선 탐색)는 시작 노드와 거리가 가장 가까운 노드를 우선하여 방문하는 방식의 알고리즘입니다. 이를 위해 '큐' 자료구조를 채택하여 시작 노드를 큐에 넣은 다음, 방문 처리를 합니다. 이후,1. 큐가 비었는지 확인. 큐가 비었다면 방문할 수 있는 모든 노드를 방문했기 때문에 탐색을 종료합니다.2. 큐에서 노드를 팝합니다.3. 팝한 노드와 인접한 모든 노드를 확인하고 그 중 아직 방문하지 않은 노드는 큐에 푸시하여 방문처리이 과정을 반복하는 것이 BFS입니다.고려 사항으로는1. 현재 방문한 노드와 직접 연결된 모든 노드를 방문할 수 있어야 하고,2. 이미..

개념문제DFS를 구현하는 대표적인 두 가지 방법은 재귀 호출을 이용하는 것과 명시적인 스택(Stack) 자료구조를 사용하는 것입니다. 각 구현 방식의 장단점을 비교 설명해주세요.더보기1. 재귀재귀 함수를 호출할 때마다 호출한 함수는 시스템 스택이라는 곳에 쌓이므로 DFS에 적용하여 구현하게 된다. 장점 : 코드의 간결함, (호출 스택이 DFS의 진행 과정을 자연스럽게 관리)단점 : 스택오버플로우 발생 가능성이 높다, (함수 호출 오버헤드로 인한 성능 저하).직접 문제를 풀면서 느꼈던 재귀 함수와 DFS의 장단점은 코드가 간결한 만큼, 스택오버플로우(시간초과, 메모리초과) 발생 확률이 타 문제들보다 많았다는 점이다. 메모리초과가 나지 않으면 시간초과로 이어지는 경우가 많았다. 괄호 내 내용은 각종 AI툴들..

Best Time to Buy and Sell Stock IIYou are given an integer array prices where prices[i] is the price of a given stock on the ith day.On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.Find and return the maximum profit you can achieve. Example 1:Input: prices = [7..

Best Time to Buy and Sell StockYou are given an array prices where prices[i] is the price of a given stock on the ith day.You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0. Example 1:Input: prices = [7,1..

Best Time to Buy and Sell Stock IIIYou are given an array prices where prices[i] is the price of a given stock on the ith day.Find the maximum profit you can achieve. You may complete at most two transactions.Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again). Example 1:Input: prices = [3,3,5,0,0,3,1,4]Output: 6Explanation: Buy o..

Add Two NumbersYou are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.You may assume the two numbers do not contain any leading zero, except the number 0 itself. Example 1:Input: l1 = [2,4,3], l2 = [5,6,4]Output: [7,0,8]Explana..

Average of Levels in Binary TreeGiven the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10-5 of the actual answer will be accepted. Example 1:Input: root = [3,9,20,null,null,15,7]Output: [3.00000,14.50000,11.00000]Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11.Hence return [3, ..

Add BinaryGiven two binary strings a and b, return their sum as a binary string. Example 1:Input: a = "11", b = "1"Output: "100"Example 2:Input: a = "1010", b = "1011"Output: "10101" Constraints:1 4a and b consist only of '0' or '1' characters.Each string does not contain leading zeros except for the zero itself.class Solution: def addBinary(self, a: str, b: str) -> str: decimal_a = de..

Basic CalculatorGiven a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval(). Example 1:Input: s = "1 + 1"Output: 2Example 2:Input: s = " 2-1 + 2 "Output: 3Example 3:Input: s = "(1+(4+5+2)-3)+(6+8)"Out..