이것이 취업을 위한 코딩테스트다 - 구현(1)

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

문제 해결 분야에서 구현 유형의 문제는 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미한다.

 

이 책에서는 완전 탐색,  시뮬레이션 유형을 모두 '구현' 유형으로 묶어서 다루고 있다.

완전탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미한다.

시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형을 의미한다.

---

대표 예제 1. 상하좌우

여행가 A는 N×N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 × 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상(1, 1) 이다. 
계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀 있다. 각 문자의 의미는 다음과 같다.
* L : 왼쪽으로 한 칸 이동
* R : 오른쪽으로 한 칸 이동
* U : 위로 한 칸 이동
* D : 아래로 한 칸 이동

이때 여행가 A가 N×N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다. 예를 들어 (1, 1)의 위치에서 L 혹은 U를 만나면 무시된다. 
예를 들어 N이 5이고, 계획서는 R→R→R→U→D→D 인 경우 여행가가 움직이게 되는 위치는 순서대로 (1, 2), (1, 3), (1, 4), (1, 4), (2, 4), (3, 4) 이므로 최종적으로 여행가 A가 도착하게 되는 곳의 좌표는 (3, 4)이다. 다시말해 3행 4열의 위치에 해당하므로 (3, 4)라고 적는다.
계획서가 주어졌을 때 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오.

입력 조건
 * 첫째 줄에 공간의 크기를 나타내는 N이 주어진다. (1 ≤ N ≤ 100)
 * 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다.(1 ≤ 이동횟수 ≤ 100 )

출력 조건
 * 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X, Y)를 공백으로 구분하여 출력한다.

입력 예시	출력 예시
5 R R R U D D	3 4

 

 

 

import java.util.Scanner;

public class J_4_1 {
    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;
            int 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);
    }
}

 

 

 

 

 

★ 알게된 표현

행렬이란 2차원 데이터를 일종의 표와 같은 형태로 쉽게 나타낼 수 있는 수학 개념중 하나

프로그래밍 언어에서 2차원 배열이라고 부르는 것과 동일하다고 볼 수 있다.

 

행렬에서는 가장 왼쪽 위에 있는 원소가 첫번째 원소이다.

세로축을 행이라고 표현하고, 가로축을 열이라고 표현한다.

 

  그래서 왼쪽 위부터 오른쪽으로 차례대로 이동하면 열의 위치가 증가한다고 볼 수 있고, 위에서 아래쪽으로 차례대로 이동하면 행의 인덱스가 증가한다고 볼 수 있다.

 

실제로 코딩테스트에서 2차원 공간에서의 방향벡터가 많이 사용된다. 이러한 각각의 방향에 따라서 어떠한 위치에서 다른 위치로 이동시키는 방식으로 로직을 설계하는 경우가 많다.    

 

dx, dy → direction x, direction y 와 같은 형태로 방향성을 명시해주기 위해서 배열같은 형태로 사용된다.

 

 

 

 

 

 

참고한 책 : 이것이 취업을 위한 코딩 테스트다 with 파이썬 by 나동빈
참고한 GitHub : https://github.com/ndb796/python-for-coding-test
참고한 강의 :
https://www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=2