Difference between r1.9 and the current

@@ -12,12 +12,12 @@

2021.4.7.
2021.4.28.
2021.5.5.

2021.5.12.

Describe 알고있니/이상진 here

### 21.05.12

-> ### 21.05.12

* DP (memoization, tabulation)

memoization은 top-down 방식으로 풀이하는 방식임. 민욱님은 이걸 연마했다고 함..

@@ -45,10 +45,11 @@

PS는 보통 코드 이쁘게 안짠다..ㅎ

코테는 보통 골3에서 끊긴다.

코테는 합격이 보통 골3에서 끊긴다. (max 다3)

구사가 - 랭킹 1위

DP:: 10942참조

* 아무튼 테이블로 문제풀기!
LIS (Longest Increasing Subsequence) 를 손으로 계산해서 그린 테이블 주어짐.
keywwords...

@@ -60,3 +61,72 @@

## subsequence와 substring의 차이?
-> 부분수열은 원소끼리 떨어져 있어도 되고, 부분문자열은 원소들이 붙어있어야 함.

-> ### 21.05.24

- 그래프

민욱

라이브 코딩...

테마:: 그래프나 트리가 아니라, 구현력을 위한 테마 (벡터를 노드, 엣지로 해결하기.) 참조 https://sunrinnote.tistory.com/101

구현력 사고력..

(실)_

뭐가 안된다 -> 일단 파라메터가 모자란가? (민욱의 습관임.)

(골)_

시작점 후보가 여러개이면 BFS일 가능성이 크다.

일단 무지성으로 당연히 필요한거 적고

bfs니까 queue필요하다.

"가능하면 쉬운 애 부터 푼다 -> priority_queue 를 사용하자."

priority queue에 음수를 넣으면 작은 것 부터 나온다. (야매꼼수)

그래프는 문제를 위한 도구

민욱은 DP도 그래프로 푼다.

실제로는 숫자 뭉탱이인데 그래프를 사용하면 우리가 알만한 문제로 접근됨. (추상화)

그래프는 사실상 재귀함수.

못풀겠으면 일단 그래프로 생각하고 접근한다(민욱)

네오빔 사용함.

sandbox 디렉토리 굿.

#** SPANNING TREE (신장트리)**

## 그래프를 트리로 만들었을 때, 이를 spanning tree라고 한다.

* 노드간 경로가 오직 하나뿐인 topology(위상: 그래프)

* 루프 순환이 없는 그래프의 일종

* 모든 노드는 연결되며

