음하하하

https://www.acmicpc.net/problem/9466

난이도 : MH

https://www.acmicpc.net/problem/10451

난이도 : MH

https://github.com/simjaemun2/BaekJoon/blob/master/BOJ9466/BOJ9466.cpp

https://github.com/simjaemun2/BaekJoon/blob/master/BOJ10451/BOJ10451.cpp

DFS

Graph Cycle 검출

[Perfect Squares]

https://leetcode.com/problems/perfect-squares/

DP를 이용

BFS or MATH를 이용하여 풀이 가능

- Python

1. 2**3 = 8

2. math.sqrt(4) = 2

3. for문에서 가능하면 xrange를 쓰자

- xrange는 필요한 반복 요소만 생성

- range는 list형태로 모든 반복 요소를 포함하여 생성하기 때문에 시간 및 메모리를 더 많이 사용함

[Decode Ways]

https://leetcode.com/problems/decode-ways/

DP를 이용하여 푼다.

예외처리에 유의한다.

[Clone Graph]

https://leetcode.com/problems/clone-graph/

[Copy List with Random Pointer]

https://leetcode.com/problems/copy-list-with-random-pointer/

HashTable, BFS를 이용하여 푼다.

[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)보다 작으면 더이상 진행할 수 없다.

1. http://www.scala-lang.org/download/ 에서 Scala Binary 다운

- JRE 1.6 이상이 미리 설치되어 있어야 함

2. https://www.jetbrains.com/idea/에서 Intellij IDE를 다운

- 학생 이메일이 있으면, 1년동안 사용 가능 라이센스를 줌

- 라이센스는 1년마다 갱신 가능

- 교육용 목적으로만 사용해야 함

3.Intellij 실행 전, 설정 스크립트 수정을 통한 성능 튜닝(WIN 64비트 설정 기준)

- [C:\Program Files (x86)\JetBrains\IntelliJ IDEA 15.0.4\bin\idea64.exe.vmoptions]파일을 열어 아래 URL에 있는 스크립트로 대체한다.

- https://gist.github.com/P7h/4388881

4. Intellij 설치 시, Scala Plugin을 설치

[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개를 사용한다.

[Valid Sudoku]

https://leetcode.com/problems/valid-sudoku/

[Sudoku Solver]

https://leetcode.com/problems/sudoku-solver/

스도쿠 게임은 보통 backtracking으로 푼다.

[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을 이용하여 풀 수 있다.

[Implement Stack using Queues]

https://leetcode.com/problems/implement-stack-using-queues/

[Implement Queue using Stacks]

https://leetcode.com/problems/implement-queue-using-stacks/

stack, queue를 2개씩 만들어서, 하나의 stack or queue에 pop()할 item을 하나씩 유지

[Simplify Path]

https://leetcode.com/problems/simplify-path/

stack

Python "///".split("/") = ['','','',''] 과 같이 리턴