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.1. 8 9

3.1.1.

3.1.2.

3.2. 8 14

3.3. 8 17


3.3.2.

3.4. 8 21


3.4.1.

3.4.3.

3.5. 8 24


3.5.1.

  • : ,
    • Pairsumonious Numbers -
    • Bridge -
  • fail... .

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.

3.8.2.

  • ㅠㅠ -

3.9. 9 22

3.9.1.

  • : , ,
  • Codeforce 3 set.
    • 2 .
    • 1 , testcase .

3.10. 10 2

3.10.1.

  • : , ,
  • Codeforce 3 set.
    • 3 .

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.


    • 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 ㅁ

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.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.0981 sec