전체 글 (21) 썸네일형 리스트형 [Day 1] 백준 1937 : 욕심쟁이 판다 해법 : 이것도 greedy 음 사실 이것도 처음에 dfs로 뻘 코딩을 했다가 다시 생각해보았다. 사실 제목부터가... 물론 다른 의미지만 왜 greedy같은 형식으로 문제 푸는 것이 가능할까? 판다가 선택하는 기준에 방향성이 있기 때문인 것 같다. 시간복잡도와 내용을 고려해서 한 번 더 고민하는 것이 필요할듯.. #include #include #include #include using namespace std; int n; int A[505][505]; struct tuple2 { int x,y,val; }; tuple2 s[250005]; int _x[4]={1,-1,0,0}; int _y[4]={0,0,1,-1}; int m[505][505]; int _max; bool sf(tuple2 a,tu.. [C++] STL sort 시간복잡도 : O(n*logn) 추가해줘야할 헤더 : #include 사용법 : sort(A,A+n); (구조체, 배열) sort(A.begin(),A.end()); (vector 형식) #include #include #include using namespace std; int n; struct tuple2 { long long s,e; }; tuple2 A[100000+5]; bool sf(tuple2 a,tuple2 b) { if(a.e==b.e) { return a.s [Day 2] 백준 1931 : 회의실 배정 해법 : 정렬 후 greedy 사실 처음보고 무조건 DP로 짰다가 시간초과가 나와서 다시 생각해보았다. 해답은 회의가 끝나는 시간을 기준으로 오름차순 정렬한 뒤에 배열의 앞에서부터 보면서 조건에 맞는(회의 시작 시간이 내가 담은 회의들이 끝나는 시간이 크거나 같은 애들)을 담으면 된다. 왜 Greedy 가 해법일까? 조건에 맞는애가 있을 때 그 애를 선택하지 않고 다음 거를 선택했을 때 얻을 수 있는 이익이 없다. 즉, 현재 지점을 i라고 한다면 i대신 i+1을 선택했을 때(i+1도 조건에 맞는다고 가정하면) 얻는 이익이 없다는 것이다. 그 이유는 회의 종료 시간을 기준으로 정렬했기 때문에 i의 회의 종료 시간이 i+1의 회의 종료시간보다 작거나 같기 때문이다. #include #include #incl.. 이전 1 ··· 4 5 6 7 다음