본 게시글은 유튜버 [ 동빈나 ] 님의 유튜브 영상과 git hub 페이지, ' 이것이 코딩 테스트다 ' 교재 를 공부하고 정리한 글 입니다.
예제 문제
[ #1 상하 좌우 ] / [ #2 시각 ]
==========================================================================
예제 문제 | 실전 문제 | 기출 문제
#1 [ 상하 좌우 ]
시간 제한 : 1초 메모리 제한 : 128 MB
여행가 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를 만나면 무시된다.
계획서가 주어졌을 떄 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오.
입력 조건 : 첫째 줄에 공간의 크기를 나타내는 N이 주어진다. ( 1 <= N <= 100 )
둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다. ( 1 <= 이동횟수 <= 100 )
출력 조건 : 첫째 줄에 여행가 A가 최정적으로 도착할 지점의 좌표 ( X ,Y ) 를 공백으로 구분하여 출력하시오.
입력 예시 : 5
R R R U D D
출력 예시 : 3 4
▼ 정답 코드 보기
#include <iostream> #include <vector> #include <algorithm> #include <string> using std::cout; using std::cin; using std::vector; using std::string; int n; string order; int pos_x =1, pos_y=1; // L R U D int dx[] = { 0,0,-1,1 }; int dy[] = { -1,1,0,0 }; char move[] = { 'L','R','U','D' }; int main() { std::ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n; cin.ignore(); getline(cin, order); for (int j = 0; j < order.length();j++) { char ord = order[j]; for (int i = 0; i < 4; i++) { if (ord == move[i]) { pos_x += dx[i]; pos_y += dy[i]; if (pos_x < 1 || pos_x > n || pos_y < 1 || pos_y >n) { // 그래프 범위 밖 일때 pos_x -= dx[i]; // 다시 되돌리기 pos_y -= dy[i]; // 다시 되돌리기 } break; } } } cout << pos_x << " " << pos_y; return 0; }
예제 문제 | 실전 문제 | 기출 문제
#2 [ 시각 ]
시간 제한 : 2초 메모리 제한 : 128 MB
정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 경우 모든 경의 수를 출력하는 프로그램을 작성하시오.
예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다.
* 00시 00분 03초
* 00시 13분 30초
반면에 다음은 3이 하나라도 포함되어 있지 않으므로 세면 안 되는 시각이다.
* 00시 02분 55초
* 01시 27분 45초
입력 조건 : 첫째 줄에 정수 N이 입력된다. ( 0 <= N <= 23 )
출력 조건 : 00시 00분 00초부터 N시 59분 59초까지의 시각 중에서 3이 하나라도 포함되는 모든 경우의수를 출력.
입력 예시 : 5
출력 예시 : 11475
▼ 정답 코드 보기
#include <iostream> #include <vector> #include <algorithm> #include <string> using std::cout; using std::cin; using std::vector; using std::string; int n, answer; int main() { std::ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n; for (int h = 0; h <= n; h++) { for (int m = 0; m < 60; m++) { for (int s = 0; s< 60; s++) { // 1의 자리가 3이거나 10의 자리가 3이면 3이 포함된거다. if (h % 10 == 3 || m % 10 == 3 || m / 10 == 3 || s % 10 == 3 || s / 10 == 3) answer++; } } } cout << answer; return 0; }
[ 실전 문제 ]
[#1 왕실의 나이트] / [#2 게임 개발]
==========================================================================
예제 문제 | 실전 문제 | 기출 문제
#1 [ 왕실의 나이트 ]
시간 제한 : 2초 메모리 제한 : 128 MB
행복 왕국의 왕실 정원은 체스판과 같은 8 × 8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서있다.
나이트는 매우 충성스러운 신하로서 매일 무술을 연마한다.
나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다
나이트는 특정 위치에서 다음과 같은 2가지 경우로 이동할 수 있다.
1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기
2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기
프로그램을 작성하라.
예를 들어 만약 나이트가 a1에 있을 때 이동할 수 있는 경우의 수는 다음 2가지이다. a1의 위치는 좌표 평면에서 구석의 위치에 해당하며 나이트는 정원으 밖으로는 나갈 수 없기 때문이다.
1. 오른쪽으로 두 칸 이동 후 아래로 한 칸 이동하기 ( c2 )
2. 아래로 두 칸 이동 후 오른쪽으로 한 칸 이동하기 ( b3 )
입력 조건 : 첫째 줄에 8x8 좌표 평면상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두 문자로 구성된 문자열이 입력된다. 입력 문자는 a1 처럼 열과 행으로 이뤄진다.
출력 조건 : 첫째 줄에 나이트가 이동할 수 있는 경우의 수를 출력하시오.
입력 예시 : a1
출력 예시 : 2
▼ 정답 코드 보기
#include <iostream> #include <vector> #include <string> using std::cout; using std::cin; using std::vector; using std::string; string pos; int dx[] = { -1,-2,-2,-1,1,2,2,1 }; // 시계 방향 int dy[] = { -2,-1,1,2,2,1,-1,-2 }; int cnt; int main() { std::ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); // 1. string 변수 pos에 입력을 받는다. cin >> pos; // 2. x,y 좌표를 int 형으로 저장한다. int x = pos[1] - '0'; int y = (pos[0] - 'a') + 1; // 3. 현재 x,y에서 가능한 모든 경우의 수(8가지)를 전부 확인하고 그래프를 안 쪽에 있다면 cnt++ for (int i = 0; i < 8; i++) { int temp_x = x + dx[i]; int temp_y = y + dy[i]; if (temp_x >= 1 && temp_x <= 8 && temp_y >= 1 && temp_y <= 8) { cnt++; } } cout << cnt; return 0; }
예제 문제 | 실전 문제 | 기출 문제
#2 [ 게임 개발 ]
시간 제한 : 2초 메모리 제한 : 128 MB
현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 X 1 크기의 정사각형으로 이뤄진 N X M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다.
맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다.
캐릭터의 움직임을 설정하기 위해 정해 놓은 매뉴얼은 이러하다.
1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다.
2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 횐전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다.
3. 만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.
현민이는 위 과정을 반복적으로 수행하면서 캐릭터의 움직임에 이상이 있는지 테스트하려고 한다. 메뉴얼에 따라 캐릭터를 이동시킨 뒤에, 캐릭터가 방문한 칸의 수를 출력하는 프로그램을 만드시오.
입력 조건 :
첫째 줄에 맵의 세로 크기 N과 가로 크기 M을 공백으로 구분하여 입력한다.(3 <= N, M <= 50)
둘째 줄에 게임 캐릭터가 있는 칸의 좌표 (A, B)와 바라보는 방햔 d가 각각 서로 공백으로 구분하여 주어진다.
방향 d의 값으로는 다음과 같이 4가지가 존재한다.
0 : 북쪽
1 : 동쪽
2 : 남쪽
3 : 서쪽
셋째 줄부터 맵이 육지인지 바다인지에 대한 정보가 주어진다.
N개의 줄에 맵의 상태가 북쪽부터 남쪽 순서대로, 각 줄의 데이터는 서쪽부터 동쪽 순서대로 주어진다. 맵의 외각은 항상 바다로 되어 있다.
0 : 육지
1 : 바다
처음에 게임 캐릭터가 위치한 칸의 상태는 항상 육지이다.
출력 조건 : 첫째 줄에 이동을 마친 후 캐릭터가 방문한 칸의 수를 출력한다.
입력 예시 :
4 4
1 1 0 // (1, 1)에 북쪽(0)을 바라보고 서 있는 캐릭터
1 1 1 1
1 0 0 1
1 1 0 1
1 1 1 1
출력 예시 :
3
▼ 정답 코드 보기
#include <iostream> #include <vector> #include <string> using std::cout; using std::cin; using std::vector; using std::string; int n, m; int graph[51][51]; bool visited[51][51]; int x, y, d; // 서 북 동 남 int dx[] = {0,-1,0,1}; int dy[] = {-1,0,1,0}; // d= 0,1,2,3, 북 동 남 서 int main() { std::ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n >> m; cin >> x >> y >> d; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> graph[i][j]; } } int rotate_cnt = 0; // 회전 횟수 int cnt = 0; // 이동 횟수 visited[x][y] = true; while (1) { // 왼쪽이 육지이고 안 가봤으면 if(graph[x + dx[d]][y + dy[d]] == 0 && !visited[x + dx[d]][y + dy[d]]){ x += dx[d]; y += dy[d]; d -= 1; if (d < 0) d = 3; rotate_cnt = 0; // 회전 횟수 visited[x][y] = true; cnt++; } else { // 왼쪽이 바다이거나 이미 가본 곳이라면 d -= 1; if (d < 0) d = 3; rotate_cnt++; if (rotate_cnt ==4) { d -= 1; if (d < 0) d = 3; if (!graph[x + dx[d]][y + dy[d]]) { x += dx[d]; y += dy[d]; d += 1; if (d > 3) d = 0; cnt++; rotate_cnt = 0; continue; } break; } } } cout << cnt; return 0; }
'PS > 이코테' 카테고리의 다른 글
| [ 이코테 2. Greedy ] (0) | 2021.11.23 |
|---|---|
| [ 이코테 3. DFS/BFS ] / 복습 ○ (0) | 2021.11.09 |