algorithm Study/2014

• in_out
  
• ubiquitous
  

• matrixprod
  
• poop
  

• /shredding
  

• /pigs
  

• /virtual을 풀었으면 /pigs도 다시 풀어 오는 것으로.
  

• /koi_virus
  

• /ioi_raisins
  
• 너무 어려워서 다같이 GG.
  

• 조영준, 권영기, 서지혜, 강성현, 이진규, 서민관
  

• 개강 후 첫 진행. 모두들 안녕하세요!
  
• 스터디 방식을 모여서 페어코딩 하는 식으로 변경.
  
  • 페어/싱글로 해도 되며, 각각 풀고 싶은 문제를 풀고 끝나기 전에 직접/위키로 공유
    
• 다른 사이트를 사용하자는 의견이 있었음. 다음 스터디 하기 전까지 Slack에서 결정하기로.
  
  • http://www.acmicpc.net/
    
  • http://www.topcoder.com/
    
  • 등...
    

• http://183.106.113.109/30stair/tight/tight.php?pname=tight&stair=21
  
• http://183.106.113.109/30stair/assignment/assignment.php?pname=assignment
  

• 조영준, 이진규
  

• http://183.106.113.109/30stair/queen/queen.php
  
• http://183.106.113.109/30stair/nqueen/nqueen.php
  
• http://183.106.113.109/30stair/bus/bus.php
  

• 서민관, 이원준, 권영기, 조영준, 이진규 (온라인 참가)
  

• codejam 2012 practice : https://code.google.com/codejam/contest/1460488/dashboard
  
  

• 권영기, 서민관, 이원준, 이진규, 조영준
  

• 지금까지 진행해 본 결과 조금 더 뚜렷한 목표가 필요하는 의견이 나옴.
  
• 알고리즘 관련 문제 서적을 보거나 현재 진행하던 대로 유지하자는 등의 의견이 나옴.
  
• 의논을 해 본 결과 매 주 하나의 주제를 잡아서 스터디를 진행하자는 방향으로 의견이 수렴됨.
  
  • 스터디 전에 하나의 주제를 정하고 스터디 때에는 해당 주제에 대해서 각자 하고 싶은 것들을 함.
    
  • 주제에 대해 문제를 풀거나 해당 주제를 다룬 책을 읽거나 등 다양한 활동 가능.
    
  • 스터디를 끝내기 30분 전에 각자 한 내용을 공유.
    
    

• Greedy Algorithm
  
  

• Greedy Algorithm
  
• Dynamic Programming
  
• Tree
  
• Graph
  
  

• 참가자: 이원준, 조영준
  
• 내용: http://183.106.113.109/30stair/tram/tram.php?pname=tram + union find
  
  

• 참가자: 서지혜, 강성현, 조영준
  
• Hungarian Method
  
  

• 참가자: 이원준, 조영준
  
• Hungarian Merthod cont.
  

• http://en.wikipedia.org/wiki/Hungarian_algorithm: 다른 곳에는 나와있지 않은 '최소한의 라인으로 모든 0을 덮는 법'이 나와있음
  
• http://www.math.harvard.edu/archive/20_spring_05/handouts/assignment_overheads.pdf: 어느 때 사용이 되는지부터 Big-O 분석, 구현 방법 등이 정리되어있음
  
• http://www.wikihow.com/Use-the-Hungarian-Algorithm: 방법 설명이 가장 단순하고 심플.
  
• http://www.ee.oulu.fi/~mpa/matreng/eem1_2-1.htm
  
  

• 0들을 어떻게 최소한 라인으로 덮는가?
  
• 위키피디아 해답 step 3 부분
  
  1. 처음에 가장 많은 일들을 할당한다.
     
  2. 할당되지 않은 row를
     
• 처음에 가장 많은 일들을 할당한다?
  
  • 할 수 있는 일이 하나인 애들 부터 할당
    
  • 그 다음으로 여러 개 할 수 있는 애들을 할당한다
    
• 조금 더 구체적으로 하자면...
  
  

n = 1

n이 배열의 크기보다 작을 경우 아래를 계속 반복한다.
모든 라인에 대해서 0이 n개가 있는 라인이 있는가?
  있으면, 해당되는 라인들 중 하나의 라인에서 임의의 0을 할당시켜주고, 그 0의 가로/세로에 있는 다른 0들을 다른 값으로 바꿈. 그리고 n을 1로 세팅.
  없으면, n을 1 증가.

