(백준 13904번 과제 C++) 라이님 블로그 대회 알고리즘 따라잡기 3) 그리디 알고리즘(Greedy Algorithm) 2탄

오늘은 과제가 많은 웅찬이가 좋은 학점을 받도록 도와주고자 한다.(문제 내용의 일부임, 웅찬이 모름)

 

요건 그리디 알고리즘 1탄!↓

2023.12.29 - [알고리즘] - (백준 1969번 DNA C++) 라이님 블로그 대회 알고리즘 따라잡기 3) 그리디 알고리즘(Greedy Algorithm) 1탄

(백준 1969번 DNA C++) 라이님 블로그 대회 알고리즘 따라잡기 3) 그리디 알고리즘(Greedy Algorithm) 1탄

배경지식

1. 정렬방식

내가 본 블로그 중에서 이게 제일 정확한거 같다. 설명이 개쩌니까 한 번 읽어보는걸 추천!!!!!!!!!

(그래놓고 버블정렬로 짰다 ㅋ)

https://d2.naver.com/helloworld/0315536

출처 : https://d2.naver.com/helloworld/0315536

참조 지역성 원리의 관점에서

- Heap sort는 참조 지역성이 좋지 않은 정렬이다. 

- Merge sort는 참조 지역성의 원리는 어느 정도 잘 만족하지만, 메모리가 많이 든다는 단점이 있다.

- Quick sort는  참조 지역성이 좋으며, 평균 시간 복잡도가 Heap sort, Merge sort보다 좋다고 알려져 있다. 하지만 최악의 경우 $O(n^2)$이 될 수 있다는 단점이 있다. 

백준 13904번 

https://www.acmicpc.net/problem/13904

13904번: 과제

일단 아이디어는 매우 간단했으나..

디버깅 과정은 순탄하지 않았다^^

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
bool CheckBlanck(int* Sch, int DL); //빈칸 있으면 false, 없으면 true
int  main() {
	int N; scanf("%d", &N);
	int** Arr = new int* [N]; // N * 2 배열
	int Sch[1001] = { 0 };
	for (int i = 0; i < N; i++) {
		Arr[i] = new int[2];
		scanf("%d %d", &Arr[i][0], &Arr[i][1]);
	}
	// Arr을 sorting(과제 점수가 높은 순으로, 과제 점수가 같다면 기한이 짧은 순으로)
	int temp0, temp1;
	for (int i = 1; i < N ; i++) {
		for (int j = 0; j < N - i; j++) {
			if (Arr[j][1] < Arr[j + 1][1]){
				temp0 = Arr[j][0];
				temp1 = Arr[j][1];
				Arr[j][0] = Arr[j + 1][0]; 
				Arr[j][1] = Arr[j + 1][1];
				Arr[j + 1][0] = temp0;	   
				Arr[j + 1][1] = temp1;
			}
			else if (Arr[j][1] == Arr[j + 1][1] and Arr[j + 1][0] < Arr[j][0]) {
				temp0 = Arr[j][0];
				Arr[j][0] = Arr[j + 1][0];
				Arr[j + 1][0] = temp0;
			}
		}
	}

	
	int DL, Score; 
	for (int i = 0; i < N; i++) {
		DL = Arr[i][0]; // 과제 마감기한		
		Score = Arr[i][1]; // 과제 점수
		if (Sch[DL] == 0) Sch[DL] = Score;
		else if (Sch[DL] < Score and CheckBlanck(Sch, DL)) Sch[DL] = Score;
		else {
			while (1) {
				--DL;
				if (Sch[DL] == 0) {
					Sch[DL] = Score;
					break;
				}
				else if (Sch[DL] < Score and CheckBlanck(Sch, DL)){
					Sch[DL] = Score;
					break;
				}
				if (DL <= 0) break;
			}
		}
	}
	

	int Sum = 0;
	for (int i = 1; i < 1001; i++) Sum += Sch[i];
	printf("%d", Sum);

	for (int i = 0; i < N; i++) delete []Arr[i];
	delete[] Arr;
	return 0;
}

bool CheckBlanck(int* Sch, int DL) { 
	if (DL == 1) {
		if (Sch[DL] == 0) return false;
		else return true;
	}
	for (int i = 1; i < DL; i++) {
		if (Sch[i] == 0) return false;
	}
	return true;
}

 

오늘의 실수

1. Bubble sort를 잘못 짰다. 이 부분에서 시간을 잡아먹었다. 내 풀이의 경우 점수가 높은 순서로 배열하는 내림차순 배열로 Bubble sort에서 이중 for loop이 크게 한 바퀴 돌면 가장 뒤에 점수가 가장 작은 과제가 배치된다. 이중 배열을 사용할 때는 그 범위를 주의해야 하는데, 나는 이 부분을 고려하지 못했다. 

 

2.  과제 마감일까지 남은 일수는 최대 1000일까지 가능하며, index입장에서 1000이라는 것은 1001번째 배열칸을 의미한다는 것을 생각하지 못했다. 그래서 i < 1000이라고 했던 걸 i < 1001로 고치니 코드가 정답이 되었는데, 인덱스 차원에서와 실제 순번 사이의 관계를 항상 잘 생각하고 코딩해야겠다.

 

3. 이 문제가 안 풀릴 누군가를 위해..

내가 디버깅할 때 쓴 반례들을 공유한다. 개인적으로 세 번째 반례로 많은 걸 고쳤기 때문에 한 번 돌려보는걸 추천한다.

 

4
1 500
2 250
2 400
2 350

5
1 500
2 250
2 300
2 550
2 600

3
1000 1
1000 2
1000 3

 

 

그리고 내 풀이가 좀 마음에 안 들어서 다른 분 풀이를 참고해보았다. (terryaa님 풀이 )

가져와도 될지 모르겠어서 배울만한 점만 적어보았다.

 

우선 pair<int, int>로 input을 받아주고, sort함수를 이용해 정렬해준다.

아래 같이 짠 코드는 처음봤는디 심박했다.

sort(p, p + N, [](pair<int,int> &a, pair<int,int> &b) {
		if (a.second != b.second) return a.second > b.second;
		return a.first < b.first;
	});

https://blog.caputdraconis.dev/entry/C-pair-vector%EB%A5%BC-sort-%EB%91%90%EB%B2%88%EC%A7%B8%EA%B0%92%EC%9D%84-%EA%B8%B0%EC%A4%80%EC%9C%BC%EB%A1%9C%EB%8F%84-%EC%A0%95%EB%A0%AC-%EA%B0%80%EB%8A%A5%ED%95%98%EB%8B%A4%EA%B1%B0

[C++] pair vector를 sort! 두번째값을 기준으로도 정렬 가능하다거!

← 요거 보면 이해 쌉가능!! pair함수를 이용해 sort를 변형하는 풀이.. 다음에 이용해보아야겠다.

 

 

---

+ 그리고 저 공스타그램 만들었어요...

많이 놀러와주세요...😀😀😀😀😀😀😀😀

https://www.instagram.com/study_human.c/