Madison Digital Garden

Search

SearchSearch

5. 해시, 힙 (충남대 알고리즘 강의록)

Oct 13, 2021, 6 min read

충남대학교 컴퓨터공학과 이영석 교수님의 "알고리즘" 강의 실습 내용입니다.

  • 실습 문제들의 코드 위주로 구성되어 있습니다.

문제 1: 완주하지 못한 참가자

프로그래머스 문제 변형 

#include <iostream>
#include <string>
#include <sstream>
#include <unordered_map>
 
using namespace std;
 
int main() {
	string participant, completion, temp;
	getline(cin, participant);
	getline(cin, completion);
	stringstream sp(participant), sc(completion);
	unordered_map<string, int> /* {이름: 명수} */ m;
 
	// 완료한 사람들을 한명씩 hashmap에 추가하고 이미 추가되어 있으면 명수를 1 증가시킨다.
	while(getline(sc, temp, ' ')) { m[temp]++; }
	// 참여한 사람들을 한명씩 hashmap에서 탐색한다.
	while(getline(sp, temp, ' ')) {
		// 만약 명수가 1보다 크거나 같으면 1을 감소시킨다.
		if(m[temp] > 0) {
			m[temp]--;
 
		// 만약 명수가 1보다 작으면 완료한 참가자가 아니므로 화면에 그의 이름을 출력한다.
		} else {
			cout << temp << ' ';
		}
	}
	cout << '\n';
	return 0;
}

문제 2: 라면 공장

프로그래머스 문제 변형 

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int main() {
	int stock, k, dlen, slen, temp, nextImp = 0, impCnt = 0;
	cin >> stock >> k >> dlen >> slen;
	vector<int> dates, supls;
	for(int i = 0; i < dlen; i++) {
		cin >> temp;
		dates.push_back(temp);
	}
	for(int i = 0; i < slen; i++) {
		cin >> temp;
		supls.push_back(temp);
	}
 
	priority_queue<int> pq;
	// 재고를 나타내는 stock이 목표일수인 k보다 크거나 같으면 목표일수를 현재의 재고로 버틸 수 있으므로 stock이 k보다 작은 동안 while문이 실행된다.
	while(k > stock) {
		// nextImp은 현재의 재고로 버틸 수 없는 기간에 대한 첫번째 수입 일정을 가리키는 인덱스이다.
		//	 하지만 수입 이후에는 해당 일자까지 버틸 수 있으므로 수입 이후에는 for문을 이용해 다시 버틸 수 없는 첫번째 수입 일정까지 nextImp를 옮겨준다.
		//	 for문의 i 값의 초깃값으로 nextImp를 주어 수입 이전에는 버틸 수 없었지만 수입하고 나서는 버틸 수 있는 첫번째 수입 일자부터 순회하게 한다.
		for(int i = nextImp; i < dlen; i++) {
			// 만약 수입 일정까지 현재의 재고로 버틸 수 있을 때
			if(dates[i] <= stock) {
				// 해당 수입 일정에 예정된 수입양을 우선순위 큐에 넣어준다.
				pq.push(supls[i]);
				// nextImp를 1 올려준다.
				nextImp++;
 
			// 만약 수입 일정까지 현재의 재고로 버틸 수 없을 때
			} else {
				break;
			}
		}
		// 현재의 재고로 버틸 수 있는 일자까지의 수입 일정 중에 가장 많이 수입할 수 있는 양을 수입한다.
		stock += pq.top();
		pq.pop();
		// 수입 횟수를 1 증가시킨다.
		impCnt++;
	}
 
	cout << impCnt << endl;
 
	return 0;
}

문제 3: 소행성 충돌시키기

#include <iostream>
#include <string>
#include <sstream>
#include <queue>
 
using namespace std;
 
int main() {
	string strIn, temp;
	getline(cin, strIn);
	stringstream ss(strIn);
	priority_queue<int> pq;
	// 소행성의 무게를 우선순위 큐에 넣어 항상 소행성의 가장 무거운 무게가 top에 위치하도록 한다.
	while(getline(ss, temp, ' ')) { pq.push(stoi(temp)); }
	// 우선순위 큐의 크기가 1보다 커 충돌시킬 수 있는 소행성이 항상 존재할때 while문이 실행된다.
	while(pq.size() > 1) {
		// 제일 무게가 많이 나가는 소행성을 꺼낸다.
		int head = pq.top();
		pq.pop();
 
		// 두번째로 무게가 많이 나가는 소행성을 꺼낸다.
		int next = pq.top();
		pq.pop();
 
		// 충돌해서 잔해가 남는 경우에는 잔해의 무게를 다시 우선순위 큐에 넣어준다.
		if(head > next) {
			pq.push(head - next);
		}
	}
 
	// 소행성이 모두 사라진 경우에는 0을 출력한다.
	if(pq.size() == 0) {
		cout << 0 << endl;
 
	// 소행성이 하나 남은 경우에는 해당 소행성의 무게를 출력한다.
	} else {
		cout << pq.top() << endl;
	}
 
	return 0;
}

Graph View

Backlinks