📚 구현
구현이란, 머릿속에 있는 알고리즘을 소스 코드로 바꾸는 과정
알고리즘 대회에서 구현문제란?
- 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제
- 피지컬을 요구하는 문제
예시
- 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
- 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
- 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
- 적절한 라이브러리를 찾아서 사용해야 하는 문제
- 완전탐색, 시뮬레이션 문제 등등
📚 예제
📕 상하좌우
여행가 A는 N X N 크기의 정사각형 공간 위에 서 있습니다. 이 공간은 1 X 1 크기의 정사각형으로 나누어져 있습니다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당합니다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)입니다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 게획서가 놓여 있습니다.
계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀 있습니다. 각 문자의 의미는 다음과 같습니다.
- L : 왼쪽으로 한 칸 이동
- R : 오른쪽으로 한 칸 이동
- U : 위로 한 칸 이동
- D : 아래로 한 칸 이동
이때 여행가 A가 N X N 크기의 정사각형 공간을 벗어나는 움직임은 무시됩니다. 예를 들어 (1, 1)의 위치에서 L 혹은 U를 만나면 무시됩니다.ㅏ 다음은 N = 5인 지도와 계획서입니다.
#include <iostream>
#include <string>
using namespace std;
int main()
{
int n;
int x = 1, y = 1;
int dx, dy;
string arr;
cin >> n;
cin.ignore();
getline(cin, arr);
for (int i = 0; i < arr.size(); i++)
{
dx = 0;
dy = 0;
if (arr[i] == 'R')
dx = 1;
else if (arr[i] == 'L')
dx = -1;
else if (arr[i] == 'U')
dy = -1;
else if (arr[i] == 'D')
dy = 1;
if (x + dx < 1 || y + dy < 1 || x + dx > n || y + dy > n)
{
dx = 0;
dy = 0;
}
x += dx;
y += dy;
}
cout << x << ' ' << y << endl;
return 0;
}이것저것 많이 배운 문제라고 생각이 든다 일단 다른문제를 풀때 보통 scanf를 이용하여서 입력을 받았는데 이 경우 스페이스를 입력 못한다 그래서 어떤식으로 구현을 해야하나 고민을 많이 하였는데 결국 생각이 닿지 않아서 책을 참조하였다.
여기서 알게된것이 getline 이다 getline을 이용하여 '\n' 까지 문자열을 받게되는데 전에 n을 한번 받을때 버퍼에 남아있는게 있어서 그걸 초기화시켜주는 ignore을 이용하였다.
그 이후 반복문을 돌면서 내가 원하는 문자가 나왔을때 좌표를 옮겨주는식으로 구성하였다.
하지만 이 문제는 조작 커맨드가 4개밖에 없는데 만약 개수가 늘어나면 책에 나와있는대로 배열형태로 이용하는게 좀 더 효율적이라고 생각이든다.
📘 시각
정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하세요.
단순 3중 반복문을 이용하여 구하였다 이 경우 완전탐색이라고 하는데 책에서는 탐색해야 할 전체 데이터의 개수가 100만 개 이하일 때 완전 탐색을 사용하면 적절하다고 한다.
#include <iostream>
using namespace std;
int main()
{
int N;
int count = 0;
cin >> N;
for (int i = 0; i <= N; i++)
{
for (int j = 0; j < 60; j++)
{
for (int k = 0; k < 60; k++)
{
if (k / 10 == 3 || k % 10 == 3)
count++;
else if (j / 10 == 3 || j % 10 == 3)
count++;
else if (i / 10 == 3 || i % 10 == 3)
count++;
}
}
}
cout << count << endl;
return 0;
}
📙 왕실의 나이트
- 행복 왕국의 왕실 정원은 체스판과 같은 8 X 8 좌표 평면입니다. 왕실 정원의 특정한 한 칸에 나이트가 서있습니다. 나이트는 매우 충성스러운 신하로서 매일 무술을 연마합니다.
- 나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없습니다.
- 나이트는 특정 위치에서 다음과 같은 2가지 경우로 이동할 수 있습니다.
- 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기
- 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기
나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오.
상하좌우 문제와 똑같은 문제이다 근데 아까와 같이 일일이 움직이는 모든 경우를 조건문으로 빼려니 개수가 많아져서 이번에는 책에서 추천한 방법대로 풀어봤다 확실히 배열을 정하고 그걸 돌리니 코드가 간결해졌다.
#include <iostream>
using namespace std;
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[] = {-1, -2, -2, -1, 1, 2, 2, 1};
int main()
{
int x, y, xx, yy, res = 0;
string po;
cin >> po;
x = po[0] - 96;
y = po[1] - 48;
for (int i = 0; i < 8; i++)
{
xx = x + dx[i];
yy = y + dy[i];
if (xx >= 1 && xx <= 8 && yy >= 1 && yy <= 8)
res++;
}
cout << res << endl;
return 0;
}📗 게임 개발
현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다 캐릭터가 있는 장소는 1 X 1크기의 정사각형으로 이뤄진 N X M 크기의 직사각형이다, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다.
- 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다.
- 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방항에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다.
- 만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.
실력부족... 머릿속에 어떤식으로 구현할지 고민해보았지만 도저히 모르겠어서 그냥 클론코딩을 했다
제일 중요한건 문제에서 주어진 변수들이 어떤식으로 동작하는지 확실하게 알아야한다 그리고 방향을 설정하는데 있어서 dx, dy라는 별도의 리스트를 만들어서 방향을 정하는게 효과적이다 그리고 2차원배열을 만들때 전체맵과 방문한맵 두가지 배열을 만들어서 그 값들을 저장하며 풀이하면 된다.
#include <iostream>
using namespace std;
int map[50][50]; // 방문한 위치를 남겨두는 배열
int arr[50][50]; // 전체 맵 정보
int N, M, x, y, d; //맵 크기, 현재 좌표, 방향
//북동남서 방향 정의
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
//왼쪽으로 회전
void ft_left()
{
d--;
if (d == -1)
d = 3;
}
int main()
{
cin >> N >> M;
cin >> x >> y >> d;
map[x][y] = 1;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
int cnt;
cin >> cnt;
arr[i][j] = cnt;
}
}
int cnt = 1;
int turn_time = 0;
while (true)
{
ft_left();
int nx = x + dx[d];
int ny = y + dy[d];
// 회전하고 정면에 가보지 않은 칸이 존재하면 이동
if (map[nx][ny] == 0 && arr[nx][ny] == 0)
{
map[nx][ny] = 1;
x = nx;
y = ny;
cnt += 1;
turn_time = 0;
}
// 회전한 이후 정면에 가보지 않은 칸이 없가나 바다인 경우
else
turn_time += 1;
// 네 방향 모두 갈 수 없는 경우
if (turn_time == 4)
{
nx = x - dx[d];
ny = y - dy[d];
// 뒤로 갈 수 있다면 이동
if (arr[nx][ny] == 0)
{
x = nx;
y = ny;
}
// 뒤가 바다로 막혀있는 경우
else
break;
turn_time = 0;
}
}
cout << cnt << endl;
}➕ 2503 숫자야구
영수와 민혁이가 숫자야구를 한다
현재 민혁이와 영수는 게임을 하고 있는 도중에 있다. 민혁이가 영수에게 어떤 수들을 물어보았는지, 그리고 각각의 물음에 영수가 어떤 대답을 했는지가 입력으로 주어진다. 이 입력을 바탕으로 여러분은 영수가 생각하고 있을 가능성이 있는 수가 총 몇 개인지를 알아맞혀야 한다.
- 민혁: 123
- 영수: 1 스트라이크 1 볼
- 민혁: 356
- 영수: 1 스트라이크 0 볼
- 민혁: 327
- 영수: 2 스트라이크 0 볼
- 민혁: 489
- 영수: 0 스트라이크 1 볼
이때 가능한 답은 324와 328, 이렇게 두 가지이다.
영수는 동아리의 규율을 잘 따르는 착한 아이라 민혁이의 물음에 곧이곧대로 정직하게 답한다. 그러므로 영수의 답들에는 모순이 없다.
민혁이의 물음들과 각각의 물음에 대한 영수의 답이 입력으로 주어질 때 영수가 생각하고 있을 가능성이 있는 답의 총 개수를 출력하는 프로그램을 작성하시오.
