[이것이~] 탐욕법, 구현

참고: https://www.youtube.com/playlist?list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81

 

위의 동영상에 나오는 문제들을 직접 풀어보았다. 

 

Greedy Algorithm

문제1) 1이 될 때까지

#include <iostream>

using namespace std;

int main(void){
	
	int n, k, left, res, count, temp;
	cin >> n >> k;
	
	res = n;
	while(res>k){
		temp = res%k;
		if(temp!=0){
			res = res-temp;
			count = count + temp;
		}
		res = res/k;
		count++;
	}
	
	cout << count;
	
}

문제2) 더하기 혹은 곱하기

#include <iostream>

using namespace std;

int main(void){
	
	string str;
	cin >> str;
	
	int result = str[0]-'0';
	for(int i = 1; i<str.size(); i++){
		if (result <= 1 || str[i]-'0' <= 1){
			result = result + (str[i]-'0');
		}else{
			result = result * (str[i]-'0');
		}
	}
	
	cout << result;
}

 

구현(Implementation) (14강)

방향 벡터

동, 북, 서, 남

dx = {0, -1, 0, 1}

dy = {1, 0, -1, 0}

 

방향벡터를 정해놓고, 다음 위치를 이 벡터를 이용해서 움직이는 것이 훨씬 나음! ex) 체스 문제 등

 

문제1) 상하좌우 이동하기

#include <iostream>
#include <vector>

using namespace std;

int main(void){
	
	pair<int, int> point (1, 1);
	
	int num;
	string order;
	vector<char> v;

	cin >> num;
	cin.ignore();
	getline(cin, order);
	
	cout << order << endl;
	
	for(int i = 0; i<order.size();){
		v.push_back(order[i]);
		i= i+2;
	}
	
	
	int dx[4] = {0, 0, 1, -1};
	int dy[4] = {1, -1, 0, 0};
	
	for(vector<char>::iterator it = v.begin(); it!=v.end(); it++){
	
		cout << *it << endl;
	
		if(*it == 'R'){
			if(point.first+dx[0] > 0 && point.second+dy[0]>0 && point.first+dx[0]<=num && point.second+dy[0]<=num){
				point.first = point.first + dx[0];
				point.second = point.second + dy[0];
			}
		}else if(*it == 'L'){
			if(point.first+dx[1] > 0 && point.second+dy[1]>0 && point.first+dx[1]<=num && point.second+dy[1]<=num){
				point.first = point.first + dx[1];
				point.second = point.second + dy[1];
			}
		}else if(*it == 'D'){
			if(point.first+dx[2] >=0 && point.second+dy[2]>0 && point.first+dx[1]<=num && point.second+dy[1]<=num){
				point.first = point.first + dx[2];
				point.second = point.second + dy[2];
			}
		}else if(*it == 'U'){
			if(point.first+dx[3] > 0 && point.second+dy[3]>0 && point.first+dx[1]<=num && point.second+dy[1]<=num){
				point.first = point.first + dx[3];
				point.second = point.second + dy[3];
			}
		}
		cout << "moved to: (" << point.first << ", " << point.second << ") \n";
		
	}
	
}

 

* 영상과 내 코드 차이

1. 나는 띄어쓰기 제거를 위해 받은 스트링을 다시 vector에 문자만 넣어줬다. 영상에선 별도로 이런 코드는 안넣은 것 같다.

2. 일단 temporary한 좌표에 결과 넣어두고 범위 벗어나는지 확인하는데 난 if문 안에 때려박아서 매우 길어졌다.

3. 아예 방향키들을 하나의 array에 넣고 for문으로 비교해서 코드가 훨씬 심플해보인다.

 

역시 사람은 교육을 받아야... ^^