* 간선의 개수가 (#노드 - 1)

* 비순환 (loop없음)

# 이걸 왜하죠??

- 그래프는 너무 어렵다.

- 다익스트라, 벨만-포드 알고리즘이 전부이다.

그래프를 트리로 만들자 ... 길찾기 알고리즘 (외워버리는게 편하다.) - 다익스트라가 이거 만들고 상받았다.. 그니까 외우는게 편하다.

그래프를 DFS 트리로 만들면...

* 트리 간선

* 순방향 간선

* 역방향 간선

* 교차 간선

위 4가지만 가능하다.

https://bowbowbow.tistory.com/1

무향 그래프라면?

* 트리간선

* 순/역방향만 존재..(교차간선x)

BFS SPANNING TREE

모든 간선은 depth가 1이상 차이나는 노드를 가르키지 않는다. (모든 간선의 양 끝 노드의 depth차이는 1이다.)

https://torbjorn.tistory.com/290

Contents ¶

프로필 ¶

* 16학번
* 96.07.27.
* 낙생고 졸업
* SYSLAB PE

==정모==
2021.3.31.
2021.4.7.
2021.4.28.
2021.5.5.
2021.5.12.

Describe 알고있니/이상진 here

-> ### 21.05.12
* DP (memoization, tabulation)

memoization은 top-down 방식으로 풀이하는 방식임. 민욱님은 이걸 연마했다고 함..
민욱님은 bottom-up풀이가 지능의 영역에 맞닿아 있다고 봄

민욱 지인분은 memoization, 점화식 두개의 이름으로 나누어서 부른다고 한다.

DP에서는 수학적으로 정의 될 수 없는 문제가 없다. (수식적으로 떠오르면 DP라고 생각할 수도 있다.)
일반적으로 3줄을 넘지않는 깔끔한 수식이

생각은 20분간 차근차근, bordercase 까지 보고
코딩이 10분 내로 안된다면, 코딩력이 부족한것

구현력이 부족하다면 양치기로 solved.ac의 실/골 문제들을 하루 10문제씩 양치기로 푼다.

e.g., ACM-ICPC에서 7시간 중 4시간 생각하고 1시간 코드짜는 극단적인 케이스도 있음 (민욱 지인)

9번줄 사용하지 않고 34번 줄에 auto 써도 됨.
17줄 전역변수로 빼면 static안써도 됨

#34 iterator문을 for in문으로 쓸 수 있다.

남의 코드를 많이 읽자

PS는 보통 코드 이쁘게 안짠다..ㅎ

코테는 합격이 보통 골3에서 끊긴다. (max 다3)

구사가 - 랭킹 1위

DP:: 10942참조
* 아무튼 테이블로 문제풀기!
LIS (Longest Increasing Subsequence) 를 손으로 계산해서 그린 테이블 주어짐.
keywwords...
- 단조증가
- 바이토닉 수열
- dpi = max( dpi-1, max(dpj+1, 단 dataji and j

자기보다 앞쪽에 있으면서 가장 큰 값을 참조.

- 보통 DP는 min, max, sum을 사용한다.

-> 부분수열은 원소끼리 떨어져 있어도 되고, 부분문자열은 원소들이 붙어있어야 함.

-> ### 21.05.24

- 그래프

민욱
라이브 코딩...

테마:: 그래프나 트리가 아니라, 구현력을 위한 테마 (벡터를 노드, 엣지로 해결하기.) 참조 https://sunrinnote.tistory.com/101
구현력 사고력..

(실)_
뭐가 안된다 -> 일단 파라메터가 모자란가? (민욱의 습관임.)

(골)_
시작점 후보가 여러개이면 BFS일 가능성이 크다.
일단 무지성으로 당연히 필요한거 적고
bfs니까 queue필요하다.

"가능하면 쉬운 애 부터 푼다 -> priority_queue 를 사용하자."
priority queue에 음수를 넣으면 작은 것 부터 나온다. (야매꼼수)

그래프는 문제를 위한 도구

민욱은 DP도 그래프로 푼다.
실제로는 숫자 뭉탱이인데 그래프를 사용하면 우리가 알만한 문제로 접근됨. (추상화)
그래프는 사실상 재귀함수.

못풀겠으면 일단 그래프로 생각하고 접근한다(민욱)

네오빔 사용함.

sandbox 디렉토리 굿.

#** SPANNING TREE (신장트리)**
* 노드간 경로가 오직 하나뿐인 topology(위상: 그래프)
* 루프 순환이 없는 그래프의 일종

* 모든 노드는 연결되며
* 간선의 개수가 (#노드 - 1)
* 비순환 (loop없음)

# 이걸 왜하죠??
- 그래프는 너무 어렵다.
- 다익스트라, 벨만-포드 알고리즘이 전부이다.

그래프를 트리로 만들자 ... 길찾기 알고리즘 (외워버리는게 편하다.) - 다익스트라가 이거 만들고 상받았다.. 그니까 외우는게 편하다.
그래프를 DFS 트리로 만들면...
* 트리 간선
* 순방향 간선
* 역방향 간선
* 교차 간선
위 4가지만 가능하다.
https://bowbowbow.tistory.com/1

무향 그래프라면?
* 트리간선
* 순/역방향만 존재..(교차간선x)

BFS SPANNING TREE
모든 간선은 depth가 1이상 차이나는 노드를 가르키지 않는다. (모든 간선의 양 끝 노드의 depth차이는 1이다.)
https://torbjorn.tistory.com/290