04: 구현

개요

구현 유형의 문제란 풀이를 떠올리는 것은 쉽지만 소스 코드로 옮기기 어려운 문제.

주로 간단한 알고리즘이지만 지나치게 긴 코드, 실수 연산, 특정 소수점 자리 출력, 문자열을 특정 기준에 따라 처리, 적절한 라이브러리를 찾아서 사용하는 문제가 예시이다.

일반적으로 알고리즘 문제에서의 2차원 공간은 행렬의 의미.

시뮬레이션 및 완전 탐색 문제에서는 방향 벡터가 자주 활용.

 

 

문제 1. 상하좌우

 

• 여행가 A는 N * N 크기의 정사각형 공간 위에 서있다. 이공간은 1 * 1 크기의 정사각형으로 나누어져 있다.
  가장 왼쪽 위 좌표는 (1, 1)이며 가장 오른 쪽 아래 좌표는 (N, N)에 해당한다. 여행가 A는 상, 하 ,좌 ,우 방향으로 이동할 수 있으며
  시작좌표는 항상(1, 1)이다. 우리앞에는 여행가가 A가 이동할 계획서가 놓여있다.
• 계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D중 하나의 문자가 반복적으로 적혀 있다. 각 문자의 의미는
  다음과 같다.
  
  L : 왼쪽으로 한 칸 이동
  R : 오른쪽으로 한 칸 이동
  U : 위로 한 칸 이동
  D : 아래로 한 칸 이동
• 이때 여행가 A가 N × N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다
  예를 들어 (1, 1)의 위치에서 L 혹은 U를 만나면 무시된다
  다음은 N = 5인 지도와 계획이다

 

내 풀이

#include <iostream>
#include <string>

using namespace std;

int main() 
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	string s;
	cin >> n;
	cin >> s;

	int x=1, y=1;
	int l = s.length();
	for (int i = 0; i < l; i++) {
		switch (s[i]) {
		case 'L':
			if (x > 1)
				x--;
			break;
		case 'R':
			if (x < n)
				x++;
			break;
		case 'U':
			if (y > 1)
				y--;
			break;
		case 'D':
			if (y < n)
				y++;
			break;
		}
	}

	cout << x << " " << y << "\n";
}

 

 

아이디어 및 풀이

요구사항대로 충실히 구현하면 된다.

일련의 명령에 따라 개체를 차례대로 이동시킨다는 점에서 시뮬레이션 유형으로 분류되기도 하나, 구현이 중요한 대표적인 문제 유형이다.

#include <iostream>
#include <string>

using namespace std;

int n;
string plans;
int x = 1, y = 1;

int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
char moveTypes[4] = { 'L', 'R', 'U', 'D' };

int main() 
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	getline(cin, plans);
	
	for (int i = 0; i < plans.size(); i++) {
		char plan = plans[i];
		int nx = -1, ny = -1;
		for (int j = 0; j < 4; j++) {
			if (plan == moveTypes[j]) {
				nx = x + dx[j];
				ny = y + dy[j];
			}
		}
		if (nx < 1 || ny < 1 || nx > n || ny > n) continue;
		x = nx;
		y = ny;
	}

}

 

피드백

방향 벡터 이용

 

 

문제 2. 시각

• 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는
  모든 경우의 수를 구하는 프로그램을 작성하세요. 예를 들어 1을 입력했을 때
  다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각입니다.
  • 00시 00분 03초
  • 00시 13분 30초
• 반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각입니다.
  • 00시 02분 55초
  • 01시 27분 45초

 

아이디어 및 풀이

하루는 24*60*60=86400초이므로, 모든 시각의 경우를 하나씩 세서 풀 수 있는 문제이다.

이러한 유형은 Brute Forcing 문제 유형이라고 불린다.

#include <iostream>
#include <string>

using namespace std;

int n;
int main() 
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	string s;

	int cur = 0, result = 0;

	for (int hour = 0; hour <= n; ++hour) {
		for (int min = 0; min < 60; ++min) {
			for (int sec = 0; sec < 60; ++sec) {
				if (hour % 10 == 3 || hour / 10 == 3 
					|| min % 10 == 3 || min / 10 == 3 
					|| sec % 10 == 3 || sec / 10 == 3) {
					result++;
				}
			}
		}
	}
	cout << result << "\n";
}

 

 

문제 3. 왕실의 나이트

행복 왕국의 왕실 정원은 체스판과 같은 8 x 8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서 있다. 나이트는 매우 충성스러운 신하로서 매일 무술을 연마한다.

 

