algorithmStudy/2013

1월 14일

  • in_out(http://183.106.113.109/30stair/in_out/in_out.php?pname=in_out)
  • ubiquitous(http://183.106.113.109/30stair/ubiquitous/ubiquitous.php?pname=ubiquitous)

1월 21일

  • matrixprod(http://183.106.113.109/30stair/matrixprod/matrixprod.php?pname=matrixprod)
  • poop(http://183.106.113.109/30stair/poop/poop.php?pname=poop)

1월 28일

2월 4일

2월 11일

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

2월 18일

2월 25일

3월 25일

참가자

진행

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

문제

4월 2일

참가자

문제

4월 9일

참가자

문제

4월 29일

참가자

논의사항

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

다음 주 주제

  • Greedy Algorithm

in the interest of time

  • Greedy Algorithm
  • Dynamic Programming
  • Tree
  • Graph

7월 1일

7월 12일

7월 26일

meterials

논의

  • 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 계산(http://en.wikipedia.org/wiki/Hungarian_algorithm#Matrix_interpretation) step 3 부분)
    1. 열과 행이 겹치지 않게 최대한 많은 0들을 고른다. (이것도 알고리즘 문제...)
    2. 선택되지 않은 모든 행들을 마크한다
    3. 바로 위의 행에서 0으로 기록된 열들을 모두 마크한다
    4. 바로 위의 열에서 일을 할당 받은 모든 행을 마크한다
    5. 일정한 패턴이 나올때 까지 계속 반복한다.
  6. 선들이 그려지지 않은 부분에서 최소값을 찾아서 선들이 그려진 부분에 더한다. 두번 겹친 부분은 두번 더함
  7. 전체 배열에서 최소값을 찾아 전부 뺀다
  8. 0 덮기. 최소한의 선이 행의 갯수와 같지 않으면 다시 위에 연산, 같으면 탈출
  9. 이제 행과 열을 겹치지 않게 0 선택하기.
  10. 최초의 배열에 적용하면 최소값 고르기 완성.

소소한 팁

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

8월 16일

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

8월 23일

오늘의 문제(https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=609&page=show_problem&problem=4512): 네 명 다 펑... 이런 문제는 버리자.
  • 작년에 성현이 형이 풀었던 문제 - 0번, 6번, 10번, 11번
    • 도전했던 문제 - 8, 9번

8월 30일

6502번 문제를 풀다가 펑. 이원준과 조영준 둘 다 수학적으로 접근하다가 시간을 매우 많이 잡아먹었습니다.
한 두 개 직접 해 보다가 '이 식이 아닐까' 싶은 것은 나왔으나 증명은 실패.

스터디 시간을 월요일 오후 7시로 옮겼습니다. 다만, 9월 1일에는 쉬며, 평소에도 ACM 나가는 사람들끼리 모여 별도로 문제를 풀어볼 계획입니다.

9월 15일

2013 뉴욕 문제(https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=617) 전제적으로 풀기

9월 22일

  • 팀 별로 문제 풀이 진행

9월 29일

10월 6일

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

11월 24일

Retrieved from http://wiki.zeropage.org/wiki.php/algorithmStudy/2014
last modified 2021-02-07 05:31:35