티스토리

코딩일지
검색하기

블로그 홈

코딩일지

convex.tistory.com/m

snowflake17 님의 블로그입니다.

구독자
1
방명록 방문하기

주요 글 목록

  • SOS DP 어떤 원소 N개짜리 집합에서 모든 부분집합에 대해 어떤 연산을 한 결과를 전부 더한 값을 알고 싶을 때가 있다. 간단하게 비트마스킹으로 구현하면 이렇게 된다. for (int mask = 0; mask < (1 공감수 0 댓글수 0 2023. 9. 7.
  • Dynamic Programming - Convex Hull Trick 이번엔 DP를 최적화하는 심화 기법에 대해서 알아보겠다. CHT, Convex Hull Optimization이라고도 불린다. 번역하면 볼록 껍질을 이용한 최적화 정도가 되겠다. 이름에서 볼록 껍질이 나오다시피 볼록 껍질을 응용해서 하나의 쿼리의 시간복잡도를 줄이는 것이다. 대표적으로 \(O(N)\)의 쿼리를 \(O(\log N)\)으로 줄이는 최솟값/최댓값 쿼리가 있다. 하지만 항상 사용할 수 있는 최적화 기법은 아니고, 최솟값/최댓값을 구하고자 하는 배열의 일부가 단조감소 혹은 단조증가할 때만 사용할 수 있다. 이렇게 말하면 너무 어려우니 예시를 보자. 아 그리고 이제 글에 \(\LaTeX\)이 적용이 돼서 기분이 너무 좋다. 이제 N^2나 a_1같은 표기 안봐도된다. 화살표도 \(\Rightarro.. 공감수 0 댓글수 0 2023. 6. 7.
    문의안내
    • 티스토리
    • 로그인
    • 고객센터

    티스토리는 카카오에서 사랑을 담아 만듭니다.

    © Kakao Corp.