Contents
- 1. 목표
- 2. 진행 방식
- 3. 스터디
- 3.1. 1월 10일
- 3.2. 1월 18일
- 3.3. 1월 24일
- 3.4. 2월 13일
- 3.5. 2월 20일
- 3.6. 2월 27일
- 3.7. 3월 6일
- 3.8. 3월 13일
- 3.9. 3월 20일
- 3.10. 3월 24일
- 3.11. 4월
- 3.12. 5월 8일
- 3.13. 5월 15일
- 3.14. 6월 27일
- 3.15. 7월 4일
- 3.16. 7월 11일
- 3.17. 7월 16일
- 3.18. 7월 25일
- 3.19. 7월 28일
- 3.20. 7월 30일,8월 6일,8월 8일
- 3.21. 8월 13일,8월 15일
- 3.22. 8월 21일,8월 28일, 8월 30일
- 3.23. 9월 28일, 10월 2일
3.1.2. 풀이 ¶
- sort/권영기
- subsequence/권영기 - 부분 구간, 건조, 공격적인 소 문제 코드 모두 있어여. 근데 소스 공개하기 부끄럽네..
3.4.1. 내용 ¶
* 참가자 :
- 오늘 푼 문제
- 곽병학
- 김태진
- 계단오르기
- BackTracking문제 1문제
- 계단오르기
- 권영기
- 곽병학
- 풀어보기 : land
3.5.1. 내용 ¶
* 참가자 :
- 오늘 푼 문제
- 곽병학
- 김태진
- 헛간(저번주 문제)
- n 마리의 쥐가 크기가 같은 n 개의 버터를 먹는데 n 시간이 걸린다고 할 때 , m 마리의 쥐가 m 개의 버터를 먹는데 걸리는 시간을 구하는것이 문제이다. 각각의 쥐가 치즈를 먹는 속도는 모두 동일하다고 한다.
- 헛간(저번주 문제)
- 권영기
- 곽병학
- 풀어보기 : land
3.13.1. 내용 ¶
- 김태진
- 코드잼_1C라운드: 857등
- Consonants, Pogo, The Great Wall
- Consonants, Pogo, The Great Wall
- 코드잼_1C라운드: 857등
def Solve(x, y): N = 0 sum = 0 while sum < abs(x) + abs(y) or (sum + x + y) % 2 == 1: N += 1 sum += N result = "" while N > 0: if abs(x) > abs(y): if x > 0: result += 'E' x -= N else: result += 'W' x += N else: if y > 0: result += 'N' y -= N else: result += 'S' y += N N -= 1 return result.reversed()
- 권영기
- 곽병학
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
- proof - http://prezi.com/fsaynn-iexse/kadanes-algorithm/
- Array에서 특정 subset의 합이 가장 크도록 하는 부분찾기.
- proof - http://prezi.com/fsaynn-iexse/kadanes-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냅색 문제 이제 좀 이해했음다..
- 곽병학 : 한붓그리기?
- 권영기 : ?
3.17.2. 내용 ¶
- 참고문제 prime_path http://211.229.66.5/30stair/prime_path/prime_path.php?pname=prime_path
- 곽병학: 전체 맵에서 각각 독립적인 그래프들 찾기 - 문제점은 알았고 풀어오겠음, 그래프 문제 안풀어오면 저녁
- 김태진: gusul/김태진
3.18. 7월 25일 ¶
- 완전(교란)순열 - http://ko.wikipedia.org/wiki/완전순열
- !n = (n - 1) * (!(n - 2) + !(n - 1))
- 증명 - http://blog.naver.com/PostView.nhn?blogId=kcg2271&logNo=90064644595
- !n = (n - 1) * (!(n - 2) + !(n - 1))
- DP 문제 worm/김태진 - 점화식 세울 때 k=0와 k=1, k=2일때를 특히 조심하자. - 걍 여긴 수작업하는게 속편함.
- Bar_code 문제 - http://211.229.66.5/30stair/bar_code/bar_code.php?pname=bar_code
- 풀이 - 삼차원 테이블을 사용한 DP문제, d(bar,unit,width)는 bar번째의 bar를 사용하면서, unit의 위치에 그 bar의 폭이 width일 때의 경우이다. 따라서 가능한 모든 바코드의 수를 구하는 것은 d(bar,unit,0 ~ width)를 전부 더해주면 된다.
- 점화식 : d(bar, unit, width) += d(bar - 1,unit - width,l);
- 점화식을 구하는 것은 금방 구했으나, index를 얻어내는 것이 힘들었음.
- 설명하면 1110110 이라는 것이 있을 때, 1110110이 오기 전에는 110으로 시작하는 모든 바코드가 있을 것이고, 그 이전에는 10으로 시작하는 모든 바코드가 있을 것이다. 그리고 1110110이라는 바코드가 오기 전에는 111000으로 시작하는 모든 바코드가 있을 것이고, 그 이전에는 11100으로 시작하는 모든 바코드가 있을 것이다. dp테이블에 해당 경우에 대한 경우의 수를 모두 저장해놨기 때문에, 앞에서 부터 차례대로 이전에 올 바코드의 수를 더해나가면 index를 구할 수 있다.
- 풀면서 주의할 점 : dp테이블의 범위에 벗어나는 경우(예를 들어서 음수 번지)가 나올 수 있으므로 이에 대한 처리를 해줘야 한다. 비쥬얼 스튜디오에서 코드를 작성할 때, 테이블 범위에 벗어나도 정답이 나오는 경우가 생겨서 이런 예외를 발견하기 힘들었음..
- 풀이 - 삼차원 테이블을 사용한 DP문제, d(bar,unit,width)는 bar번째의 bar를 사용하면서, unit의 위치에 그 bar의 폭이 width일 때의 경우이다. 따라서 가능한 모든 바코드의 수를 구하는 것은 d(bar,unit,0 ~ width)를 전부 더해주면 된다.
3.20. 7월 30일,8월 6일,8월 8일 ¶
- Coder's High 2013 (Algospot 알고리즘대회) 풀기
- 링크
- 푼 문제
- 사신도
- 태진 풀이 FOURGODS/김태진
- 태진 풀이 FOURGODS/김태진
- Jump
- 태진 풀이 JumpJump/김태진
- 태진 풀이 JumpJump/김태진
- 째능교육
- Weekly Calendar
- 우주개발의 길은 멀고도 험하다
- 권영기 품
- 권영기 품
- 사신도
- 링크
3.21. 8월 13일,8월 15일 ¶
- 2012 ICPC대전 문제 풀기 : 링크
- C - Critical 3-path
- 위상정렬, critical path에 대해 공부 및 코딩 - 코드 및 해설은 Fundamental of DataStructure를 참고하자.
- 위상정렬, critical path에 대해 공부 및 코딩 - 코드 및 해설은 Fundamental of DataStructure를 참고하자.
- C - Critical 3-path
- 폴리오미노
- DP문제. 태진 풀이 POLY/김태진
- DP문제. 태진 풀이 POLY/김태진
3.22. 8월 21일,8월 28일, 8월 30일 ¶
- 제2회 대학생프로그래밍 대회 동아리 연합 링크
- 사각형 2개가 겹치는 지 아닌지 판별하는 방법
Ax1은 A사각형의 왼쪽위 x좌표. By2는 B사각형의 오른쪽아래 y좌표 if Ax1 < Bx1 if Bx1 > Ax2 && By1 > Ay2 if By2 > Ay1 then 겹침 else 안겹침 else 안겹침 else A와 B를 바꿔서 재시도
- Sliding Window Minimum Algorithm - http://people.cs.uct.ac.za/~ksmith/articles/sliding_window_minimum.html