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들을 모두 포함하는 선들을 그린다
   
   1. ㅇ
      
6. 선들이 그려지지 않은 부분에서 최소값을 찾아서 선들이 그려진 부분에 더한다. 두번 겹친 부분은 두번 더함
   
7. 전체 배열에서 최소값을 찾아 전부 뺀다
   
8. 0 덮기. 최소한의 선이 행의 갯수와 같지 않으면 다시 위에 연산, 같으면 탈출
   
9. 이제 행과 열을 겹치지 않게 0 선택하기.
   
10. 최초의 배열에 적용하면 최소값 고르기 완성.
    

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