재밌는문제

다익스트라

BFS

  • ABC299E

    뭐야 이거 O(N+M)풀이가 정해인줄 알았는데, 에디토리얼은 NM설명하고 있다. 내 제출이 O(N+M)풀이임.

BellmanFord

게임이론

  • ARC112C
  • CF767 Game on Sum

    평형?안장점?을 관찰해서 dp transition을 그리디하게 해주는 재밌는 문제. Hard버전의 조합으로 바꾸는 테크닉도 알아둬야할듯.

  • https://codeforces.com/contest/1839/problem/E

DP

  • CF709 Div2E

  • 2449 전구

  • 2618 경찰차

  • 7579 앱

  • 1315 RPG

  • 6101 식당, monge는 아님

  • 8131 Ploughing, 관찰만으로 어려운 DP

  • https://codeforces.com/contest/1701/problem/F

  • 3114 사과와 바나나

    처음보면 R*R*C밖에 생각안나는데, 왼쪽에서 들어올때 위쪽영역값이 결정되고, 오른쪽으로 나갈때 아래쪽영역값 결정되므로 한칸씩 움직이면서 풀 수 있다.

  • 14752 Map Labeling

    NlogN최적화 가능하다는듯. 백준문제의 메모참고.

  • 재귀적 기댓값 점화식 https://codeforces.com/contest/1823/problem/F 재귀적인 점화식은 boj.kr/15264 이것도 있다.

그래프 모델링이 중요한 문제

  • BOJ1533 길의 개수

  • BOJ5214 환승

  • SCPC 2022 2차 3번

단조성

  • 17763 Fish, 원점을 꼭짓점으로 공유하는 직사각형들의 합집합 부피

Flow

  • POJ dual core cpu

  • 모비스 플로우문제: https://level.goorm.io 에서 5단계에 추가될듯? https://level.goorm.io/exam/152119/%ED%98%84%EB%8C%80%EB%AA%A8%EB%B9%84%EC%8A%A4-%EC%98%88%EC%84%A0-%EB%8F%84%EB%A1%9C%EB%A7%9D-%EC%84%A4%EA%B3%84/quiz/1

  • https://codeforces.com/contest/1913/submission/238217500 min cost flow 모델링

  • https://www.acmicpc.net/problem/12936 최소컷 모델링

  • https://www.acmicpc.net/problem/19579 최소컷 모델링 더 어려움

Constructive

  • 19614 Traveling Salesperson

미분류