1. 입력
   
2. n*n 행렬 만들기
   
   1. n*n 행렬이 아닐 경우에 행렬의 최대값으로 행 또는 열을 추가해서 n*n행렬을 만들어버림
      
3. 행에 대해서 그 행의 최소값으로 전부 뺌
   
4. 0이 없는 열이 있을 경우 열에 대해서 연산한다. 그 열의 최소값으로 전부 빼기
   
5. 최소한의 선으로 0들을 모두 포함하는 선들을 그린다 (알고리즘 문제 2..)(위키피디아 Matrix 계산 step 3 부분)
   
   1. 열과 행이 겹치지 않게 최대한 많은 0들을 고른다. (이것도 알고리즘 문제...)
      
   2. 선택되지 않은 모든 행들을 마크한다
      
   3. 바로 위의 행에서 0으로 기록된 열들을 모두 마크한다
      
   4. 바로 위의 열에서 일을 할당 받은 모든 행을 마크한다
      
   5. 일정한 패턴이 나올때 까지 계속 반복한다.
      
6. 선들이 그려지지 않은 부분에서 최소값을 찾아서 선들이 그려진 부분에 더한다. 두번 겹친 부분은 두번 더함
   
7. 전체 배열에서 최소값을 찾아 전부 뺀다
   
8. 0 덮기. 최소한의 선이 행의 갯수와 같지 않으면 다시 위에 연산, 같으면 탈출
   
9. 이제 행과 열을 겹치지 않게 0 선택하기.
   
10. 최초의 배열에 적용하면 최소값 고르기 완성.
    

• 초기에 입력받는 값들이 음수여도 괜찮.
  
  • 첫번째 스텝에서 '최솟값'을 빼기 때문에, 결국 모두 양수가 됨.
    
• 입력받은 배열이 n*n이 아닐 경우 빈 곳에 최댓값을 넣어서 n*n으로 만들어야 함
  
• 입력받은 배열에 전부 -1을 곱할 경우 '최소 비용' 이 아닌 '최대 비용'을 구할 수 있음.
  
  

• 안내 페이지
  
• ACM 문제 아카이브
  
• ACM_ICPC/Problems
  
  • 6500
    
    

• 온라인 예비소집 - 온라인 예선 - 지역 본선 - 세계 본선 순으로 이루어 진다.
  
• 문제는 전부 영어로 나온다.
  
• 3명이 한 컴퓨터를 쓰면 보통 어떻게 일을 분담하는가?
  
  • 한 명은 코딩하고, 나머지 두 명은 손으로 알고리즘을 구상. 번역을 잘 하는 사람이 있으면 문제를 번역해 주는 것도 괜찮다.
    
• 지도교수 한 분이 여러 팀을 맡을 수 있는가?
  
  • 된다. 하지만 제한이 있을 수 있으니 확인해 보는 것이 좋다.
    
• 온라인 예선에서 일정 문제 수 이상을 풀지 않으면 실격 될 수 있으니 유의.
  
• 본선에서 종이 25장에 (커버 포함, 양면 가능) 내용을 정리해 갈 수 있다. 단, 50cm 거리에서 식별이 가능해야 한다.
  
• 팀을 짜고 역할 분담을 하는 것도 매우 중요.
  
• 못 푼 문제 미련가지고 계속 붙잡지는 말자.
  
• ACM 참가한다고 하면 학교에서 경비와 이것 저것 지원을 해 준다.
  
• 1학년들도 경험 삼아 참가를 해 보는 것을 추천한다. 차후 나갈 때 도움이 될 것이며, 맛있는 것도 먹을 수 있다
  
  

• 작년에 성현이 형이 풀었던 문제 - 0번, 6번, 10번, 11번
  
  • 도전했던 문제 - 8, 9번
    
    

• 팀 별로 문제 풀이 진행
  
  

• 팀 별로 문제 풀이 진행
  
  • codeforces.com 이용
    
  • http://codeforces.com/contest/469
    
    

• 기본적인 자료구조 공부
  
  • dovelet 이용
    
    

• 조영준, 이원준, 권준혁
  
• dovelet/problems/race1