U E D R , A S I H C RSS
ZeroWiki

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.2.2. 풀이

3.2.3. 과제 제출

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.2. 풀이

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.2. 풀이

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.2. 풀이

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 2021-02-07 05:22:20
Processing time 0.0496 sec