Difference between r1.42 and the current
@@ -335,6 +335,6 @@
=== 과제 ===
* Inflate 푸세여
=== 후기 ===
[2012년활동지도], [ACM_ICPC]
* Inflate 푸세여
=== 후기 ===
*
* [권영기] - 드디어 Histogram을 풀었습니다. 기분이 너무너무 좋네여 ㅎㅎ
----[2012년활동지도], [ACM_ICPC]
Contents
3.1.1. 내용 ¶
- 참가자 : 김태진, 정종록, 이민규, 이진규, 남성준, 권영기
- 진행 방식에 대한 회의
- 우선 www.dovelet.com 더블릿 사용
- 우선 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)
- 아시아 정보올림피아드/koi_aio: http://211.228.163.31/pool/koi_aio/koi_aio.php?pname=koi_aio (옥상 Vol1 koi_aio)
- 숙제로 풀 문제
- 이기적인 소/usa_selfish : 이기적인 소
- 이기적인 소/usa_selfish : 이기적인 소
3.1.2. 풀이 ¶
- coci_coko/권영기
- koi_aio/권영기
- koi_aio/김윤환 //이거랑 푼거 더 올리고싶은데... 영기처럼 올리는거 어떻게 함요? ㅠㅜ 위키 사용법을 모르것소 살려줍매!
3.2.1. 내용 ¶
- 참가자 : 김태진, 정종록, 권영기, 곽병학
- 진행 방식에 대한 회의
- 풀어온 문제를 가지고 논해보고, 다음 문제를 정하는 방식.
- Programming Challenge에서 알고리즘 당 두문제 정도 풀기.
- 더블릿 옥상에서 한 문제 풀기.
- 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)
- Doublets - http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=31&page=show_problem&problem=1091
3.3.1. 내용 ¶
- 참가자 : 김태진, 이민규, 권영기, 곽병학, 김윤환
- 진행 방식에 대한 회의
- Dovelet의 30계단에 있는 문서를 읽고 공유해보기.
- 문서를 공유한다면, 그 알고리즘을 이용한 문제를 풀어보는 것도 병행해야한다고 생각함.
- 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)
- Doublets - http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=31&page=show_problem&problem=1091 //화요일까지 풀지 못하면 소스 분석이라도 해서..
3.3.2. 풀이 ¶
- A_Multiplication_Game/권영기
- A_Multiplication_Game/김태진
- A_Multiplication_Game/곽병학
- Shoemaker's_Problem/곽병학 <- 왜 안되는지 모르겠음 스터디 할 때 찾아주길 부탁....
- Shoemaker's_Problem/김태진 -> 마찬가지..
- koi_cha/곽병학 <- 내 컴퓨터에선 작동이 되는데 제출하면 컴파일 에러난다; 왜이러는거지(맞았는지 틀렸는지는 모르겠음)
3.4.1. 내용 ¶
- 참가자 : 김태진, 권영기, 곽병학
- 문제 풀이, 못 푼 것 이유 분석
- koi_cha - http://211.228.163.31/pool/koi_cha/koi_cha.php?pname=koi_cha (dovelet)
- Pairsumonious Numbers -
- Bridge -
- koi_cha - http://211.228.163.31/pool/koi_cha/koi_cha.php?pname=koi_cha (dovelet)
3.8.1. 내용 ¶
3.12.2. 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
3.13.1. 내용 ¶
- 참가자
- 오늘 한 내용
- ACM-ICPC Asia-Daejeon Regional 참가.
- OOPARTS - 학교 순위 15위, 전체 순위 38위
- GoSoMi_Critical - 학교 순위 15위, 전체 순위 39위
- D, E, F, I 문제를 풀었습니다.
- G번 문제, H번 문제와 J번 문제는 다시 한 번 본다면 풀 수 있을지도..
- G번 문제, H번 문제와 J번 문제는 다시 한 번 본다면 풀 수 있을지도..
- ACM-ICPC Asia-Daejeon Regional 참가.
- 우리나라 알고리즘 대회 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 ㅁㄴㅇㄹㅎ
3.14.1. 내용 ¶
- 우리의 공부는 계속된다.
- 지역본선 문제 복기. H번, G번등.
- H번은 저지 시스템이 올라오면 다시 제출해볼 예정
- H번은 저지 시스템이 올라오면 다시 제출해볼 예정
- 계속 토요일 오전 9시 혹은 9시반에 진행하기로 함.
- 다음주 토요일까지 더블릿에서 3문제 풀어오기. 각자 다른문제를 풀어와서, 설명해주기.
3.16.1. 내용 ¶
- 더블릿 문제 풀어옴
- 김태진
- BackTracking 문제(25) - eating_puzzle, scales
- BackTracking 문제(25) - eating_puzzle, scales
- 곽병학
- tree 문제(15) - treeornot
- tree 문제(15) - treeornot
- 권영기
- 김태진
