Coding Test/LeetCode57 [LeetCode] 94. Binary Tree Inorder Traversal [JAVA(자바)] 문제 👉 1. 문제 이진 트리의 루트가 주어지면 노드 값의 순회 순회를 반환합니다. Input: root = [1,null,2,3] Output: [1,3,2]2. 풀이 Inorder : left -> self -> right 3. 코드 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * thi.. 2021. 11. 24. [LeetCode] 70. Climbing Stairs [JAVA(자바)] 문제 👉 1. 문제 (계단 오르기) 계단을 매번 1개 혹은 2개를 오를 수 있을 때, 계단을 오르는 방법은 몇개인가? Input: n = 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step2. 풀이 다이나믹 프로그래밍 (DP) 을 이용한 풀이 피보나치 수열 (단순 재귀 함수) f(n) = f(n-1) + f(n-2) f(5) = f(4) + f(3) -> 재귀함수를 통해 반복적인 연산 수행 f(4) = f(4) + f(2) f(3) = f(2) + f(1) f(5)를 구하기 위해 이전에 연산을 했던 f(4), f(3).. 2021. 11. 24. [LeetCode] 110. Balanced Binary Tree [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (균형 이진 트리) 이진 트리가 높이 균형(Height-Balanced)인지 판단하라. 높이 균형은 모든 노드의 서브 트리 간의 높이 차이가 1 이하인 것을 마한다. 2. 풀이 재귀탐색을 이용한 풀이 3. 코드 # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Codec: def serialize(self, root): """Encodes a tree to a single string. :type root: TreeNo.. 2021. 11. 24. [LeetCode] 39. Combination Sum [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (조합의 합) 숫자 집합 candidates를 조합하여 합이 target이 되는 원소를 나열하라. 각 원소는 중복으로 나열 가능하다. 2. 풀이 DFS를 이용한 풀이 3. 코드 class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: def dfs(csum, idx, path): if csum < 0: return if csum == 0: ret.append(path[:]) return for i in range(idx, len(candidates)): dfs(csum - candidates[i], i, path +.. 2021. 11. 23. [LeetCode] 22. Generate Parentheses [JAVA(자바)] 문제 👉 https://leetcode.com/problems/generate-parentheses/ 1. 문제 (괄호 생성) n 쌍의 괄호의 모든 조합을 생성한다. Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"] 2. 풀이 백트래킹을 이용한 풀이 backtracking == recursion + termination check termination check : ( 와 ) 의 개수가 n 일 때 종료 recurse : ( 의 개수가 n 보다 작을 때 ( 추가 ) 의 개수가 ( 의 개수 보다 작을 때 ) 추가 3. 코드 백트래킹을 이용한 풀이 class Solution { // numClosed > numOpen -> invalid .. 2021. 11. 23. [LeetCode] 771. Jewels and Stones [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (보석과 돌) 돌에 보석이 몇개 있는지 구해라. (대소문자 구분) 2. 풀이 해시를 이용한 풀이 Counter를 이용한 풀이 파이썬 스타일을 이용한 풀이 3. 코드 해시를 이용한 풀이 from collections import defaultdict class Solution: def numJewelsInStones(self, jewels: str, stones: str) -> int: ret, dic = 0, defaultdict(int) for s in stones: dic[s] += 1 for j in jewels: ret += dic[j] return ret Counter를 이용한 풀이 from collecti.. 2021. 11. 23. [LeetCode] 739 Daily Temperatures [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (일일 온도) 매일의 화씨 온도 리스트 T를 입력받아, 더 따뜻한 날씨를 위해서는 며칠을 더 기다려야하는지를 출력하라. 2. 풀이 스택을 이용한 풀이 스택에 인덱스를 넣기 전에 해당 인덱스의 온도 값이 추가되는 온도와 비교한다 3. 코드 스택을 이용한 풀이 class Solution: def dailyTemperatures(self, T: List[int]) -> List[int]: st, ret = [], [0] * len(T) for idx, val in enumerate(T): while st and T[st[-1]] < val: last = st.pop() ret[last] = idx - last st.app.. 2021. 11. 23. [LeetCode] 347. Top K Frequent Elements [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (상위 K 빈도 요소) k번 이상 등장하는 요소를 추출하라. 2. 풀이 해시와 Counter를 이용한 풀이 zip()와 Counter를 이용한 풀이 3. 코드 해시와 Counter를 이용한 풀이 from collections import Counter class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: ret = [] cnt = Counter(nums).most_common(k) for i in range(k): ret.append(cnt[i][0]) return ret zip()와 Counter를 이용한 풀이 from colle.. 2021. 11. 23. [LeetCode] 316. Remove Duplicate Letters [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (중복 문자 제거) 중복된 문자를 제외하고 사전식 순서 중 가장 작게 만들어라. Example 1: Input: s = "bcabc" Output: "abc" Example 2: Input: s = "cbacdcbc" Output: "acdb" 2. 풀이 스택의 개념을 이용한 풀이 (list를 stack처럼 활용하는 문제) 사전에서 가장 앞에 나오게 중복된 문자를 제거하는 문제이다. 문자열의 문자를 미리 카운팅한 후 스택에 다음과 같은 조건에 맞춰 문자를 추가한다. 추가하는 문자가 스택에 존재하지 않을 경우 스택의 마지막 문자가 추가하는 문자 보다 사전 순위가 크고 카운팅 수가 0 보다 클 때 스택의 문자를 계속해서.. 2021. 11. 23. 이전 1 2 3 4 5 6 7 다음
