'컴퓨터공학 > Program Solving' 카테고리의 다른 글
[BOJ] 5466 팀 프로젝트, 10451 순열 사이클 (0) | 2016.09.25 |
---|---|
[Leetcode] 160323 (0) | 2016.03.23 |
[Leetcode] 160309 (0) | 2016.03.09 |
[Leetcode] 160308 (0) | 2016.03.08 |
[Leetcode]160307 (0) | 2016.03.07 |
[BOJ] 5466 팀 프로젝트, 10451 순열 사이클 (0) | 2016.09.25 |
---|---|
[Leetcode] 160323 (0) | 2016.03.23 |
[Leetcode] 160309 (0) | 2016.03.09 |
[Leetcode] 160308 (0) | 2016.03.08 |
[Leetcode]160307 (0) | 2016.03.07 |
[Clone Graph]
https://leetcode.com/problems/clone-graph/
[Copy List with Random Pointer]
https://leetcode.com/problems/copy-list-with-random-pointer/
HashTable, BFS를 이용하여 푼다.
[Leetcode] 160323 (0) | 2016.03.23 |
---|---|
[Leetcode]160322 (0) | 2016.03.23 |
[Leetcode] 160308 (0) | 2016.03.08 |
[Leetcode]160307 (0) | 2016.03.07 |
[Leetcode] 160302 (0) | 2016.03.02 |
[Spiral Matrix]
https://leetcode.com/problems/spiral-matrix/
[Spiral Matrix2]
https://leetcode.com/problems/spiral-matrix-ii/
spiral 모양으로 돌아가는 것을, 반복문을 이용해 연상할 수 있어야 한다.
[Jump Game]
https://leetcode.com/problems/jump-game/
DP로 풀면 메모리를 많이 사용하기 때문에, GREEDY로 풀어야 한다.
반복문의 현재 인덱스에서 앞으로 나아갈 수 있는 값이(nums[i]+i), 현재 인덱스(i)보다 작으면 더이상 진행할 수 없다.
[Leetcode]160322 (0) | 2016.03.23 |
---|---|
[Leetcode] 160309 (0) | 2016.03.09 |
[Leetcode]160307 (0) | 2016.03.07 |
[Leetcode] 160302 (0) | 2016.03.02 |
[Leetcode] 160301 (0) | 2016.03.02 |
[Fraction to Recurring Decimal]
https://leetcode.com/problems/fraction-to-recurring-decimal/
Recurring Decimal - 순환소수
순환소수는 소수점 아래의 어떤 자리부터 일정한 숫자의 배열이 끝없이 되풀이되는 무한소수
순환소수는 무한등비급수를 이용하여 분수로 나타낼 수 있으므로, 모든 순환소수는 유리수이다.
n/q에서 정수 n을 양의 정수 q로 나누면 나머지로 가능한 수는 0부터 (q-1)뿐이므로 나누는 과정에서 나머지가 반복될 수 밖에 없다.
[Product of Array Except]
https://leetcode.com/problems/product-of-array-except-self/
변수 2개를 사용한다.
[Leetcode] 160309 (0) | 2016.03.09 |
---|---|
[Leetcode] 160308 (0) | 2016.03.08 |
[Leetcode] 160302 (0) | 2016.03.02 |
[Leetcode] 160301 (0) | 2016.03.02 |
[leetcode] 160229 (0) | 2016.02.29 |
[Valid Sudoku]
https://leetcode.com/problems/valid-sudoku/
[Sudoku Solver]
https://leetcode.com/problems/sudoku-solver/
스도쿠 게임은 보통 backtracking으로 푼다.
[Leetcode] 160308 (0) | 2016.03.08 |
---|---|
[Leetcode]160307 (0) | 2016.03.07 |
[Leetcode] 160301 (0) | 2016.03.02 |
[leetcode] 160229 (0) | 2016.02.29 |
[leetcode]160225 (0) | 2016.02.25 |
[Largest Rectangle in Histogram]
https://leetcode.com/problems/largest-rectangle-in-histogram/
stack을 이용해 O(n) 시간에 구할 수 있다.
height = [2,1,5,6,2,3]
아래와 같은 Histogram이 입력으로 들어온다고 가정하자.
모든 height를 방문하면서 stack에 집어 넣는데, 규칙은 다음과 같다.
현재 반복문의 인덱스를 i라고 할 때,
height[i] <= height[stack.top()] 인 모든 경우에 대하여
stack.pop()을 한 후, 사각형의 넓이를 계산하는 과정을 수행한다.
아래 그림에서 회색 음영의 사각형은 현재 stack에 추가되는 사각형을 의미한다.
점선 테두리의 사각형은 stack에서 pop 되는 사각형이고, 노란색 음영의 사각형은 이 떄 계산하는 사각형의 넓이를 의미한다.
모든 사각형이 stack에 추가되었을 때, stack에 남아 있는 사각형의 넓이를 계산할 수 없다. 따라서, height 배열의 마지막에 0 을 추가한 후, 반복문 순회를 시작해야 한다. 그러면 마지막에 남은 사각형의 넓이를 계산할 수 있다.
[Maximal Rectangle]
https://leetcode.com/problems/maximal-rectangle/
[Largest Rectangle in Histogram] 문제의 응용 버전이다.
입력으로 받은 큰 사각형에서 반복문을 통해 각 row마다 높이를 계산하는 작업을 전처리한 후, 각 row마다 [Largest Rectangle in Histogram] 문제처럼 stack을 이용한 sweeping 작업을 수행한다.
O(n^2) 의 시간이 걸린다.
DP로 문제를 푸는 방법은 답이 생각나지 않아서 해결하지 못했다.
[Maximal Square]
https://leetcode.com/problems/maximal-square/
[Maximal Rectangle]문제의 하위 버전이다.
DP를 이용하여 쉽게 풀 수 있다.
[Path Sum]
https://leetcode.com/problems/path-sum/
[Path Sum 2]
https://leetcode.com/problems/path-sum-ii/
[Binary Tree Paths]
https://leetcode.com/problems/binary-tree-paths/
모두 stack을 이용하여 풀 수 있다.
[Leetcode]160307 (0) | 2016.03.07 |
---|---|
[Leetcode] 160302 (0) | 2016.03.02 |
[leetcode] 160229 (0) | 2016.02.29 |
[leetcode]160225 (0) | 2016.02.25 |
[leetcode.com] 160224 (0) | 2016.02.24 |
[Symmetric Tree]
https://leetcode.com/problems/symmetric-tree/
DFS
[Minimum Depth of Binary Tree]
https://leetcode.com/problems/minimum-depth-of-binary-tree/
DFS로 구현, BFS로도 구현 가능
[Excel Sheet Column Number]
https://leetcode.com/problems/excel-sheet-column-number/
math
[Leetcode] 160302 (0) | 2016.03.02 |
---|---|
[Leetcode] 160301 (0) | 2016.03.02 |
[leetcode] 160229 (0) | 2016.02.29 |
[leetcode]160225 (0) | 2016.02.25 |
[leetcode.com] 160223 (0) | 2016.02.23 |
[Palindrome Partitioning]
https://leetcode.com/problems/palindrome-partitioning/
def dfs(sublist, str)
if not str
ret += sublist
else
for str의 0번 인덱스 시작 길이가 1부터 len(str)까지의 모든 substring
if substring is palindrome
dfs(sublist += substring, str에서 substring을 제외한 나머지)
[Binary Tree Preorder, Inorder, Postorder]
https://leetcode.com/problems/binary-tree-preorder-traversal/
https://leetcode.com/problems/binary-tree-inorder-traversal/
https://leetcode.com/problems/binary-tree-postorder-traversal/
stack, hash
reverse(preorder) = postorder
[Leetcode] 160302 (0) | 2016.03.02 |
---|---|
[Leetcode] 160301 (0) | 2016.03.02 |
[leetcode] 160229 (0) | 2016.02.29 |
[leetcode]160225 (0) | 2016.02.25 |
[leetcode.com] 160224 (0) | 2016.02.24 |