U E D R , A S I H C RSS

Algorithm Study/CLRS

Difference between r1.14 and the current

@@ -33,6 +33,15 @@
* 다음주: 24장 각자 읽고, 25장 하기로 함.
=== 5주차 (2017/04/23 일) ===
* 25장 읽음
* 다음주: 26.3장 까지 읽기, 문제 풀기
* [컨닝 https://www.acmicpc.net/problem/1014]
* https://www.acmicpc.net/problem/3640
* '''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이므로 항상 짝수임을 알게되었다.
* 구글링한 학습 자료([[http://math.mit.edu/~rothvoss/18.304.1PM/Presentations/2-Chandler-slideslect2.pdf|1]], [[https://resources.mpi-inf.mpg.de/departments/d1/teaching/ss12/AdvancedGraphAlgorithms/Slides14.pdf|2]])에는 위 알고리즘이 '''seidel's algorithm이라고''' 명명되어 있는데 해당 키워드로 검색이 되지 않았다. 알고보니 seidel은 수학자이고 seidel's algorithm은 정식 명칭이 아니라 [[https://en.wikipedia.org/wiki/Gauss%E2%80%93Seidel_method|Gauss Seidel method]]이 정식 명칭인 듯 하다.
* 다음주: '''26.3장''' 까지 읽기, 문제 풀기
* [[https://www.acmicpc.net/problem/1014|컨닝]]
* [[https://www.acmicpc.net/problem/3640|제독]]





1. 개요

2. 진행 상황

2.1. 1주차 (2017/03/26 일)

2.2. 2주차 (2017/04/02 일)

  • 22장을 읽음
  • Topological sort와 Strongly connected components의 pseudocode 설명이 부실하다...
  • 연습문제 3-13의 단일 연결에 대한 이야기
  • 23장 읽어오기
  • 최소 신장 트리 기본 문제 + 못 푼 문제 풀어오기
  • 연습문제 풀고 싶은 것 하나씩 풀어와서 공유

2.3. 3주차 (2017/04/09 일)

  • 23장을 읽음

2.4. 4주차 (2017/04/15 토)

  • 24장 읽기로 했음
    • 이번주 스터디 쉽니다
  • 다음주: 24장 각자 읽고, 25장 하기로 함.

2.5. 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이므로 항상 짝수임을 알게되었다.
    • 구글링한 학습 자료(1, 2)에는 위 알고리즘이 seidel's algorithm이라고 명명되어 있는데 해당 키워드로 검색이 되지 않았다. 알고보니 seidel은 수학자이고 seidel's algorithm은 정식 명칭이 아니라 Gauss Seidel method이 정식 명칭인 듯 하다.
  • 다음주: 26.3장 까지 읽기, 문제 풀기
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:22:27
Processing time 0.0421 sec