Contents
3.5.1. 내용 ¶
* 참가자 :
- 오늘 푼 문제
- 곽병학
- 김태진
- 헛간(저번주 문제)
- n 마리의 쥐가 크기가 같은 n 개의 버터를 먹는데 n 시간이 걸린다고 할 때 , m 마리의 쥐가 m 개의 버터를 먹는데 걸리는 시간을 구하는것이 문제이다. 각각의 쥐가 치즈를 먹는 속도는 모두 동일하다고 한다.
- 헛간(저번주 문제)
- 권영기
- 곽병학
- 풀어보기 : land
3.14. 6월 27일 ¶
- 김태진 : Dynamic Programming 6.1~6.3
- Shortest Path : DAG(directed acyclic graphs)로 바꾼 후 Source에서부터 dist(v) = min{dist(v) + l(u,v)}사용
- 170p
- 170p
- Longest increasing subsequence : DAG로 바꾼다.(increasing하는 곳에만 edge생성됨) 이후 가장 많이 방문하도록 L(j) = 1+ max{L(i) : (i,j)}수행
- 최대 path의 길이를 구한 후에 뒤로 돌아가면서 숫자가 줄어드는 녀석들을 스택에 담으면 path도 구할 수 있다.
- 최대 path의 길이를 구한 후에 뒤로 돌아가면서 숫자가 줄어드는 녀석들을 스택에 담으면 path도 구할 수 있다.
- Edit distance : 글자 최소 오류개수 구하기 (exponential과 polynomial의 최소 오류는 6개.)
- Similar to DTW
- Similar to DTW
- Shortest Path : DAG(directed acyclic graphs)로 바꾼 후 Source에서부터 dist(v) = min{dist(v) + l(u,v)}사용
- 권영기 : 3장 그래프
- 곽병학 : Hoffman code - 쓸데없을거 같음..
3.15.2. 내용 ¶
- 김태진 : DP
- Maximum Sum - kadane's algorithm
- 권영기 :
- Topological sort -
- Strongly Connected Component(SCC)
- Tarjan's strongly connected components algorithm - 링크
- URL에 '가 들어가면 개고생.
- URL에 '가 들어가면 개고생.
- Tarjan's strongly connected components algorithm - 링크
- Topological sort -
- 곽병학 :
3.16.2. 내용 ¶
- 김태진 : Dynamic Programming
- KnapsackProblem/김태진 : 0/1냅색 문제 이제 좀 이해했음다..
- KnapsackProblem/김태진 : 0/1냅색 문제 이제 좀 이해했음다..
- 곽병학 : 한붓그리기?
- 권영기 : ?
