algorithmStudy/2014 (rev. 1.36)
진행 ¶
- 개강 후 첫 진행. 모두들 안녕하세요!
- 스터디 방식을 모여서 페어코딩 하는 식으로 변경.
- 페어/싱글로 해도 되며, 각각 풀고 싶은 문제를 풀고 끝나기 전에 직접/위키로 공유
- 다른 사이트를 사용하자는 의견이 있었음. 다음 스터디 하기 전까지 Slack에서 결정하기로.
논의사항 ¶
- 지금까지 진행해 본 결과 조금 더 뚜렷한 목표가 필요하는 의견이 나옴.
- 알고리즘 관련 문제 서적을 보거나 현재 진행하던 대로 유지하자는 등의 의견이 나옴.
- 의논을 해 본 결과 매 주 하나의 주제를 잡아서 스터디를 진행하자는 방향으로 의견이 수렴됨.
- 스터디 전에 하나의 주제를 정하고 스터디 때에는 해당 주제에 대해서 각자 하고 싶은 것들을 함.
- 주제에 대해 문제를 풀거나 해당 주제를 다룬 책을 읽거나 등 다양한 활동 가능.
- 스터디를 끝내기 30분 전에 각자 한 내용을 공유.
in the interest of time ¶
- Greedy Algorithm
- Dynamic Programming
- Tree
- Graph
7월 26일 ¶
- 참가자: 이원준, 조영준
- Hungarian Merthod cont.
논의 ¶
- 0들을 어떻게 최소한 라인으로 덮는가?
- 위키피디아 해답 step 3 부분
- 처음에 가장 많은 일들을 할당한다.
- 할당되지 않은 row를
- 처음에 가장 많은 일들을 할당한다?
- 할 수 있는 일이 하나인 애들 부터 할당
- 그 다음으로 여러 개 할 수 있는 애들을 할당한다
- 조금 더 구체적으로 하자면...
n = 1
n이 배열의 크기보다 작을 경우 아래를 계속 반복한다.
모든 라인에 대해서 0이 n개가 있는 라인이 있는가?
있으면, 해당되는 라인들 중 하나의 라인에서 임의의 0을 할당시켜주고, 그 0의 가로/세로에 있는 다른 0들을 다른 값으로 바꿈. 그리고 n을 1로 세팅.
없으면, n을 1 증가.
생각나는 대로 쓰는 헝가리안 순서! ¶
- 입력
- n*n 행렬 만들기
- n*n 행렬이 아닐 경우에 행렬의 최대값으로 행 또는 열을 추가해서 n*n행렬을 만들어버림
- 행에 대해서 그 행의 최소값으로 전부 뺌
- 0이 없는 열이 있을 경우 열에 대해서 연산한다. 그 열의 최소값으로 전부 빼기
- 최소한의 선으로 0들을 모두 포함하는 선들을 그린다 (알고리즘 문제 2..)(위키피디아 Matrix 계산 step 3 부분)
- 열과 행이 겹치지 않게 최대한 많은 0들을 고른다. (이것도 알고리즘 문제...)
- 선택되지 않은 모든 행들을 마크한다
- 바로 위의 행에서 0으로 기록된 열들을 모두 마크한다
- 바로 위의 열에서 일을 할당 받은 모든 행을 마크한다
- 일정한 패턴이 나올때 까지 계속 반복한다.
- 선들이 그려지지 않은 부분에서 최소값을 찾아서 선들이 그려진 부분에 더한다. 두번 겹친 부분은 두번 더함
- 전체 배열에서 최소값을 찾아 전부 뺀다
- 0 덮기. 최소한의 선이 행의 갯수와 같지 않으면 다시 위에 연산, 같으면 탈출
- 이제 행과 열을 겹치지 않게 0 선택하기.
- 최초의 배열에 적용하면 최소값 고르기 완성.
소소한 팁 ¶
- 초기에 입력받는 값들이 음수여도 괜찮.
- 첫번째 스텝에서 '최솟값'을 빼기 때문에, 결국 모두 양수가 됨.
- 입력받은 배열이 n*n이 아닐 경우 빈 곳에 최댓값을 넣어서 n*n으로 만들어야 함
- 입력받은 배열에 전부 -1을 곱할 경우 '최소 비용' 이 아닌 '최대 비용'을 구할 수 있음.
8월 16일 ¶
ACM ICPC 참가 신청이 시작되었습니다. 그에 따라 ACM 기출 문제 풀이를 진행하려고 합니다.
