More actions
No edit summary |
No edit summary |
||
| Line 34: | Line 34: | ||
=== 5주차 (2017/04/23 일) === | === 5주차 (2017/04/23 일) === | ||
* 25장 읽음 | * 25장 읽음 | ||
** APSP(All Pairs of Shortest Path) 알고리즘 중 Matrix multiplication 알고리즘에 대해 이야기 함 | |||
while m < n-1 { | |||
L^(2m) = L^(m)*L^(m) | |||
m = m*2 | |||
} | |||
** 이 때 m = n-1이고 n이 짝수이면 m은 홀수인데 어떻게 결과를 얻는가 혼란스러웠는데 m < n-1동안 루프를 반복하는 것이고 마지막 L의 차수는 2^m이므로 항상 짝수임을 알게되었다. | |||
** 구글링한 학습 자료에는 위 알고리즘이 seidel's algorithm이라고 명명되어 있는데 해당 키워드로 검색이 되지 않았다. 알고보니 seidel은 수학자이고 seidel's algorithm은 정식 명칭이 아니라 [[https://en.wikipedia.org/wiki/Gauss%E2%80%93Seidel_method|Gauss Seidel method]]이 정식 명칭인 듯 하다. | |||
* 다음주: 26.3장 까지 읽기, 문제 풀기 | * 다음주: 26.3장 까지 읽기, 문제 풀기 | ||
** [[https://www.acmicpc.net/problem/1014|컨닝]] | ** [[https://www.acmicpc.net/problem/1014|컨닝]] | ||
** [[https://www.acmicpc.net/problem/3640|제독]] | ** [[https://www.acmicpc.net/problem/3640|제독]] | ||
Revision as of 13:50, 23 April 2017
개요
- `Introduction to Algorithms` 책으로 행아웃 온라인 스터디를 합니다.
- 기본적으로 매주 토요일 오전 11시, 혹은 일요일 오전 11시
- 참가자 : 서지혜, 최다인
- [대한 좋은 글]
진행 상황
1주차 (2017/03/26 일)
- 1장을 읽음
- 22장 그래프로 바로 건너뜀. 22장 읽기
- 그래프 기본 문제 풀어보기
- 연습문제 하나씩 풀어와서 공유
2주차 (2017/04/02 일)
- 22장을 읽음
- Topological sort와 Strongly connected components의 pseudocode 설명이 부실하다...
- 연습문제 3-13의 단일 연결에 대한 이야기
- 23장 읽어오기
- 최소 신장 트리 기본 문제 + 못 푼 문제 풀어오기
- [연결]
- 연습문제 풀고 싶은 것 하나씩 풀어와서 공유
3주차 (2017/04/09 일)
- 23장을 읽음
4주차 (2017/04/15 토)
- 24장 읽기로 했음
- 이번주 스터디 쉽니다
- 다음주: 24장 각자 읽고, 25장 하기로 함.
5주차 (2017/04/23 일)
- 25장 읽음
- APSP(All Pairs of Shortest Path) 알고리즘 중 Matrix multiplication 알고리즘에 대해 이야기 함
while m < n-1 {
L^(2m) = L^(m)*L^(m)
m = m*2
}
- 이 때 m = n-1이고 n이 짝수이면 m은 홀수인데 어떻게 결과를 얻는가 혼란스러웠는데 m < n-1동안 루프를 반복하는 것이고 마지막 L의 차수는 2^m이므로 항상 짝수임을 알게되었다.
- 구글링한 학습 자료에는 위 알고리즘이 seidel's algorithm이라고 명명되어 있는데 해당 키워드로 검색이 되지 않았다. 알고보니 seidel은 수학자이고 seidel's algorithm은 정식 명칭이 아니라 [Seidel method]이 정식 명칭인 듯 하다.
- 다음주: 26.3장 까지 읽기, 문제 풀기