U E D R , A S I H C RSS

ACM_ICPC/2012년스터디

1. 목표

  • 김태진, 권영기, 곽병학 팀 : 동상 (본선 학교순위 10위 이내)

2. 진행 방식

  • 문제를 지정해서, 풀어오고, 분석. (Programming Challenges와 더블릿 홈페이지 사용)

2.1. 방학 중

  • 시간 - 매주 화, 금 오후 1시 30분.
  • 장소 - 6층 PC실
  • 방식 - 문제를 풀어와서 토의하고, 다음 문제를 정합니다.

2.2. 학기 중

  • 시간 - 매주 토 오전 9시.
  • 장소 - 6층 PC실
  • 방식 - 문제를 풀어와서 토의하고, 다음 문제를 정합니다.

3. 스터디

3.1. 8월 9일

3.1.1. 내용

3.1.2. 풀이

  • coci_coko/권영기
  • koi_aio/권영기

  • koi_aio/김윤환 //이거랑 푼거 더 올리고싶은데... 영기처럼 올리는거 어떻게 함요? ㅠㅜ 위키 사용법을 모르것소 살려줍매!

3.2. 8월 14일

3.2.1. 내용

3.3. 8월 17일


3.3.1. 내용

3.3.2. 풀이

3.4. 8월 21일


3.4.1. 내용

3.4.2. 풀이

3.4.3. 후기

  • 모든 쌍의 합 문제 풀다가 시간 다갔네-- 근데 못풀겠어 -김태진

3.5. 8월 24일


3.5.1. 내용

  • 참가자 : 김태진, 권영기
    • Pairsumonious Numbers -
    • Bridge -
  • 문제가 어려워서 fail... 문제 풀다가 이방식도 아니고 저방식도 아니라 멘붕한 상태에서 끝났습니다.

3.5.3. 후기


3.6. 8월 31일


3.6.1. 내용

  • 참가자 : 김태진, 곽병학, 권영기
  • 학기 중 시간
    • 매주 토요일 오전 9시부터
  • 오늘 한 내용
    • Pairsumonious Numbers
    • Bridge
    • 두 문제에 대해서 논함. 풀지 못한 사람들은 다음 시간까지 소스를 분석해서라도 해결해오기.
  • 다음 시간까지 해올 것.
    • Expressions
    • Bigger Square Please
    • koi_cha
    • Binary Indexed Tree

3.6.3. 후기

  • 공학인증을 뺄 수 있는 좋은 방법을 알았다. 태진이형은 지략가 - 권영기
  • 아직도 저 문제들에 사경(?)을 헤매고 있습니다...== -김태진

3.7. 9월 8일


3.7.1. 내용

  • 참가자 : 김태진, 곽병학, 권영기
  • 학기 중 시간
    • 매주 토요일 오전 9시부터
  • 오늘 한 내용
    • Expressions - 풀이를 보고 문제를 풀어오기
    • Bigger Square Please - 좀 더 생각해서 짜보기
    • Binary Indexed Tree
  • 다음 시간까지 해올 것.
    • Expressions
    • Bigger Square Please
    • koi_cha
    • Smith Numbers

3.7.3. 후기


3.8. 9월 18일


3.8.1. 내용

  • 참가자 : 김태진, 곽병학, 권영기
  • 9월 15일 스터디가 멘붕으로 파.개.되었으므로 18일로 미뤄짐.
  • 오늘 한 내용
    • 인터넷 예선 대회를 앞두고 어떻게 공부를 할지.
    • 자신감 문제는 왜 자신감 하락을 가져왔는지.
  • 다음 시간까지 해올 것.
    • 멘탈을 회복합시다.
    • 스미스 수로 자신감을 회복합시다.
    • 밤 안새기.

3.8.2. 후기

  • 아 공학인증하기 싫어 ㅠㅠ - 권영기

3.9. 9월 22일

3.9.1. 내용

  • 참가자 : 김태진, 곽병학, 권영기
  • Codeforce 3시간으로 문제 set풀기.
    • 2문제 풀었음.
    • 컴퓨터가 1대만 있을때의 문제점, testcase에 관해 생각해봄.

3.10. 10월 2일

3.10.1. 내용

3.11. 10월 6일

3.11.1. 내용

  • 참가자 : 김태진, 곽병학, 권영기
  • 오늘 한 내용
    • ACM-ICPC 인터넷 예선을 치름.
      • 세 문제를 풀었다.
        • D,F,G
      • 문제 선택은 잘 했다.
      • 세 문제는 잘 풀었지만, 네 번째 문제는 당황해서 제대로 해결하지 못함.
  • 다음 시간까지 어떤 공부를 해야할 지
    • 백트래킹
    • 기하
    • 김상섭 선배가 보내준 것
  • 다음 시간까지 해올 것.
    • 인터넷 예선에서 아쉬웠던 문제를 풀어오기.
    • Programming Challenges에서 기하 파트 맘에 드는 문제 하나 풀어오기.

3.11.2. 후기

  • 4문제를 풀지 못한게 아쉽네요.
    위키를 꾸준히 작성해야 되겠습니다. 밀려서 당일에 한 활동이 기억이 안나요. ㅎㅎ - 권영기
  • A번을 좀 연구해봐야겠다는 생각... 역시 더 열심히 해야하는데 많이 부족하군요.(게다가 게을러-) -김태진

3.12. 10월 13일

3.12.1. 내용

  • 참가자 : 김태진, 곽병학, 권영기
  • 오늘 한 내용
    • 작년 본선문제 풀어보기
      • B번과 Soju문제. Soju문제를 고민 중.

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. 11월 3일

3.13.1. 내용

  • 참가자
  • 오늘 한 내용
    • 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 ㅁㄴㅇㄹㅎ

3.14. 11월 8일

3.14.1. 내용

  • 우리의 공부는 계속된다.
  • 지역본선 문제 복기. H번, G번등.
    • H번은 저지 시스템이 올라오면 다시 제출해볼 예정
  • 계속 토요일 오전 9시 혹은 9시반에 진행하기로 함.
  • 다음주 토요일까지 더블릿에서 3문제 풀어오기. 각자 다른문제를 풀어와서, 설명해주기.

3.15. 11월 17일

3.15.1. 내용

3.15.2. 과제

  • 히스토그램 문제 필수
  • 목걸이, 뮤직노트, 오목 중 택 1
  • 원하는 문제 1~2문제

3.15.3. 후기

  • 김태진 - 생각보다 공부하기 좋은 방식이었습니다. (이때까지 방식 중 가장 좋았던듯.. 대회의 충격때문인가?) 앞으로 일단 이 방식으로 계속 나가면 좋을거 같네요.
  • 권영기 - 지난 번에 같이 풀어본 히스토그램 문제 해답이 그게 아닌가봐요 ㅠㅠ 다시 이야기 해야할 듯 합니다.(역시 채점을 해봐야되네요...)

3.16. 11월 24일

3.16.1. 내용

3.16.2. 과제

  • 히스토그램 문제 재도전
  • 김태진,곽병학 - pattern matching
  • 원하는 문제 1~2문제

3.16.3. 후기


3.17. 12월 1일

3.17.1. 내용

3.17.2. 과제

  • Inflate 푸세여

3.17.3. 후기

  • 권영기 - 드디어 Histogram을 풀었습니다. 기분이 너무너무 좋네여 ㅎㅎ

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2012-12-01 02:57:43
Processing time 0.3747 sec