[[TableOfContents]] = 목표 = * 김태진, 권영기, 곽병학 팀 : 동상 (본선 학교순위 10위 이내) = 진행 방식 = * 문제를 지정해서, 풀어오고, 분석. (Programming Challenges와 더블릿 홈페이지 사용) == 방학 중 == * 시간 - 매주 화, 금 오후 1시 30분. * 장소 - 6층 PC실 * 방식 - 문제를 풀어와서 토의하고, 다음 문제를 정합니다. == 학기 중 == * 시간 - 매주 토 오전 9시. * 장소 - 6층 PC실 * 방식 - 문제를 풀어와서 토의하고, 다음 문제를 정합니다. = 스터디 = == 8월 9일 == === 내용 === * 참가자 : [김태진], [정종록], [이민규], [이진규], [남성준], [권영기] * 진행 방식에 대한 회의 * 우선 [www.dovelet.com 더블릿] 사용 * 오늘 푼 문제 * 아시아 정보올림피아드/koi_aio: [http://211.228.163.31/pool/koi_aio/koi_aio.php?pname=koi_aio] (옥상 Vol1 koi_aio) * 초콜릿/coci_coko : [http://211.228.163.31/pool/coci_coko/coci_coko.php?pname=coci_coko] (옥상Vol3 coci_coko) * 숙제로 풀 문제 * 이기적인 소/usa_selfish : [http://211.228.163.31/pool/usa_selfish/usa_selfish.php?pname=usa_selfish 이기적인 소] === 풀이 === * [coci_coko/권영기] * [koi_aio/권영기] * [koi_aio/김윤환] '''//이거랑 푼거 더 올리고싶은데... 영기처럼 올리는거 어떻게 함요? ㅠㅜ 위키 사용법을 모르것소 살려줍매!''' == 8월 14일 == === 내용 === * 참가자 : [김태진], [정종록], [권영기], [곽병학] * 진행 방식에 대한 회의 * 풀어온 문제를 가지고 논해보고, 다음 문제를 정하는 방식. * Programming Challenge에서 알고리즘 당 두문제 정도 풀기. * [http://www.dovelet.com 더블릿] 옥상에서 한 문제 풀기. * Programming Challenge 문제에 더욱 높은 우선순위를 둠. - [http://uva.onlinejudge.org/] * 금요일 까지 풀어올 문제. * Doublets - [http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=31&page=show_problem&problem=1091] * Where's Waldorf - [http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=31&page=show_problem&problem=951] * koi_spra - [http://211.228.163.31/pool/koi_spra/koi_spra.php?pname=koi_spra] (dovelet) === 풀이 === * [usa_selfish/곽병학] * [usa_selfish/권영기] * [usa_selfish/김태진] === 과제 제출 === * [Where's_Waldorf/곽병학_미완..] == 8월 17일 == === 내용 === * 참가자 : [김태진], [이민규], [권영기], [곽병학], [김윤환] * 진행 방식에 대한 회의 * Dovelet의 30계단에 있는 문서를 읽고 공유해보기. * 문서를 공유한다면, 그 알고리즘을 이용한 문제를 풀어보는 것도 병행해야한다고 생각함. * 화요일 까지 풀어올 문제. * Doublets - [http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=31&page=show_problem&problem=1091] //화요일까지 풀지 못하면 소스 분석이라도 해서.. * A Multiplication Game - [http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=33&page=show_problem&problem=788] * Shoemaker's Problem - [http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=32&page=show_problem&problem=967] * koi_cha - [http://211.228.163.31/pool/koi_cha/koi_cha.php?pname=koi_cha] (dovelet) === 풀이 === * [A_Multiplication_Game/권영기] * [A_Multiplication_Game/김태진] * [A_Multiplication_Game/곽병학] * [Shoemaker's_Problem/곽병학] <- 왜 안되는지 모르겠음 스터디 할 때 찾아주길 부탁.... * [Shoemaker's_Problem/김태진] -> 마찬가지.. * [koi_cha/곽병학] <- 내 컴퓨터에선 작동이 되는데 제출하면 컴파일 에러난다; 왜이러는거지(맞았는지 틀렸는지는 모르겠음) == 8월 21일 == === 내용 === * 참가자 : [김태진], [권영기], [곽병학] * 문제 풀이, 못 푼 것 이유 분석 * koi_cha - [http://211.228.163.31/pool/koi_cha/koi_cha.php?pname=koi_cha] (dovelet) * Pairsumonious Numbers - * Bridge - === 풀이 === === 후기 === * 모든 쌍의 합 문제 풀다가 시간 다갔네-- 근데 못풀겠어 -[김태진] == 8월 24일 == === 내용 === * 참가자 : [김태진], [권영기] * Pairsumonious Numbers - * Bridge - * 문제가 어려워서 fail... 문제 풀다가 이방식도 아니고 저방식도 아니라 멘붕한 상태에서 끝났습니다. === 풀이 === * [Bridge/권영기] * [Pairsumonious_Numbers/권영기] === 후기 === == 8월 31일 == === 내용 === * 참가자 : [김태진], [곽병학], [권영기] * 학기 중 시간 * 매주 토요일 오전 9시부터 * 오늘 한 내용 * Pairsumonious Numbers * Bridge * 두 문제에 대해서 논함. 풀지 못한 사람들은 다음 시간까지 소스를 분석해서라도 해결해오기. * 다음 시간까지 해올 것. * Expressions * Bigger Square Please * koi_cha * Binary Indexed Tree === 풀이 === * [IndexedTree/권영기] === 후기 === * 공학인증을 뺄 수 있는 좋은 방법을 알았다. 태진이형은 지략가 - [권영기] * 뭔가 후기가 이상하다. -[김태진] * 아직도 저 문제들에 사경(?)을 헤매고 있습니다...== -[김태진] == 9월 8일 == === 내용 === * 참가자 : [김태진], [곽병학], [권영기] * 학기 중 시간 * 매주 토요일 오전 9시부터 * 오늘 한 내용 * Expressions - 풀이를 보고 문제를 풀어오기 * Bigger Square Please - 좀 더 생각해서 짜보기 * Binary Indexed Tree * 다음 시간까지 해올 것. * Expressions * Bigger Square Please * koi_cha * Smith Numbers === 풀이 === * [SmithNumbers/김태진] === 후기 === * 저번 주 내용과 같아보인다면 기분 탓입니다. - [권영기] * 미치겠다 진짜 ㅋ -[곽병학] * 쉽지 않군요. ㅋㅋ -[김태진] * ㅠㅠ - [권영기] == 9월 18일 == === 내용 === * 참가자 : [김태진], [곽병학], [권영기] * 9월 15일 스터디가 멘붕으로 파.개.되었으므로 18일로 미뤄짐. * 오늘 한 내용 * 인터넷 예선 대회를 앞두고 어떻게 공부를 할지. * 코드포스 http://codeforces.com/ * 자신감 문제는 왜 자신감 하락을 가져왔는지. * 다음 시간까지 해올 것. * 멘탈을 회복합시다. * 스미스 수로 자신감을 회복합시다. * 밤 안새기. === 후기 === * 아 공학인증하기 싫어 ㅠㅠ - [권영기] == 9월 22일 == === 내용 === * 참가자 : [김태진], [곽병학], [권영기] * Codeforce 3시간으로 문제 set풀기. * 2문제 풀었음. * 컴퓨터가 1대만 있을때의 문제점, testcase에 관해 생각해봄. == 10월 2일 == === 내용 === * 참가자 : [김태진], [곽병학], [권영기] * Codeforce 3시간으로 문제 set풀기. * 3문제 풀었음. == 10월 6일 == === 내용 === * 참가자 : [김태진], [곽병학], [권영기] * 오늘 한 내용 * ACM-ICPC 인터넷 예선을 치름. * 세 문제를 풀었다. * D,F,G * 문제 선택은 잘 했다. * 세 문제는 잘 풀었지만, 네 번째 문제는 당황해서 제대로 해결하지 못함. * 다음 시간까지 어떤 공부를 해야할 지 * 백트래킹 * 기하 * 김상섭 선배가 보내준 것 * 다음 시간까지 해올 것. * 인터넷 예선에서 아쉬웠던 문제를 풀어오기. * Programming Challenges에서 기하 파트 맘에 드는 문제 하나 풀어오기. === 후기 === * 4문제를 풀지 못한게 아쉽네요. 위키를 꾸준히 작성해야 되겠습니다. 밀려서 당일에 한 활동이 기억이 안나요. ㅎㅎ - [권영기] * A번을 좀 연구해봐야겠다는 생각... 역시 더 열심히 해야하는데 많이 부족하군요.(게다가 게을러-) -[김태진] == 10월 13일 == === 내용 === * 참가자 : [김태진], [곽병학], [권영기] * 오늘 한 내용 * 작년 본선문제 풀어보기 * B번과 Soju문제. Soju문제를 고민 중. === required data structure === {{{ < 그래프 & 자료구조 > 검색 (이분검색, 이진검색트리) (=> 여기서 이진검색트리의 최악의 경우 시간복잡도를 줄이기 위해서 AVL Tree가 구현되어졌는데, 레드블랙트리는 AVL의 일종입니다. 정올 할 때 꼭 배울 필요성은 없습니다..) 스택, 큐 Deque (Double Ended Queue) (알아두면 좋습니다) 링크드리스트 (Linked List) 힙 구조 - Binary Heap - Binomial Heap - Fibonacci Heap (이건 꼭 알 필요는 없습니다.) - (Binary) Indexed Tree (이건 알아둬야 합니다. 실제로 Binary Indexed Tree는 Binomial에 가깝지만..) - Interval Tree (이것 또한 Indexed Tree가 이녀석의 역할을 대신할정도로 만능이지만.) 정렬 (합병정렬, 퀵정렬, 힙정렬, 버블정렬, 선택정렬, 삽입정렬, 기수정렬) - K번째 숫자를 최악의 경우 O(n)에 찾는 문제 최소비용신장트리 - Prim - Kruskal - Matroid Theory (이것도 꼭 알 필요는 없습니다) 최단경로 - Dijkstra (다익스트라) - Floyd (플로이드) - Bellman Ford (벨만포드) 그래프 탐색 - BFS(너비우선탐색), DFS(깊이우선탐색) 위상정렬 (Topological Sort) 최대유량 알고리즘 (Maximum Flow Algorithm) - Ford-Fulkerson의 방법 - Minimum Cut (최소 절단 문제) - 푸시-재명명 방법 (이것도 꼭 알 필요는 없습니다) - 최대 이분매칭 (Bipartite Maximum Matching) - Hungarian Method (가중치가 들어간 매칭) - Gale-Shapely Matching (이건 최대유량과는 관계없이, 그리디 부분이지만, 매칭 알고리즘의 일종이므로 여기에 넣었습니다) - Hopcroft-Karp의 방법 (이건 이분매칭의 시간복잡도를 가장 줄이는 방법인데, 꼭 알 필요는 없습니다) - Mincost-Maxflow Algorithm - Stoer-Wagner Algorithm (간선연결도 문제에 쓰이는 최적 알고리즘인데, 꼭 알 필요는 없습니다) 트리 관련 - 최소 비용 채색 문제 (이건 다이나믹에 속하지만 , 트리 구조가 그래프에 속하니 여기에..) - 절점 찾기 - Bridge 찾기 (등등등등... 너무 많아서 생략) 강한 연결 성분 (Strongly Connected Components , 줄여서 SCC) - Kosaraju , Tarjan의 방법 2-CNF (2-SAT의 일종입니다) 서로소 집합 (Disjoint Set) - 순위 정하기 (휴리스틱의 일종) - 경로 압축 (휴리스틱의 일종 , Path Compression) }}} - from kin.naver.com by kanghd13 == 11월 3일 == === 내용 === * 참가자 * GoSoMi_Critical - ([김태진], [곽병학], [권영기]) * OOPARTS - ([김준석], [강성현], [장용운]) * 오늘 한 내용 * ACM-ICPC Asia-Daejeon Regional 참가. * OOPARTS - 학교 순위 15위, 전체 순위 38위 * GoSoMi_Critical - 학교 순위 15위, 전체 순위 39위 * D, E, F, I 문제를 풀었습니다. * G번 문제, H번 문제와 J번 문제는 다시 한 번 본다면 풀 수 있을지도.. * 우리나라 알고리즘 대회 1인자가 해준 짧은 해설 (의 dictation) {{{ A - accelerator 원형상의 빨강,파란점. 파란점이 더 많거나 같음 빨간점을 파란점에 연결했을때, 그 길이의 합을 최소로 한다. 각각의 빨간점을 어느 파란점에 연결해야하나,,, 빨간점을 연결할 수 있는 파란점은 제일 좋은 조건일때가 .. B 왼쪽에서 오른쪽으로 플래인 ..뭐? 다각형이 시작되는 edge를 만날때 ... indexed tree C shortest path, 같은 점을 공유하면 안됨. state로 나타낸다..? dynamic programming을 할 때 두 state로 들어오지 않도록만 하면 됨. D E F G 어떤 점에서 다른 점으로 가는데, H 가장 작은 막대기가 어딨는지 결정. (가정 ) 왼쪽에서 볼땐 오른쪽에 있으면 영향을 미치지 않음. 가장 오른쪽에 있을때 왼쪽에서 보면 보이지 않음. 어렵게 푸는 방법.. 가장 큰 폴대가 어딨는지 찾는 방법... 매우 어려움 I J 각 상태를 x길이가 얼마일때 y의 최솟값은 얼마인가 를 저장해둠. DP 가로선을 기준으로 아랫쪽 상태, 윗쪽 상태를 합쳐 가로가 n이 되나 세로가 .......ㅁㄴ이ㅏ러ㅣ아처ㅣㅇㄴ K DAG에서 minimum cover 를 구하는????? L ㅁㄴㅇㄹㅎ }}} == 11월 8일 == === 내용 === * 우리의 공부는 계속된다. * 지역본선 문제 복기. H번, G번등. * H번은 저지 시스템이 올라오면 다시 제출해볼 예정 * 계속 토요일 오전 9시 혹은 9시반에 진행하기로 함. * 다음주 토요일까지 더블릿에서 3문제 풀어오기. 각자 다른문제를 풀어와서, 설명해주기. == 11월 17일 == === 내용 === * 더블릿 문제 풀어옴 * [김태진] * DP 문제(21) - [http://211.228.163.31/30stair/seat/seat.php?pname=seat 자리배치], [http://211.228.163.31/30stair/seat/seat.php?pname=seat 긋기게임] * [곽병학] * Recursion 문제(9) - [http://211.228.163.31/30stair/omok/omok.php?pname=omok 오목], [http://211.228.163.31/30stair/necklace/necklace.php?pname=necklace 목걸이] * 퀵정렬, BinSearch(10) - [http://211.228.163.31/30stair/notes/notes.php?pname=notes music notes] * [권영기] * Stack 문제 - [http://211.228.163.31/30stair/seat/seat.php?pname=seat bad hair day], [http://211.228.163.31/30stair/seat/seat.php?pname=seat 히스토그램] === 과제 === * 히스토그램 문제 필수 * 목걸이, 뮤직노트, 오목 중 택 1 * 원하는 문제 1~2문제 === 후기 === * [김태진] - 생각보다 공부하기 좋은 방식이었습니다. (이때까지 방식 중 가장 좋았던듯.. 대회의 충격때문인가?) 앞으로 일단 이 방식으로 계속 나가면 좋을거 같네요. * [권영기] - 지난 번에 같이 풀어본 히스토그램 문제 해답이 그게 아닌가봐요 ㅠㅠ 다시 이야기 해야할 듯 합니다.(역시 채점을 해봐야되네요...) ---- [2012년활동지도], [ACM_ICPC]