진행 ¶
- 개강 후 첫 진행. 모두들 안녕하세요!
- 스터디 방식을 모여서 페어코딩 하는 식으로 변경.
- 페어/싱글로 해도 되며, 각각 풀고 싶은 문제를 풀고 끝나기 전에 직접/위키로 공유
- 페어/싱글로 해도 되며, 각각 풀고 싶은 문제를 풀고 끝나기 전에 직접/위키로 공유
- 다른 사이트를 사용하자는 의견이 있었음. 다음 스터디 하기 전까지 Slack에서 결정하기로.
문제 ¶
문제 ¶
논의사항 ¶
- 지금까지 진행해 본 결과 조금 더 뚜렷한 목표가 필요하는 의견이 나옴.
- 알고리즘 관련 문제 서적을 보거나 현재 진행하던 대로 유지하자는 등의 의견이 나옴.
- 의논을 해 본 결과 매 주 하나의 주제를 잡아서 스터디를 진행하자는 방향으로 의견이 수렴됨.
- 스터디 전에 하나의 주제를 정하고 스터디 때에는 해당 주제에 대해서 각자 하고 싶은 것들을 함.
- 주제에 대해 문제를 풀거나 해당 주제를 다룬 책을 읽거나 등 다양한 활동 가능.
- 스터디를 끝내기 30분 전에 각자 한 내용을 공유.
- 스터디 전에 하나의 주제를 정하고 스터디 때에는 해당 주제에 대해서 각자 하고 싶은 것들을 함.
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 부분
- 처음에 가장 많은 일들을 할당한다.
- 할당되지 않은 row를
- 처음에 가장 많은 일들을 할당한다.
- 처음에 가장 많은 일들을 할당한다?
- 할 수 있는 일이 하나인 애들 부터 할당
- 그 다음으로 여러 개 할 수 있는 애들을 할당한다
- 할 수 있는 일이 하나인 애들 부터 할당
- 조금 더 구체적으로 하자면...
n = 1 n이 배열의 크기보다 작을 경우 아래를 계속 반복한다. 모든 라인에 대해서 0이 n개가 있는 라인이 있는가? 있으면, 해당되는 라인들 중 하나의 라인에서 임의의 0을 할당시켜주고, 그 0의 가로/세로에 있는 다른 0들을 다른 값으로 바꿈. 그리고 n을 1로 세팅. 없으면, n을 1 증가.
생각나는 대로 쓰는 헝가리안 순서! ¶
- 입력
- n*n 행렬 만들기
- n*n 행렬이 아닐 경우에 행렬의 최대값으로 행 또는 열을 추가해서 n*n행렬을 만들어버림
- n*n 행렬이 아닐 경우에 행렬의 최대값으로 행 또는 열을 추가해서 n*n행렬을 만들어버림
- 행에 대해서 그 행의 최소값으로 전부 뺌
- 0이 없는 열이 있을 경우 열에 대해서 연산한다. 그 열의 최소값으로 전부 빼기
- 최소한의 선으로 0들을 모두 포함하는 선들을 그린다 (알고리즘 문제 2..)(위키피디아 Matrix 계산 step 3 부분)
- 열과 행이 겹치지 않게 최대한 많은 0들을 고른다. (이것도 알고리즘 문제...)
- 선택되지 않은 모든 행들을 마크한다
- 바로 위의 행에서 0으로 기록된 열들을 모두 마크한다
- 바로 위의 열에서 일을 할당 받은 모든 행을 마크한다
- 일정한 패턴이 나올때 까지 계속 반복한다.
- 열과 행이 겹치지 않게 최대한 많은 0들을 고른다. (이것도 알고리즘 문제...)
- 선들이 그려지지 않은 부분에서 최소값을 찾아서 선들이 그려진 부분에 더한다. 두번 겹친 부분은 두번 더함
- 전체 배열에서 최소값을 찾아 전부 뺀다
- 0 덮기. 최소한의 선이 행의 갯수와 같지 않으면 다시 위에 연산, 같으면 탈출
- 이제 행과 열을 겹치지 않게 0 선택하기.
- 최초의 배열에 적용하면 최소값 고르기 완성.
소소한 팁 ¶
- 초기에 입력받는 값들이 음수여도 괜찮.
- 첫번째 스텝에서 '최솟값'을 빼기 때문에, 결국 모두 양수가 됨.
- 첫번째 스텝에서 '최솟값'을 빼기 때문에, 결국 모두 양수가 됨.
- 입력받은 배열이 n*n이 아닐 경우 빈 곳에 최댓값을 넣어서 n*n으로 만들어야 함
- 입력받은 배열에 전부 -1을 곱할 경우 '최소 비용' 이 아닌 '최대 비용'을 구할 수 있음.
8월 16일 ¶
ACM ICPC 참가 신청이 시작되었습니다. 그에 따라 ACM 기출 문제 풀이를 진행하려고 합니다.
기타 오갔던 이야기들
기타 오갔던 이야기들
- 온라인 예비소집 - 온라인 예선 - 지역 본선 - 세계 본선 순으로 이루어 진다.
- 문제는 전부 영어로 나온다.
- 3명이 한 컴퓨터를 쓰면 보통 어떻게 일을 분담하는가?
- 한 명은 코딩하고, 나머지 두 명은 손으로 알고리즘을 구상. 번역을 잘 하는 사람이 있으면 문제를 번역해 주는 것도 괜찮다.
- 한 명은 코딩하고, 나머지 두 명은 손으로 알고리즘을 구상. 번역을 잘 하는 사람이 있으면 문제를 번역해 주는 것도 괜찮다.
- 지도교수 한 분이 여러 팀을 맡을 수 있는가?
- 된다. 하지만 제한이 있을 수 있으니 확인해 보는 것이 좋다.
- 된다. 하지만 제한이 있을 수 있으니 확인해 보는 것이 좋다.
- 온라인 예선에서 일정 문제 수 이상을 풀지 않으면 실격 될 수 있으니 유의.
- 본선에서 종이 25장에 (커버 포함, 양면 가능) 내용을 정리해 갈 수 있다. 단, 50cm 거리에서 식별이 가능해야 한다.
- 팀을 짜고 역할 분담을 하는 것도 매우 중요.
- 못 푼 문제 미련가지고 계속 붙잡지는 말자.
- ACM 참가한다고 하면 학교에서 경비와 이것 저것 지원을 해 준다.
- 1학년들도 경험 삼아 참가를 해 보는 것을 추천한다. 차후 나갈 때 도움이 될 것이며, 맛있는 것도 먹을 수 있다
8월 30일 ¶
6502번 문제를 풀다가 펑. 이원준과 조영준 둘 다 수학적으로 접근하다가 시간을 매우 많이 잡아먹었습니다.
한 두 개 직접 해 보다가 '이 식이 아닐까' 싶은 것은 나왔으나 증명은 실패.
한 두 개 직접 해 보다가 '이 식이 아닐까' 싶은 것은 나왔으나 증명은 실패.
스터디 시간을 월요일 오후 7시로 옮겼습니다. 다만, 9월 1일에는 쉬며, 평소에도 ACM 나가는 사람들끼리 모여 별도로 문제를 풀어볼 계획입니다.
