무제 무제

문제 Given a 32-bit signed integer, reverse digits of an integer. Example 1: Input: 123 Output: 321 Example 2: Input: -123 Output: -321 Example 3: Input: 120 Output: 21 Note: Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer..

문제 Given a string, find the length of the longest substring without repeating characters. Example 1: Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. Example 2: Input: "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1. Example 3: Input: "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Note that the answer must be a..

어떠한 자료를 트리를 사용해 저장할때 많이 검색되는 단어가 leaf쪽에 있으면 검색 비용이 높음 따라서 검색 빈도에 따라 비용을 최소화 할 수 있는 트리를 구현 어떤 트리가 있을때 이 트리가 Optimal이면 양쪽의 subtree도 optimal이라는 아이디어로 접근 시간복잡도는 O(n^2) 점화식: https://gsmesie692.tistory.com/116 최적 이진 탐색 트리 (Optimal Binary Search Tree) 이전 포스팅에서 설명했던 이진 탐색 트리 (BST) 의 활용 예를 보자. 설명할 때는 보통 이해하기 쉽게 노드에 들어있는 데이터를 숫자로 가정하지만, 실제로 쓰일 때는 문자열이라던가 더 다양한 데이터가 들어갈.. gsmesie692.tistory.com

문제 Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order). The replacement must be in-place and use only constant extra memory. Here are some examples. Inputs are in the left-hand column and its corresponding outputs ..

(key, value)로 이루어진 자료구조 Search Delete Delete 는 평균 O(1) 최악 O(size) Hash Table의 bucket에 값을 넣는 방식은 보통 prime divisor를 사용하는데 이는 divisor를 짝수를 쓰면 항상 짝수는 짝수 bucket에, 홀수는 홀수 bucket에 들어가게 되어 bias가 생김. 홀수 divisor를 쓰면 이런 일이 없고 소수나 20이상의 두 소수의 곱인 수를 쓰면 bias를 더 줄일 수 있음

(key, value)로 이루어진 자료구조 Search Delete Delete 는 평균 O(1) 최악 O(size) Hash Table의 bucket에 값을 넣는 방식은 보통 prime divisor를 사용하는데 이는 divisor를 짝수를 쓰면 항상 짝수는 짝수 bucket에, 홀수는 홀수 bucket에 들어가게 되어 bias가 생김. 홀수 divisor를 쓰면 이런 일이 없고 소수나 20이상의 두 소수의 곱인 수를 쓰면 bias를 더 줄일 수 있음

Vertex와 Edge로 이루어진 자료구조 G=(V,E) Undirected graph - Vertex를 잇는 Edge에 방향이 없는 그래프. 최대 edge 수 n(n-1)/2 (n은 vertex개수) Directed graph - Vertex를 잇는 Edge에 방향이 있는 그래프. 최대 edge 수 n(n-1) Connected component - 현재 연결성을 유지하면서 더 이상 vertex나 edge를 추가할 수 없는 최대한의 subgraph. connected graph에는 오직 하나의 connected component만이 존재 Cycle - 그래프에서 edge를 통한 순환. cycle은 DFS를 활용해 O(V+E)만에 찾을 수 있음 # 사이클 찾기 그래프 문제를 풀다 보면 '사이클을 찾아라'..

문제 There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). You may assume nums1 and nums2 cannot be both empty. Example 1: nums1 = [1, 3] nums2 = [2] The median is 2.0 Example 2: nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5 Approach O(log (m+n)) 만에 풀라는데 혹시나해서 그냥 두 배열..