'merge sort' 태그의 글 목록

merge sort

2017. 12. 10. 00:52

로프를 병렬로 묶을 수 있다.

병렬로 묶는다는건 내림차순으로 정렬된 리스트가 있을때

그 리스트의 길이는 N 이라고 치자

그러면 시그마 i = N 시그마 i ~ N 의 값중에 제일 큰 값이 답이다.

	#include <cstdio>
	/**
	* https://www.acmicpc.net/problem/2217
	* BOJ 백준온라인져지 2217 로프 풀이
	*/
	int ropeList[100001];
	int tempRopeList[100001];
	void mergeSort(int l, int r){
	if(l < r){
	int mid = (l + r) / 2;
	mergeSort(l, mid);
	mergeSort(mid + 1, r);

	int i = l, j = mid + 1, k = l, cnt = 0;
	while(i <= mid && j <= r){
	if(ropeList[j] > ropeList[i])
	tempRopeList[k++] = ropeList[j++];
	else
	tempRopeList[k++] = ropeList[i++];
	}
	while(i <= mid){
	tempRopeList[k++] = ropeList[i++];
	}
	while(j <= r){
	tempRopeList[k++] = ropeList[j++];
	}
	while(l <= r){
	ropeList[l] = tempRopeList[l];
	l++;
	}
	}
	}

	int main(){
	int N;
	scanf("%d", &N);

	for(int i = 0; i < N; i++){
	scanf("%d", &ropeList[i]);
	}

	mergeSort(0, N - 1);

	int result = 0;

	for(int i = 0; i < N; i++){
	if(result < ropeList[i] * (i + 1)) result = ropeList[i] * (i + 1);
	}

	printf("%d", result);
	}

view raw BOJ_2217.cpp hosted with ❤ by GitHub

2017. 12. 9. 23:59

처음에 선택정렬을 사용 => 시간초과

퀵 소트 사용 => 메모리초과

퀵 소트 특성상 마지막에 함수들을 부른다.

머지 소트 => 성공

머지소트는 먼저 함수들을 불러서 메모리가 적게든다.

	#include <cstdio>
	/**
	* https://www.acmicpc.net/problem/1931
	* BOJ 백준온라인져지 1931 회의실배정 풀이
	*/
	struct Time{
	int startTime, endTime;
	};
	bool isBiggerAThanB(Time &A, Time &B){
	if(A.endTime == B.endTime)
	return A.startTime > B.startTime;
	return A.endTime > B.endTime;
	}
	Time timeList[100001];
	Time tempTimeList[100001];
	void mergeSort(int l, int r){
	if(l < r){
	int mid = (l + r) / 2;
	mergeSort(l, mid);
	mergeSort(mid + 1, r);

	int i = l, j = mid + 1, k = l, cnt = 0;
	while(i <= mid && j <= r){
	if(isBiggerAThanB(timeList[i], timeList[j]))
	tempTimeList[k++] = timeList[j++];
	else
	tempTimeList[k++] = timeList[i++];
	}
	while(i <= mid){
	tempTimeList[k++] = timeList[i++];
	}
	while(j <= r){
	tempTimeList[k++] = timeList[j++];
	}
	while(l <= r){
	timeList[l] = tempTimeList[l];
	l++;
	}
	}
	}

	int main(){
	int N;
	scanf("%d", &N);

	for(int i = 0; i < N; i++){
	scanf("%d%d", &timeList[i].startTime, &timeList[i].endTime);
	}

	mergeSort(0, N - 1);

	int result = 0, endTime = -1;

	for(int i = 0; i < N; i++){
	if(timeList[i].startTime >= endTime){
	result++, endTime = timeList[i].endTime;
	}
	}

	printf("%d", result);
	}

view raw BOJ_1931.cpp hosted with ❤ by GitHub

PREV 1 NEXT

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`