AlgorithmStudy/CLRS: Difference between revisions

Latest revision as of 15:27, 25 April 2017

개요

`Introduction to Algorithms` 책으로 행아웃 온라인 스터디를 합니다.
기본적으로 매주 토요일 오전 11시, 혹은 일요일 오전 11시
참가자 : 서지혜, 최다인

[대한 좋은 글]

진행 상황

1주차 (2017/03/26 일)

1장을 읽음
22장 그래프로 바로 건너뜀. 22장 읽기
그래프 기본 문제 풀어보기
- [[1]]
- [UP)]
- [[2]]
연습문제 하나씩 풀어와서 공유
- 서지혜 : 22.5-2
- 최다인 : 22.3-13

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이므로 항상 짝수임을 알게되었다.
- 구글링한 학습 자료([[3]], [[4]])에는 위 알고리즘이 seidel's algorithm이라고 명명되어 있는데 해당 키워드로 검색이 되지 않았다. 알고보니 seidel은 수학자이고 seidel's algorithm은 정식 명칭이 아니라 [Seidel method]이 정식 명칭인 듯 하다.
다음주: 26.3장 까지 읽기, 문제 풀기
- [[5]]
- [[6]]

@@ Line 3: / Line 3: @@
 == 개요 ==
 * `Introduction to Algorithms` 책으로 행아웃 온라인 스터디를 합니다.
+* 기본적으로 매주 토요일 오전 11시, 혹은 일요일 오전 11시
 * 참가자 : [[서지혜]], [[최다인]]
+* [[http://hothobbang.tistory.com/m/59|공부방법에 대한 좋은 글]]
 == 진행 상황 ==
 === 1주차 (2017/03/26 일) ===
@@ Line 10: / Line 12: @@
 * 22장 그래프로 바로 건너뜀. 22장 읽기
 * 그래프 기본 문제 풀어보기
-** [[https://www.acmicpc.net/problem/7569|토마토]]
+** [[https://www.acmicpc.net/problem/7576|토마토]]
+** [[https://www.acmicpc.net/problem/7579|토마토(난이도 UP)]]
 ** [[https://www.acmicpc.net/problem/2606|바이러스]]
 * 연습문제 하나씩 풀어와서 공유
 ** [[서지혜]] : 22.5-2
 ** [[최다인]] : 22.3-13
+=== 2주차 (2017/04/02 일) ===
+* 22장을 읽음
+* Topological sort와 Strongly connected components의 pseudocode 설명이 부실하다...
+* 연습문제 3-13의 단일 연결에 대한 이야기
+* 23장 읽어오기
+* 최소 신장 트리 기본 문제 + 못 푼 문제 풀어오기
+** [[https://www.acmicpc.net/problem/1922|네트워크 연결]]
+* 연습문제 풀고 싶은 것 하나씩 풀어와서 공유
+=== 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 &lt; 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|제독]]