뚝딱뚝딱

그리디 알고리즘의 대표적인 예시 중 하나인 동전 문제를 풀어보자.

다음과 같은 절차로 해결할 수 있다.

1. 선택 절차 : 거스름돈 문제에서 가장 가치가 큰 동전부터 선택 한다.
2. 적절성 검사 : 만약 선택된 동전의 가치가 거스름돈보다 크다면 다음으로 작은 동전을 선택한다.
3. 해답 검사 : 합이 일치하면 거스름돈 문제가 해결된 것이다.

+여기에 부가적인 절차는 주석으로 작성하였다.

#include<iostream>

using namespace std;

int main() {
	int N, K;
	cin >> N >> K;

	int *a = new int[N];

	for (int i = 0; i < N; i++) {
		cin >> a[i];
	}

	int cnt = 0; //동전의 개수를 저장할 것이다

	for (int i = N - 1; i >= 0; i--) {//문제에서 동전의 가치를 오름차순으로 저장했으므로,뒤에서부터 비교한다
		if (a[i] <= K) {//입력받은 가치보다 작은 것중 가장 큰 걸 선택
			cnt += (K / a[i]);//큰 가치로 몇번 나누어질 수 있는지를 구하고 더한다
			K = K % a[i];//그 나머지를 K로 갱신한다
		}
	}

	cout << cnt;//최종 cnt를 출력한다
}

문제에서 예시로 주어진 접근 순서를 보고, 가장 멀리 있는 집부터 접근해야 한다는 건 다 캐치했을 것이다.

그런데 cap만큼 감소시키는 것을 불규칙한 vector 값에 바로 접근해서 푸는 건 복잡할 것 같았다.

집의 번수 = 물류창고로부터의 거리이고, 거리에 대한 정보도, 각 거리에 있는 집에 두어야 할/ 수거해야 할 택배 개수에 대한 정보도 동시에 가질 수 있는 방법이 무엇이 있을까 생각하다 보니.. 스택이 생각났다.

내가 접근한 방법은 delieveries와 pickups에서 0이 아닌 값을 갖는 인덱스+1(거리는 1부터니까)를 각 택배 개수만큼 스택에 차례로 넣는것이다. 그럼 스택은 뒤에서부터 빼니까, 우리가 원하는 대로 가장 멀리있는 집의 택배를 이용할 수 있게 된다.

두 스택에서 cap만큼씩 삭제하고, 이때 각각의 스택에서 맨 처음 삭제한 값이 가장 멀리까지 가는 거리가 되므로, top1과 top2에 저장해 둔다. 이때 주의할 점은 스택이 비어있지 않은 경우에만 삭제 해야 한다는 점이다.

한번 순회하고 갔다올 때 top1과 top2 중 더 큰 값에 따라서 갔다와야 한번에 해결할 수 있기 때문에 더 큰 값의 2배 만큼을 answer에 더해주면 된다!

c++ 코드는 아래와 같다.

#include <string>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
	long long answer = 0;
	
	stack<int> st1, st2;

	for (int i = 0; i < n; i++) {//스택에 다 넣어준다
		for (int j = 0; j < deliveries[i]; j++) {
			st1.push(i + 1);
		}
		for (int k = 0; k < pickups[i]; k++) {
			st2.push(i + 1);
		}
	}

	int top1, top2;

	while (!st1.empty() || !st2.empty()) {//둘다 스택이 비워지면 그만
		top1 = top2 = 0;
        for (int i = 0; i < cap; i++) {
			if (!st1.empty()) {
				if (i == 0) {
					top1 = st1.top();
				}
				st1.pop();
			}

			if (!st2.empty()) {
				if (i == 0) {
					top2 = st2.top();
				}
				st2.pop();
			}
		}
		answer += max(top1, top2) * 2;
		
	}
	
	return answer;
}

요격 시스템

요격 시스템 문제는 먼저 sorting을 해주어야 한다.

이 때 어느 값을 기준으로 정렬할 것인지가 관건이 되는데..

주어진 예제에서 어떤 폭격 미사일 하나의 구간만을 고려한다고 해보자.

 예를 들면 4-5 구간의 미사일만을 고려해 보자.

4를 요격 범위의 start로 S, 5를 요격 범위의 end로 E라고 표현하고, 현재의 요격 범위로 두자.

end가 4(현재의 S)보다 작은 미사일의 경우, 현재의 요격 범위에 포함될 수 없다.

따라서 start가 5(현재의 E)보다 큰 미사일의 경우에도 현재의 요격 범위에 포함될 수 없다.

그러므로 요격 범위에 들어올 자격이 되는지는, 각 미사일 구간의 end 포인트 지점에 달려있다.

따라서 end를 기준으로 오름차순 정렬해준다.

