[이코테_코딩테스트] 구현 문제 (Implementation)

구현 (Implementation)

• 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다.

알고리즘 대회에서 구현 유형의 문제란?

• 문제에서 요구하는 내용이 구현에 초점이 맞추어져 있음

• 구현이 어려운 문제를 의미
• 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
• 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
• 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
• 적절한 라이브러리를 찾아서 사용해야 하는 문제

일반적으로 알고리즘 문제에서의 2차원 공간은 행렬(Matrix)의 의미로 사용

시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용된다.

• 동쪽 방향 : dx[0], dy[0] = 0, 1

• 서쪽 방향 : dx[0], dy[-1] = 0, -1

• 남쪽 방향 : dx[1], dy[0] = 1, 0

• 북쪽 방향 : dx[-1], dy[0] = -1, 0

[문제] 상하좌우

• 여행가 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를 만나면 무시됩니다.

[문제] 상하좌우 : 문제 조건

[문제] 상하좌우 : 나의 답안 (Python)

n = int(input())
move = list(map(str, input().split()))

x, y = 1, 1

for i in move:
    if i == 'L' and y > 1:
        y -= 1
    elif i == 'R' and y < 5:
        y += 1
    elif i == 'U' and x > 1:
        x -= 1
    elif i == 'D' and x < 5:
        x += 1
    else:
        continue

print(x, y)

[문제] 상하좌우 : 답안 예시 (Python)

# N 입력받기
n = int(input())
x, y = 1, 1
plans = input().split()

# L, R, U, D에 따른 이동 방향
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
move_types = ['L', 'R', 'U', 'D']

# 이동 계획을 하나씩 확인
for plan in plans:
    # 이동 후 좌표 구하기
    for i in range(len(move_types)):
        if plan == move_types[i]:
            nx = x + dx[i]
            ny = y + dy[i]
    # 공간을 벗어나는 경우 무시
    if nx < 1 or ny < 1 or nx > n or ny > n:
        continue
    # 이동 수행
    x, y = nx, ny

print(x, y)

• 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];
                }
            }
            // 공간을 벗어나는 경우 무시 
            if (nx < 1 || ny < 1 || nx > n || ny > n) continue;
            // 이동 수행 
            x = nx;
            y = ny;
        }

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

}

이 글은 유튜브 “동빈나” 채널의 “(이코테 2021 강의 몰아보기) 2. 그리디 & 구현” 영상을 보고 작성하였습니다.