적당한 프로그래밍 문제

  • nocut98
    nocut98

    음 누구나 짜기 쉽지만(30분 정도)
    개인의 알고리즘에 따라 속도차이가 크게 나는 문제 없을까요?
    퀴즈를 낼려고 하는데, 적당한 게 뭐가 있을지 고민이네요.
    현재는 s = a^2+b^2+c^3 으로 하려고 했는데, 코딩이 복잡해 질 꺼 같네요-

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]


    13년 전
3개의 댓글이 있습니다.
  • Yongrok
    Yongrok

    0과1로 이뤄진 매트릭스에서 1로만 이뤄진 가장 큰 사각형 찾기
    n^6에서부터 n^5, n^4, n^3 해가 존재하죠.
    내지는 이번 서울대회 B번도 괜찮지 않을까요.
    http://algospot.com/zbxe/openlecture/5108


    13년 전 link
  • JongMan
    JongMan

    정수로 이루어진 수열에서, 연속된 부분수열 중에 가장 합이 큰 것 찾기.
    고전인데요, 생각하는 프로그래밍에 보면 O(n^3), O(n^2) 의 무식한 해법과 O(nlgn) 의 분할정복, O(n) 의 동적계획법까지 다양한 방법을 제시하고 있죠.


    13년 전 link
  • cancho
    cancho

    1로 이루어진 가장 큰 사각형은 n^2해도 존재하죠.
    http://acm.pku.edu.cn/JudgeOnline/problem?id=2559
    이 문제를 Stack을 이용해 O(n)에 푸는 방법을 이용한다면...


    13년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.