[이코테] 구현(Implementation)

구현(Implementation)

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

풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 말한다.

 

구현 유형의 예시

• 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
• 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
• 문자열을 특정한 기준에 따라서 끊어 처리해야하는 문제

 

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

for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 5; j++) {
        System.out.print("(" + i + ", " + j + ") ");
    }
    System.out.println();
}

 

완전 탐색, 시뮬레이션 유형을 '구현' 유형으로 분류하는데, 이러한 유형의 문제에서 2차원 공간에서의 방향 벡터가 자주 사용된다.

//동, 북, 서, 남
int[] dx = {0, -1, 0, 1};
int[] dy = {-1, 0, 1, 0};

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

for (int i = 0; i < 4; i++) {
    //다음 위치
    int nx = x + dx[i];
    int ny = y + dy[i];
    System.out.println(nx + " " + ny);
}

 

• 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 방법
• 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 방법

대표적인 구현 알고리즘의 문제로 '상하좌우', '시각' 문제가 있다.

---

예제 1) 상하좌우

여행가 A가 주어진 계획서를 따라 움직일 때, 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오.

계획서는 다음과 같다.

• L : 왼쪽으로 한칸 이동
• R : 오른쪽으로 한칸 이동
• U : 위로 한칸 이동
• D : 아래로 한칸 이동

가장 왼쪽 위 좌표는 (1, 1), 가장 오른쪽 아래 좌표는 (N, N)이고, 시작 좌표는 항상 (1, 1)

 

문제 해설

• 시뮬레이션 유형의 문제
• 2차원 방향 벡터를 사용해서 이동 계획에 맞는 이동 위치값을 구한다.

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());    //공간의 크기
        String[] array = br.readLine().split(" ");	//이동 계획서

        /* L, U, R, D에 따른 이동 방향
         * L -> (0, -1) 이동
         * U -> (-1, 0) 이동
         * R -> (0, 1) 이동
         * D -> (1, 0) 이동
         * */
        //동, 북, 서, 남
        int[] dx = {0, -1, 0, 1};
        int[] dy = {-1, 0, 1, 0};
        String[] directions = {"L", "U", "R", "D"};

        //시작 좌표
        int x = 1;
        int y = 1;
        for (int i = 0; i < array.length; i++) {
            for(int j = 0; j < directions.length; j++) {
                if (array[i].equals(directions[j])) {
                    int nx = x + dx[j];
                    int ny = y + dy[j];

                    //공간을 벗어나는 경우는 무시
                    if (nx < 1 || ny < 1 || nx > n || ny > n) {
                        continue;
                    }
                    x = nx;
                    y = ny;
                }
            }
        }

        bw.write(x + " " + y);
        bw.flush();
        bw.close();
    }
}

 

 

 

 

예제 2) 시각

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오.

 

문제 해설

• 완전 탐색 유형의 문제
• 3중 for문을 사용해서 00시 00분 00초부터 N시 59분 59초까지 3이 포함된 경우를 센다.
• int형 시, 분, 초를 문자열로 변환한 후, contains 함수를 사용해서 문자열 안에 "3" 이 포함되어 있는지 확인한다.

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        int answer = 0;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= 59; j++) {
                for (int k = 0; k <= 59; k++) {
                    //i, j, k를 문자로 바꿔서 contains 함수 사용
                    String str = String.valueOf(i) + String.valueOf(j) + String.valueOf(k);
                    if (str.contains("3")) {
                        answer++;
                    }
                }
            }
        }
        bw.write(answer + "\n");
        bw.flush();
        bw.close();
    }
}

 

 

 

 

예제 3) 왕실의 나이트

8 × 8 좌표 평면의 왕실 정원에 특정한 한 칸에 나이트가 서 있다. 나이트는 L자 형태로만 이동할 수 있고 정원 밖으로 나갈 수 없다.

나이트는 다음 2가지 경우로 이동할 수 있다.

1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기

2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기

나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오.

 

문제 해설

