구현 유형이란

---

• 광의적 의미 : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
• 협의적 의미(코테에서의 구현 유형 문제) : 알고리즘(풀이)을 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭함

구현 유형의 종류

• 실수연산
• 문자열 처리
• 적절한 라이브러리를 찾아서 사용
• 완전탐색
  : 가능한 경우의 수를 모두 검사해보는 탐색 방법
• 시뮬레이션
  : 행렬에서 특정 좌표에서 다음 좌표로 이동하는 문제로,
  주로 방향벡터를 사용하여 문제 풀이

    # python

    # dx, dy : 방향벡터
    # 동, 북, 서, 남
    dx = [0, -1, 0, 1]	
    dy = [1, 0, -1, 0]	

    # 현재 위치
    x, y = 2, 2

    for i in range(4):
        // nx, ny : 다음 위치
        nx = x + dx[i]
        ny = y + dy[i]
        print(nx, ny)

✅참고 : 코테에서 흔히 통용되는 개념
구현 = 시뮬레이션 + 완전탐색 + ... (강의 기준 분류)
OR
구현 = 시뮬레이션 = 완전탐색

Q. 상하좌우 (O)

---

여행가 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를 만나면
무시된다. 계획서가 주어졌을 때 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오.

답안

import java.util.Scanner;

class Main {

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        sc.nextLine();
        String[] plan  = sc.nextLine().split(" ");

        // 동, 북, 서, 남
        int[] dx = {0, -1, 0, 1};
        int[] dy = {1, 0, -1, 0};
        String[] direction = {"R", "U", "L", "D" };

        // 현재 위치
        int x = 1;
        int y = 1;

        for(int i=0; i< plan.length; i++) {
            for(int j=0; j< direction.length; j++) {
                if (plan[i].equals(direction[j])) {
                    int nx = x + dx[j];
                    int ny = y + dy[j];

                    if(nx >= 1 && ny>=1 && nx <= n && ny <= n){
                        x = nx;
                        y = ny;
                    }
                }

            }

        }

        System.out.println(x+" "+y);

    }
}

정답

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // N을 입력받기
        int n = sc.nextInt();
        // 정수 입력 후 한 줄의 문자열을 입력 받기 전엔 버퍼 비우기
        sc.nextLine(); 
        String[] plans = sc.nextLine().split(" ");
        int x = 1, y = 1;

        // L, R, U, D에 따른 이동 방향 
        int[] dx = {0, 0, -1, 1};
        int[] dy = {-1, 1, 0, 0};
        char[] moveTypes = {'L', 'R', 'U', 'D'};

        // 이동 계획을 하나씩 확인
        for (int i = 0; i < plans.length; i++) {
            char plan = plans[i].charAt(0);
            // 이동 후 좌표 구하기 
            int nx = -1, ny = -1;
            for (int j = 0; j < 4; j++) {
                if (plan == moveTypes[j]) {
                    nx = x + dx[j];
                    ny = y + dy[j];
                }
            }
            // 공간을 벗어나는 경우 continue 이후 코드는 무시하고 다음번 반복 시작
            if (nx < 1 || ny < 1 || nx > n || ny > n) continue;
            // 이동 수행 
            x = nx;
            y = ny;
        }

        System.out.println(x + " " + y);
    }

}