[[TableOfContents]] = 목표 = * 김태진, 권영기, 곽병학 팀 : 동상 (본선 학교순위 10위 이내) * 참여를 원하는 분을 위한 문은 언제나 열려있습니다. = 진행 방식 = * 각자 문제를 풀어오고 설명, 설명들은 문제는 다음 시간까지 개인적으로 풀어올 것.(Dovelet 사용) == 방학 중 == * 시간 - 매주 목 오후 5시. * 장소 - 6층 PC실 * 방식 - 각자 문제를 풀어와서 토의하고, 다음 문제를 정합니다. = 스터디 = == 1월 10일 == === 내용 === * 참가자 : [김태진], [권영기], [곽병학] * 2013년 스터디 시작! * 작년 방식하고 똑같습니다. * 오늘 푼 문제 * 김태진 * queue - [http://211.228.163.31/30stair/prime_path/prime_path.php?pname=prime_path 소수 길] * 곽병학 * dynamic programming - [http://211.228.163.31/30stair/eating_together/eating_together.php?pname=eating_together 끼리끼리] * 권영기 * linked list - [http://211.228.163.31/30stair/josephus/josephus.php?pname=josephus&stair=11 josephus] * 퀵 정렬,이진검색,parametric search - [http://211.228.163.31/30stair/guessing_game/guessing_game.php?pname=guessing_game&stair=10 숫자 추측하기], [http://211.228.163.31/30stair/sort/sort.php?pname=sort&stair=10 세 값의 정렬], [http://211.228.163.31/30stair/subsequence/subsequence.php?pname=subsequence&stair=10 부분 구간], [http://211.228.163.31/30stair/drying/drying.php?pname=drying&stair=10 건조], [http://211.228.163.31/30stair/aggressive/aggressive.php?pname=aggressive&stair=10 공격적인 소] === 풀이 === * [sort/권영기] * [subsequence/권영기] - 부분 구간, 건조, 공격적인 소 문제 코드 모두 있어여. 근데 소스 공개하기 부끄럽네.. == 1월 18일 == === 내용 === * 참가자 : [김태진], [권영기], [곽병학] * 오늘 푼 문제 * 김태진 * dynamic programming - [http://211.228.163.31/30stair/subset/subset.php?pname=subset 부분 합] * greedy method - [http://211.228.163.31/30stair/quick_change/quick_change.php?pname=quick_change 거스름돈], [http://211.228.163.31/30stair/germination/germination.php?pname=germination 발아] * 곽병학 * bisection - [http://211.228.163.31/30stair/crossed_ladder/crossed_ladder.php?pname=crossed_ladder crossed ladder] * queue - [http://211.228.163.31/30stair/catch_cow/catch_cow.php?pname=catch_cow 도망 간 소를 잡아라] * 권영기 * graph, dfs - [http://211.228.163.31/30stair/danji/danji.php?pname=danji 단지 번호 붙이기], [http://211.228.163.31/30stair/orders/orders.php?pname=orders orders], [http://211.228.163.31/30stair/bugslife/bugslife.php?pname=bugslife 짝 짓기], [http://211.228.163.31/30stair/sprime/sprime.php?pname=sprime 슈퍼 소수], [http://211.228.163.31/30stair/snail_trails/snail_trails.php?pname=snail_trails 달팽이] === 풀이 === == 1월 24일 == === 내용 === * 참가자 : [김태진], [권영기], [곽병학] * 오늘 푼 문제 * 곽병학 * 이분법 - [http://211.228.163.31/30stair/crossed_ladder/crossed_ladder.php?pname=crossed_ladder crossed ladder] * 스택 - [http://211.228.163.31/30stair/tw/tw.php?pname=tw 송신탑] * 김태진 * dp - [http://211.228.163.31/30stair/tickets/tickets.php?pname=tickets 티켓] * dp - [http://211.228.163.31/30stair/tickets/tickets.php?pname=tickets 레인지] *권영기 * 17 위상정렬 - [http://211.228.163.31/30stair/topo_sort/topo_sort.php?pname=topo_sort topo_sort] * 17 위상정렬 - 다 === 풀이 === * [crossedladder/곽병학] == 2월 13일 == === 내용 === * 참가자 : * 오늘 푼 문제 * 곽병학 * * 김태진 * [http://211.228.163.31/30stair/ustair/ustair.php?pname=ustair 계단오르기] * BackTracking문제 1문제 *권영기 * [http://211.228.163.31/30stair/barn/barn.php?pname=barn 헛간] * * 풀어보기 : land === 풀이 === * == 2월 20일 == === 내용 === * 참가자 : * 오늘 푼 문제 * 곽병학 * * 김태진 * [http://211.228.163.31/30stair/barn/barn.php?pname=barn 헛간](저번주 문제) * n 마리의 쥐가 크기가 같은 n 개의 버터를 먹는데 n 시간이 걸린다고 할 때 , m 마리의 쥐가 m 개의 버터를 먹는데 걸리는 시간을 구하는것이 문제이다. 각각의 쥐가 치즈를 먹는 속도는 모두 동일하다고 한다. *권영기 * * 풀어보기 : land === 풀이 === * == 2월 27일 == === 내용 === * 참가자 : * 오늘 푼 문제 * 곽병학 * [http://211.228.163.31/30stair/inflate/inflate.php?pname=inflate inflate] * 김태진 * 권영기 * Binary Indexed Tree * Up Sequence * [http://211.228.163.31/30stair/mobile/mobile.php?pname=mobile moblie] * 개강 이후에는 매주 수요일 6시에 스터디 시작하기로 결정, 격주로 토요일에도 만나기로 함. * inflate 모르겠다 알려줘 === 풀이 === * == 3월 6일 == === 내용 === * 참가자 : * 오늘 푼 문제 * 곽병학 * pongdang, align, us * 김태진 * jumping_cow * 권영기 * Up Sequence * [http://stackoverflow.com/questions/2631726/how-to-determine-the-longest-increasing-subsequence-using-dynamic-programming Time Complexity O(n log n) 의 Up Sequence] * [http://211.228.163.31/30stair/bridging/bridging.php?pname=bridging&stair=15 bridging - binary indexed tree를 이용한 Up Sequence 문제] * [http://211.228.163.31/30stair/tower/tower.php?pname=tower&stair=21 tower], [http://211.228.163.31/30stair/align/align.php?pname=align&stair=21 align], [http://211.228.163.31/30stair/tile_up_block/tile_up_block.php?pname=tile_up_block&stair=21 tile_up_block], [http://211.228.163.31/30stair/koi_cpaper/koi_cpaper.php?pname=koi_cpaper&stair=21 koi_cpaper], [http://211.228.163.31/30stair/buy_lower/buy_lower.php?pname=buy_lower&stair=21 buy_lower] === 풀이 === * == 3월 13일 == === 내용 === * 곽병학 * catch_cow * 김태진 * [http://211.228.163.31/30stair/ally/ally.php?pname=ally 아군살리기] * 권영기 == 3월 20일 == === 내용 === * 코드포스 문제풀기 * [http://codeforces.com/contest/284/problem 284회vol2.] * A,B번 풀었음 == 3월 24일 == === 내용 === * 코드포스 복기 * C번은 예상대로 쉽게 푸는 방법이 있었음 * D번은 풀이법에 대한 실마리가 제시되어 각자 코딩할 계획 == 4월 == * 시험기간에 의한 휴식기 == 5월 8일 == * 문제 풀어오지 못함.. == 5월 15일 == === 내용 === * 김태진 * [http://code.google.com/codejam/contest/2437488/dashboard 코드잼_1C라운드]: 857등 * Consonants, Pogo, The Great Wall {{{ 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() }}} * 권영기 * 곽병학 == 6월 27일 == * 김태진 : Dynamic Programming 6.1~6.3 * Shortest Path : DAG(directed acyclic graphs)로 바꾼 후 Source에서부터 dist(v) = min{dist(v) + l(u,v)}사용 * 170p * Longest increasing subsequence : DAG로 바꾼다.(increasing하는 곳에만 edge생성됨) 이후 가장 많이 방문하도록 L(j) = 1+ max{L(i) : (i,j)}수행 * 최대 path의 길이를 구한 후에 뒤로 돌아가면서 숫자가 줄어드는 녀석들을 스택에 담으면 path도 구할 수 있다. * Edit distance : 글자 최소 오류개수 구하기 (exponential과 polynomial의 최소 오류는 6개.) * Similar to DTW * 권영기 : 3장 그래프 * 곽병학 : Hoffman code - 쓸데없을거 같음.. == 7월 4일 == === Need to Discuss === * Stack부분에서 Histogram 문제 * BFS 효율적 구현 === 내용 === * 김태진 : DP * * Maximum Sum - kadane's algorithm * proof - [http://prezi.com/fsaynn-iexse/kadanes-algorithm/] * Array에서 특정 subset의 합이 가장 크도록 하는 부분찾기. * 권영기 : * Topological sort - * [http://homepages.ius.edu/rwisman/C455/html/notes/Chapter22/TopSort.htm] * [http://en.wikipedia.org/wiki/Topological_sorting] * Strongly Connected Component(SCC) * Tarjan's strongly connected components algorithm - [http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm 링크] * URL에 '가 들어가면 개고생. * 곽병학 : == 7월 11일 == === Need to Discuss === * === 내용 === * 김태진 : Dynamic Programming * [KnapsackProblem/김태진] : 0/1냅색 문제 이제 좀 이해했음다.. * 곽병학 : 한붓그리기? * 권영기 : ? == 7월 16일 == === Need to Discuss === * === 내용 === * 참고문제 prime_path [http://211.229.66.5/30stair/prime_path/prime_path.php?pname=prime_path] * 곽병학: 전체 맵에서 각각 독립적인 그래프들 찾기 - 문제점은 알았고 풀어오겠음, 그래프 문제 안풀어오면 저녁 * 김태진: [gusul/김태진] == 7월 25일 == * 완전(교란)순열 - http://ko.wikipedia.org/wiki/%EC%99%84%EC%A0%84%EC%88%9C%EC%97%B4 * !n = (n - 1) * (!(n - 2) + !(n - 1)) * 증명 - http://blog.naver.com/PostView.nhn?blogId=kcg2271&logNo=90064644595 * 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테이블의 범위에 벗어나는 경우(예를 들어서 음수 번지)가 나올 수 있으므로 이에 대한 처리를 해줘야 한다. 비쥬얼 스튜디오에서 코드를 작성할 때, 테이블 범위에 벗어나도 정답이 나오는 경우가 생겨서 이런 예외를 발견하기 힘들었음.. == 7월 28일 == * Algospot배 알고리즘대회 * 멘탈파괴당함 == 7월 30일,8월 6일,8월 8일 == * Coder's High 2013 (Algospot 알고리즘대회) 풀기 * [http://www.algospot.com/judge/problem/list/?tag=&source=Coder%27s+high+2013&author= 링크] * 푼 문제 * [http://www.algospot.com/judge/problem/read/FOURGODS 사신도] * 태진 풀이 [FOURGODS/김태진] * [http://www.algospot.com/judge/problem/read/JUMP Jump] * 태진 풀이 [JumpJump/김태진] * [http://www.algospot.com/judge/problem/read/XHAENEUNG 째능교육] * [http://www.algospot.com/judge/problem/read/WEEKLYCALENDAR Weekly Calendar] * [http://www.algospot.com/judge/problem/read/SPACE 우주개발의 길은 멀고도 험하다] * 권영기 품 == 8월 13일,8월 15일 == * 2012 ICPC대전 문제 풀기 : [https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=554 링크] * C - Critical 3-path * 위상정렬, critical path에 대해 공부 및 코딩 - 코드 및 해설은 Fundamental of DataStructure를 참고하자. * [http://www.algospot.com/judge/problem/read/POLY 폴리오미노] * DP문제. 태진 풀이 [POLY/김태진] == 8월 21일,8월 28일, 8월 30일 == * 제2회 대학생프로그래밍 대회 동아리 연합 [http://algospot.com/judge/problem/list/?source=제%202회%20전국%20대학생%20프로그래밍%20대회%20동아리%20연합%20대회 링크] * 사각형 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 == 9월 28일, 10월 2일 == * 우리의 1년간의 여정은 갑작스럽게 끝이 찾아왔습니다. ---- [2013년활동지도]