[일반] 개인적으로 1번이 작년이랑 재작년 1번보다 어려웠는데

[익명(221.153)]

왜 다 쉬웠다는거야
자괴감드내

[00가나(221.157)]

나도. ㅠ

[익명(180.182)]

1번 Maxsum 구하기 혹은 이분 탐색 2가지만 알아도 풀이법 바로떠올릴수 있는데

[익명(221.153)]

이분탐색방법은 머야?

[익명(221.153)]

Maxsum은 투포인터 얘기인가, 그거는 듣고알았음 ㅅㅂ

[익명(180.182)]

nlogn 솔루션으로

[익명(180.182)]

N이 20만이니까 group을 처음에 N/2로 나눌수 있다고 가정하고 탐색 -> 한번 검사에 O(n)

[익명(180.182)]

그룹 나누기 성공하면 N/4로 나눈다고 가정하고 탐색

[익명(180.182)]

실패하면 3*N/4 로 가정하고 탐색 이런거 반복하는걸로 풀수있어

[익명(221.153)]

허...걍 내가 바본가보다

[익명(180.182)]

http://blog.naver.com/PostView.nhn?blogId=zxy826&logNo=220896456728&beginTime=0&jumpingVid=&from=section&redirect=Log&widgetTypeCall=true

[익명(180.182)]

구글에 검색하면 맨위에 있는 블로그

[익명(221.153)]

근데 그룹나누는기준이 뭐야? 설명듣고도 모르겠네

[익명(221.153)]

이분탐색이 먼지아는데 문제를 풀때 어케썻는지몰겟어 ㅜ

[익명(180.182)]

maxsum에서 최대합 구하는 방법 응용해서 정렬한 이후에 pivot 2개 두고 구간 조정해가면서 최대 사람 포함 구간 찾아서 O(n)만에 해결도 가능 문제는 정렬이 O(nlogn) 이라 이것도 O(nlogn)이긴함..

[익명(221.153)]

ㄴ투포인터는 듣고 이해하긴햇음...근데 이분탐색은 어케한지모르겟다

[00가나(221.157)]

오 maxsum이라는 것도 있군요

[익명(180.182)]

저 블로그 이분탐색 게시글 기준으로하면 arr[m] < k대신에 함수를 두고

[익명(180.182)]

함수는 parameter를 현재 탐색하고자 하는 그룹의 사람수로 둬서

[익명(180.182)]

함수 내부에는 선형적 탐색하면서 그리디하게 그룹에 한명씩 집어넣으면서 하면됨

[익명(180.182)]

예를들어 총 N이 20명이고 현재 나누고자 하는 그룹이 10이라면

[익명(180.182)]

미리 방 10개 만들어두고

[익명(180.182)]

만나는 사람순서대로 0, 1, 2, 3, 4, --- , 0, 1, 2, 3, --- 이렇게 차례대로 집어넣는데

[익명(180.182)]

마지막에 집어넣은 사람이랑 지금 집어넣으려는 사람이랑 차이가 얼마 없다면 실패로 간주 끝까지 도달한다면 성공

[익명(180.182)]

근데 Maxsum방법 응용한게 더 나은 풀이방법이라 이분탐색을 응용해서도 풀 수 잇다 정도로 알고있으면 될듯

[익명(221.153)]

ㄱㅅㄱㅅ 한번 읽으면서 이해해보겟음, 투포인터가 직관적이라 이해하기는 더 쉬워서