end를 기준으로 오름차순 정렬해주면

[4,5],[4,8],[10,14],[11,13],[5,12],[3,7],[1,4] → [1,4], [4,5], [3,7], [4,8], [5,12], [11,13], [10,14]
이 된다.

미사일을 어차피 한번이상 쏘게 되어 있으니까, count는 1로 시작한다.

처음 요격 구간을 [1,4]로 설정하고 그 다음 구간부터 차례로 순회한다.

첫 S=1, E=4가 된다.

다음 미사일의 범위가 [4,5]이고, 이것의 시작 지점인 4가 현재 요격 구간의 E보다 작아야 한번에 쏠 수 있다.
(엔드 포인트인 4에서는 쏘지 못한다. 조건에 명시되어 있다.)

그런데 E보다 작지 않기 때문에 이 구간에는 첫번째 미사일 구간 빼고는 더이상 요격할 미사일이 없는 것이다.

따라서 count를 1올려주고, 다음 미사일 구간의 시작점을 s로, 끝점을 e로 하여 새로운 요격 범위를 갱신하고 위 과정을 반복하도록 한다.

그럼 최종 요격 발사 횟수를 COUNT를 반환함으로써 얻을 수 있다.

C++로 해결한 코드는 아래와 같다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool cmp(vector<int> &v1, vector<int> &v2) {
	if (v1[1] == v2[1])
		return v1[0] < v2[0];
	else return v1[1] < v2[1];
}

int solution(vector<vector<int>> targets) {
	
	int answer = 0;

	sort(targets.begin(), targets.end(), cmp);

	int e = targets[0][1];

	answer++;

	for (int i = 1; i < targets.size(); i++) {
		if (targets[i][0] < e) {
			continue;
		}
		else {
			answer++;
			e = targets[i][1];
		}

	}

	return answer;
}

대충 만든 자판

이제는 익숙해진 문자열과 숫자 한번에 다루기!

문제를 몇번 풀어보니, 이 문제 역시 문자열과 숫자 개념이 더해진 것임을 바로 파악할 수 있었고, map을 사용하여 쉽게 해결할 수 있었다.

자판의 등장하는 문자를 char형태의 index로 보고, 어떤 위치의 버튼이든 최소한으로 눌렀을 때를 그 알파벳의 버튼 횟수로 저장하도록 하였다.

그러니까 keymap을 순회하면서, 등장하는 문자를 map의 인덱스로 넣고, 해당 위치를 저장하였다.

그리고 같은 문자가 또 한번 등장할 때마다 기존에 저장해 두었던 위치와 비교해보아서 더 작은 위치로 갱신되도록 하였다.

이렇게 하여 문자당 최소 터치 수를 map에 저장해 두면 80 프로는 다 한 것이다!!

이제 targets을 순회하면서 해당 문자의 최소 터치 수가 저장된 map에서 값을 가져와 count시키고, 

만약 해당 문자가 map에 존재하지 않는다면, 작성할 수 없는 문자열이므로, 문제에서 요구한 것처럼 count를 -1로 하고, 해당 문자열은 넘어가도록 코드를 구현했다.

그리고 한 문자열씩 돌때마다 answer벡터에 count값을 push해주면 끝!

코드는 아래와 같다.

#include <string>
#include <vector>
#include <map>

using namespace std;

vector<int> solution(vector<string> keymap, vector<string> targets) {
    vector<int> answer;
    
    map<char, int> m1;

	for (int i = 0; i < keymap.size(); i++) {
		for (int j = 0; j < keymap[i].size(); j++) {
			if (m1.find(keymap[i][j]) == m1.end()) {//map에 존재하지 않은 문자면 입력
				m1.insert(pair<char, int>(keymap[i][j], j+1));
			}
			else {
				if (m1[keymap[i][j]] > j + 1) {
					m1[keymap[i][j]] = j + 1;//더작은 값으로 바꾼다
				}
			}
		}
	}

	int cnt;

	for (int i = 0; i < targets.size(); i++) {
		cnt = 0;
		for (int j = 0; j < targets[i].size(); j++) {
			if (m1.find(targets[i][j]) == m1.end()) {
				cnt = -1;
				break;
			}
			auto temp = targets[i][j];
			cnt += m1[temp];
		}
		answer.push_back(cnt);
	}

    
    return answer;
}

n칸의 벽 중 덧칠해야 할 칸 번호가 적힌 벡터를 참고하여, 한번에 m칸 칠할 수 있는 페인트 롤러를 이용해 최소의 페인트칠 횟수 구하는 문제.

문제의 조건을 보면 section 벡터의 크기가 무조건 1이상이므로, 최소 한번은 칠해야 한다는 점을 기억하자.

