[algorithmStudy/2013] == 1월 14일 == * [http://183.106.113.109/30stair/in_out/in_out.php?pname=in_out in_out] * [http://183.106.113.109/30stair/ubiquitous/ubiquitous.php?pname=ubiquitous ubiquitous] == 1월 21일 == * [http://183.106.113.109/30stair/matrixprod/matrixprod.php?pname=matrixprod matrixprod] * [http://183.106.113.109/30stair/poop/poop.php?pname=poop poop] == 1월 28일 == * [/shredding] == 2월 4일 == * [/pigs] == 2월 11일 == * [/virtual]을 풀었으면 [/pigs]도 다시 풀어 오는 것으로. == 2월 18일 == * [/koi_virus] == 2월 25일 == * [/ioi_raisins] * 너무 어려워서 다같이 GG. == 3월 25일 == === 참가자 === * [조영준], [권영기], [서지혜], [강성현], [이진규], [서민관] === 진행 === * 개강 후 첫 진행. 모두들 안녕하세요! * 스터디 방식을 모여서 페어코딩 하는 식으로 변경. * 페어/싱글로 해도 되며, 각각 풀고 싶은 문제를 풀고 끝나기 전에 직접/위키로 공유 * 다른 사이트를 사용하자는 의견이 있었음. 다음 스터디 하기 전까지 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 == 4월 2일 == === 참가자 === * [조영준], [이진규] === 문제 === * 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 == 4월 9일 == === 참가자 === * [서민관], [이원준], [권영기], [조영준], [이진규] (온라인 참가) === 문제 === * codejam 2012 practice : https://code.google.com/codejam/contest/1460488/dashboard == 4월 29일 == === 참가자 === * [권영기], [서민관], [이원준], [이진규], [조영준] === 논의사항 === * 지금까지 진행해 본 결과 조금 더 뚜렷한 목표가 필요하는 의견이 나옴. * 알고리즘 관련 문제 서적을 보거나 현재 진행하던 대로 유지하자는 등의 의견이 나옴. * 의논을 해 본 결과 매 주 하나의 주제를 잡아서 스터디를 진행하자는 방향으로 의견이 수렴됨. * 스터디 전에 하나의 주제를 정하고 스터디 때에는 해당 주제에 대해서 각자 하고 싶은 것들을 함. * 주제에 대해 문제를 풀거나 해당 주제를 다룬 책을 읽거나 등 다양한 활동 가능. * 스터디를 끝내기 30분 전에 각자 한 내용을 공유. === 다음 주 주제 === * Greedy Algorithm == in the interest of time == * Greedy Algorithm * Dynamic Programming * Tree * Graph == 7월 1일 == * 참가자: [이원준], [조영준] * 내용: http://183.106.113.109/30stair/tram/tram.php?pname=tram + union find == 7월 12일 == * 참가자: [서지혜], [강성현], [조영준] * Hungarian Method == 7월 26일 == * 참가자: [이원준], [조영준] * Hungarian Merthod cont. === meterials === * 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. 처음에 가장 많은 일들을 할당한다. 1. 할당되지 않은 row를 * 처음에 가장 많은 일들을 할당한다? * 할 수 있는 일이 하나인 애들 부터 할당 * 그 다음으로 여러 개 할 수 있는 애들을 할당한다 * 조금 더 구체적으로 하자면... {{{ n = 1 n이 배열의 크기보다 작을 경우 아래를 계속 반복한다. 모든 라인에 대해서 0이 n개가 있는 라인이 있는가? 있으면, 해당되는 라인들 중 하나의 라인에서 임의의 0을 할당시켜주고, 그 0의 가로/세로에 있는 다른 0들을 다른 값으로 바꿈. 그리고 n을 1로 세팅. 없으면, n을 1 증가. }}} === 생각나는 대로 쓰는 헝가리안 순서! === 1. 입력 1. NxN 행렬 만들기 1. NxN 행렬이 아닐 경우에 행렬의 최대값으로 행 또는 열을 추가해서 NxN행렬을 만들어버림 1. 행에 대해서 그 행의 최소값으로 전부 뺌 1. 0이 없는 열이 있을 경우 열에 대해서 연산한다. 그 열의 최소값으로 전부 빼기 1. 최소한의 선으로 0들을 모두 포함하는 선들을 그린다 1. ㅇ 1. 선들이 그려지지 않은 부분에서 최소값을 찾아서 선들이 그려진 부분에 더한다. 두번 겹친 부분은 두번 더함 1. 전체 배열에서 최소값을 찾아 전부 뺀다 1. 0 덮기. 최소한의 선이 행의 갯수와 같지 않으면 다시 위에 연산, 같으면 탈출 1. 이제 행과 열을 겹치지 않게 0 선택하기. 1. 최초의 배열에 적용하면 최소값 고르기 완성. === 소소한 팁 === * 초기에 입력받는 값들이 음수여도 괜찮. * 첫번째 스텝에서 '최솟값'을 빼기 때문에, 결국 모두 양수가 됨. * 입력받은 배열이 n*n이 아닐 경우 빈 곳에 최댓값을 넣어서 n*n으로 만들어야 함 * 입력받은 배열에 전부 -1을 곱할 경우 '최소 비용' 이 아닌 '최대 비용'을 구할 수 있음.