나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다. 나이트는 특정한 위치에서 다음과 같은 2가지 경우로 이동할 수 있다.

• 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기
• 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기

 

이처럼 8 x 8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오. 이때 왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하며, 열 위치는 a부터 h로 표현한다.

 

예를 들어 만약 나이트가 a1에 있을 때 이동할 수 있는 경우의 수는 다음 2가지 이다. a1의 위치는 좌표평면에서 구석의 위치에 해당하며 나이트는 정원의 밖으로는 나갈 수 없기 때문이다.

1. 오른쪽으로 두 칸 이동 후 아래로 한 칸 이동하기(c2)
2. 아래로 두 칸 이동 후 오른쪽으로 한 칸 이동하기(b3)

또 다른 예로 나이트가 c2에 위치해 있다면 나이트가 이동할 수 있는 경우의 수는 6가지이다.

 

입력 조건

• 첫째 줄에 8 x 8 좌표 평면상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두 문자로 구성된 문자열이 입력된다. 입력 문자는 a1처럼 열과 행으로 이뤄진다.

 

출력 조건

• 첫째 줄에 나이트가 이동할 수 있는 경우의 수를 출력하시오.

 

입력 예시

a1

 

출력 예시

2

 

내 풀이

#include <iostream>
#include <string>

using namespace std;

struct t {
	int x;
	int y;
};

t moveTypes[8] = { {-1, -2},
	{1, -2},
	{-1, 2},
	{1, 2},
	{-2, -1},
	{2, -1},
	{-2, 1},
	{2, 1}
};

int main() 
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	string s;

	cin >> s;

	t pt;
	pt.x = s[0] - 96;
	pt.y = s[1] - 48;

	int cnt = 0;

	// char a는 97
	for (int i = 0; i < 8; i++) {
		if ((pt.x + moveTypes[i].x >= 1 && pt.x + moveTypes[i].x <= 8) &&
			(pt.y + moveTypes[i].y >= 1 && pt.y + moveTypes[i].y <= 8)) {
			cnt++;
		}
	}
	cout << cnt << "\n";
}

 

아이디어 및 풀이

나이트의 8가지 방향에 대한 방향 벡터를 정의한다. (간결한 코드 작성 위함)

using namespace std;

string input;
int dx[] = { -2, -1, 1, 2, 2, 1, -1, -2 };
int dy[] = { -1, -2, -2, -1, 1, 2, 2, 1 };

int main() 
{
	cin >> input;
	int row = input[1] - '0';
	int col = input[0] - 'a' + 1;

	int result = 0;
	for (int i = 0; i < 8; i++) {
		int nextRow = row + dx[i];
		int nextCol = col + dy[i];
		if (nextRow >= 1 && nextRow <= 8
			&& nextCol >= 1 && nextCol <= 8) {
			result++;
		}
	}
	cout << result << "\n";
}

 

 

문제 4. 문자열 재정렬

• 알파벳 대문자와 숫자(0~9)로만 구성된 문자열이 입력으로 주어집니다. 이때 모든 알파벳을 오른차순으로 정렬하여 이어서 출력한 뒤에, 그 뒤에 모든 숫자를 더한 값을 이어서 출력합니다.
• 예를 들어 K1KA5CB7이라는 값이 들어오면 ABCKK13을 출력합니다.

 

내 코드

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

using namespace std;

int main() 
{
	string s;
	cin >> s;
	
	int num = 0;
	vector<char> v;
	for (int i = 0; i < s.length(); i++) {
		if (s[i] <= '9') {
			num += (s[i] - '0');
		}
		if (s[i] > '9') {
			v.push_back(s[i]);
		}
	}

	sort(v.begin(), v.end());
	
	for (int i = 0; i < v.size(); i++) {
		cout << v[i];
	}
	cout << num << "\n";
}

 

 

아이디어 및 풀이

"구현" 문제이기 때문에 요구사항대로 충실히 구현하면 정답이다.

별도의 변수로 숫자, 알파벳을 저장한다.

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

using namespace std;

int main() 
{
	string s;
	cin >> s;

	vector<char> result;
	int value = 0;

	for (int i = 0; i < s.size(); i++) {
		if (isalpha(s[i])) {
			result.push_back(s[i]);
		}
		else {
			value += s[i] - '0';
		}
	}

	sort(result.begin(), result.end());

	for (int i = 0; i < result.size(); i++) {
		cout << result[i];
	}
	if (value != 0)
		cout << value;
	cout << "\n";
}

 

 

피드백

숫자가 존재하지 않는 경우도 생각해서 짰어야..