section[0]에서 시작해서 한번 칠할 때 section[0]+m-1번 칸 까지는 칠해진다.

그리고 한번 칠했으므로, 칠한 횟수(answer)를 1 증가시켜준다.

temp에 section[0]+m에 대한 값을 저장해두고, for문을 통해 section[1]부터 section의 크기만큼 순회한다.

그래서, 다음 칠해야 할 칸이, 이전에 한번 칠했던 범위에 포함이 되는지를 살펴보고, 포함이 된다면 현재 회차는 넘어가도록 한다.이는 현재 section[i]의 값이 temp보다 작은지를 보면 된다.

만약 현재 section[i]의 값이 temp와 같거나 더 크다면 이전에 칠했을 때, 같이 칠해지지 못한 것이므로, temp를 다시 section[i]+m으로 갱신해주고, 이를 기준으로 한번 더 칠하는 것이므로 answer를 1 증가 시킨다.

위 과정을 모든 section벡터 값에 대해 순회해주면 최소 페인트 칠 횟수를 반환할 수 있다! 

코드는 아래와 같다.

#include <string>
#include <vector>

using namespace std;

int solution(int n, int m, vector<int> section) {
    int answer = 0;
    
    int temp = section[0] + m;
	answer++;
	
	for (int i = 1; i < section.size(); i++) {
		if (section[i] < temp) {//한번 칠한것에 같이 포함이 되면
			continue;//넘어간다
		}
		else {
			temp = section[i] + m;
			answer++;
		}
	}
    
    return answer;
}

이 문제는 배열의 유효범위를 이해하고, 입력으로 받은 문자열에서 한 글자씩 접근하여 장애물(X)이면 해당 이동을 진행하지 않고, 장애물이 아니면 이동을 진행하도록 하는 쉬운 문제였다.

로직을 이해하고 짜는데에는 금방이었는데, 3가지 케이스를 제외하고 모두 실패가 떠서 왜 그런가.. 테스트 케이스 결과를 보니, 처음 start 위치를 찾고 난 후부터는 전혀 이동하지 못하고 그대로 반환되는 것을 확인할 수 있었다.

원인은 너무 단순한 거였는데, string에서 이동 칸 수를 char로 읽어와서 int로 변경하는 과정에, ASCII 형식을 고려하지 않은 채로 static_case를 씌워 단순히 <int>로 형변환 하려고 해서 정확한 숫자값을 읽어오지 못한 것이었따...

char타입을 레퍼런스로 가져와서 const char 포인터에 저장해 준 후 char->int로 바꾸어주는 atoi함수를 통해 쉽게 해결하였다!!

const char *jump_char = &routes[i][2];
		int jump = atoi(jump_char);

전체 코드는 아래와 같다.

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<string> park, vector<string> routes) {
	vector<int> answer;

	int start_row = 0;
	int start_col = 0;

	bool isbreak = false;

	for (int i = 0; i < park.size(); i++) {//행길이
		for (int j = 0; j < park[i].size(); j++) {//열길이
			if (park[i][j] == 'S') {
				start_row = i;
				start_col = j;
				isbreak = true;
				break;
			}
		}
		if (isbreak) break;
	}

	for (int i = 0; i < routes.size(); i++) {
		const char *jump_char = &routes[i][2];
		int jump = atoi(jump_char);//char를 읽어와 숫자로 변환하는 과정에서 오류가 발생했음. 이렇게 수정하니 해결됨
		switch (routes[i][0])
		{
		case 'N':
			if (start_row - jump >= 0){
				bool flag = false;
				for (int j = 1; j <= jump; j++) {
					if (park[start_row - j][start_col] == 'X') {
						flag = true;
						break;
					}
				}
				if (!flag) {
					start_row -= jump;
				}
			}
			break;
			
		case 'S':
			if (start_row + jump < park.size()) {
				bool flag = false;
				for (int j = 1; j <= jump; j++) {
					if (park[start_row + j][start_col] == 'X') {
						flag = true;
						break;
					}
				}
				if (!flag) {
					start_row += jump;
				}
			}
			break;

		case 'W':
			if (start_col - jump >= 0) {
				bool flag = false;
				for (int j = 1; j <= jump; j++) {
					if (park[start_row][start_col-j] == 'X') {
						flag = true;
						break;
					}
				}
				if (!flag) {
					start_col -= jump;
				}
			}
			break;

		case 'E':
			if (start_col + jump < park[0].size()) {
				bool flag = false;
				for (int j = 1; j <= jump; j++) {
					if (park[start_row][start_col + j] == 'X') {
						flag = true;
						break;
					}
				}
				if (!flag) {
					start_col += jump;
				}
			}
			break;

		default:
			break;
		}
	}

	answer.push_back(start_row);
	answer.push_back(start_col);

	return answer;
}