• 상하좌우 문제와 유사(시뮬레이션)
• 나이트가 이동할 수 있는 모든 경로를 하나씩 확인하면서 이동한다.
• 나이트가 상하좌우로 이동할 수 있는 방향 벡터는 아래와 같다.

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String str = br.readLine(); //나이트의 현재 위치
        int x = str.charAt(1) - '0';    //행
        int y = str.charAt(0) - 96;    //열

        //상,
        int[][] moves = {{-1, -2}, {1, -2}, {2, -1}, {2, 1},
                        {-1, 2}, {1, 2}, {-2, -1}, {-2, 1}};

        int answer = 0;
        for (int i = 0; i < moves.length; i++) {
            int dx = x + moves[i][0];
            int dy = y + moves[i][1];

            System.out.println(dx + " " + dy);
            //좌표 평면을 벗어나는 경우
            if (dx < 1 || dy < 1 || dx > 8 || dy > 8) {
                continue;
            }
            answer++;
        }
        bw.write(answer + "\n");
        bw.flush();
        bw.close();
    }
}

 

 

 

 

예제 4) 게임 개발

N × M 크기의 직사각형 맵이 있고, 각 칸은 (A, B)로 나타낼 수 있다.

캐릭터는 상하좌우로 움직일 수 있고, 바다로 된 공간에는 갈 수 없다.

 

1. 현재 위치에서 현재 방향을 기준으로 왼쪽방향(반시계방향으로 90도 회전)부터 차례대로 갈 곳을 정한다.

2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 후 왼쪽으로 한 칸 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 하고 1로 돌아간다.

3. 만약 네 방향 모두 이미 가본 칸 or 바다이면, 바라보는 방향을 유지한 채로 한칸 뒤로 가고 1로 돌아간다. 이 때, 뒤쪽이 바다라 뒤로 갈 수 없을 경우 움직임을 멈춘다.

 

위의 캐릭터 매뉴얼에 따라 캐릭터를 이동시킨 후, 캐릭터가 방문한 칸의수를 출력하는 프로그램을 만드시오.

- 0: 북쪽, 1: 동쪽, 2: 남쪽, 3: 서쪽

- 0: 육지, 1: 바다

 

문제 해설

• 시뮬레이션 유형의 문제
• 예제 1) 상하좌우 문제와 동일하게 2차원 방향 벡터를 사용해서 방향을 회전한다.

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());   //캐릭터 위치 a
        int b = Integer.parseInt(st.nextToken());   //캐릭터 위치 b
        int d = Integer.parseInt(st.nextToken());   //캐릭터가 바라보는 방향

        //맵 정보
        int[][] map = new int[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        //북, 동, 남, 서
        int[] da = {-1, 0, 1, 0};
        int[] db = {0, 1, 0, -1};

        int answer = 1;     //캐릭터가 방문한 칸의 수
        int turn_count = 0;  //네 방향 모두 확인했는지 횟수
        boolean[][] visited = new boolean[n][m];    //방문 처리
        visited[a][b] = true; //현재 시작 위치는 방문처리

        while (true) {
            //왼쪽 방향으로 회전
            if (d == 0) {
                d = 3;
            } else {
                d--;
            }

            //왼쪽 방향의 방향값
            int next_a = a + da[d];
            int next_b = b + db[d];

            //왼쪽 방향에 가보지 않은 칸 O -> 왼쪽 회전, 왼쪽으로 한 칸 전진
            if (map[next_a][next_b] == 0 && visited[next_a][next_b] == false) {
                a = next_a;
                b = next_b;
                visited[a][b] = true;   //방문처리
                turn_count = 0;
                answer++;
                continue;
            } else {    //왼쪽 방향에 가보지 않은 칸 X -> 왼쪽 회전, 1단계로 돌아감
                turn_count++;
            }

            //네 방향 모두 가본 칸 or 바다 -> 방향 유지, 뒤로 한칸 후진, 1단계로 돌아감
            if (turn_count == 4) {
                //다음 위치
                next_a = a - da[d];
                next_b = b - db[d];

                if (map[next_a][next_b] == 1) {   //바다인 경우 이동 stop
                    break;
                } else {
                    a = next_a;
                    b = next_b;
                }
                turn_count = 0;
            }
        }

        bw.write(answer + "\n");
        bw.flush();
        bw.close();
    }
}

---

[참고]

이것이 취업을 위한 코딩 테스트다 with 파이썬