본문 바로가기 메뉴 바로가기

구사과

프로필사진
  • 글쓰기
  • 관리
  • 태그
  • 방명록
  • RSS

구사과

검색하기 폼
  • 분류 전체보기 (215) N
    • 공부 (179) N
    • 음악 (21)
    • 생각 (15)
  • 방명록

Linear Programming Duality

관련 내용이 이 블로그에도 매우 잘 나와 있으니 같이 보면 좋을듯. 이 글에서는 LP에 대한 정의를 안다는 것을 가정하기 때문에, 정의를 모른다면 링크한 블로그를 참고해야 한다.  직관 다음과 같은 LP 문제를 생각해 보자.$\text{Maximize: } 4x + 4y$$\text{Subject to: } x + y \leq 3,x, y \geq 0 $이 문제의 답은 굉장히 자명하다. $(x+y) \leq 3$ 이라는 조건이 있으니, $..

공부 2019.01.21 00:35
더불어민규당 2019년 신년 연습

1월 1일 심야: Petrozavodsk Winter 2018. ITMO Contest 좋은 셋이냐 하면 그건 잘 모르겠는데... 확실히 배울 건 많은 셋이었다. 그래도 이번 신년 연습 중에서는 이게 그나마 제일 정상이었던 거 같다 (...) A는 적분 식을 찾았으나 너무 복잡해서 포기했다. 하지만 그 복잡한 적분을 노가다하는게 정해였다고 한다(...) 우웩 F는 connection 정보를 관리하는 DP를 짜면, 가능한 연결 상태가 약 3000..

공부 2019.01.15 01:33
2018.12.29 problem solving

Topcoder SRM 744 Easy는 그대로는 매우 귀찮으나, 2차원 부분합을 구할 때 쓰는 포함 배제 테크닉을 활용하면 조금 덜 귀찮아진다. 물론 그래도 귀찮다. 난 문제를 잘못 읽어서 망했다. Medium은 행과 열에 대해서 해당 행 / 열을 뒤집었는가? 를 나타내는 $n+m$ 개의 boolean 변수를 잡으면, 주어진 조건은 $X_i + X_j$ 의 홀짝성에 대한 제약조건으로 바뀐다. 이를 일종의 이분 그래프라고 생각하고 풀어주면 된다..

공부 2018.12.29 19:14
이전 1 2 3 4 5 ··· 72 다음
이전 다음
공지사항
최근에 올라온 글
  • Petrozavodsk Winter 2019..
  • OS X에 새로 생긴 캡처 딜..
  • 더불어민규당 Petrozavodsk..
  • Linear Programming Duality
Total
183,299
Today
18
Yesterday
545

Blog is powered by Tistory / Designed by Tistory

티스토리 툴바

Tistory
로그인
  • 페이스북 공유하기
  • 카카오톡 공유하기
  • 카카오스토리 공유하기
  • 트위터 공유하기