[이코테] 구현

아이디어를 코드로 바꾸는 구현

피지컬로 승부하기

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

흔히 구현 유형의 문제는 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 의미한다'

흔히 개발할 때 프로그래밍 언어의 문법에 능숙하고, 코드 작성 속도(타자)가 빠른 사람을 보고 '피지컬이 좋다' 라고 이야기 하는데, 구현 문제는 그런 의미에서 '피지컬을 요구하는' 문제이다.

이 책에서는 완전 탐색과 시뮬레이션 유형을 모두 구현으로 분류했다.

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

둘 다 구현에서 핵심이 될 수 있다.

구현 시 고려해야 할 메모리 제약 사항

자바에서 int 는 4바이트이고 크기가 정해져 있지만,
파이썬의 경우 자료형을 지정할 필요도 없고, 크기 제한도 없다.

실수형 변수의 경우 유효숫자에 따라 연산 결과가 원하는 값이 나오지 않을 수 있기 때문에 주의하자

대체로 코딩 테스트는 128 ~ 512 MB 로 메모리를 제한하는데,
수백만개 이상의 데이터를 처리해야 하는 문제는 메모리를 생각하며 문제를 풀어야 한다.

int 자료형 데이터의 개수에 따른 메모리 사용량

데이터의 개수(리스트의 길이)	메모리 사용량
1000	약 4KB
1,000,000	약 4MB
10,000,000	약 40MB

채점 환경

일반적으로 파이썬은 C/C++보다 두배 느리다.
그래서 파이썬은 두배의 시간제한을 주기도 한다.

1초에 2000만번 연산한다고 생각하면 된다.

N = 1,000,000일 때
Nlon2N 은 약 20,000,000 이다

예제 4-1 상하좌우

자바

package thisiscodingtest.implementation;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class UpDownLeftRight {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int max = Integer.parseInt(br.readLine());
        String[] move = br.readLine().split(" ");

        int[] index = {1, 1};

        for (int i = 0; i < move.length; i++) {
            String moveStr = move[i];

            if (moveStr.equals("D")) {
                index[0] = index[0] + 1;
                if (index[0] > max) {
                    index[0] = max;
                }
            } else if (moveStr.equals("U")) {

                index[0] = index[0]  - 1;
                if (index[0] < 1) {
                    index[0] = 1;
                }

            } else if (moveStr.equals("L")) {

                index[1] = index[1] - 1;
                if (index[1] < 1) {
                    index[1] = 1;
                }

            } else if (moveStr.equals("R")) {
                index[1] = index[1] + 1;
                if (index[1] > max) {
                    index[1] = max;
                }
            }
        }

        System.out.println(index[0] + " " + index[1]);
    }

}

파이썬

size = int(input())
move = list(map(str, input().split()))
x, y = 1, 1

for i in range(len(move)):
    move_to = move[i]
    if move_to == "U":
        if(x > 1):
            x -= 1
    if move_to == "D":
        if(x < size):
            x += 1
    if move_to == "L":
        if(y > 1):
            y -= 1
    if move_to == "R":
        if(y < size):
            y += 1

print(x, y)

기본 문법에서 많은 시간을 소비했다.
size 를 input 받으면서 int 로 캐스팅을 하지 않아 계속해서 에러가 발생했다.
타입을 처음에 지정해주지 않는 것이 익숙하지 않아서 발생하는 실수였다.
다음 문제부턴 유의해서 풀도록 해야겠다.

해설

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 ny < 1 or nx < 1 or ny > n or nx > n:
                continue

            x, y = nx, ny

print(x, y)

예제 4-2 시각

자바

package thisiscodingtest.implementation;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

public class Time {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int answer = 0;

        int a = 0;
        int b = 0;
        int c = 0;

        while (a != time + 1) {
            c++;
            if (c == 60) {
                c = 0;
                b++;
            }
            if (b == 60) {
                b = 0;
                a++;
            }
            String strA = String.valueOf(a);
            String strB = String.valueOf(b);
            String strC = String.valueOf(c);
            if (strA.contains("3") || strB.contains("3") || strC.contains("3")) {
                answer++;
            }
        }
        
        System.out.println(answer);
    }
}

파이썬

time = int(input())

answer = 0

for i in range (time + 1):
    for j in range(60):
        for k in range(60):
            if '3' in str(i) + str(j) + str(k):
                answer += 1

print(answer)

자바의 경우 3중포문을 사용하고 싶지 않아서 코드가 더 길어진 탓도 있는듯 하지만
파이썬은 정말 직관적이고 코드를 짧게 쓸 수 있다는 것을 깨달을 수 있는 문제였다.

실전 문제 - 왕실의 나이트

자바

package thisiscodingtest.implementation;

import java.util.Scanner;

public class Knight {
    public static void main(String[] args) {

        int answer = 0;
        final int min = 1;
        final int max = 8;

        Scanner sc = new Scanner(System.in);

        char[] chars = sc.nextLine().toCharArray();
        int indexX = chars[0] - 96;
        int indexY = Integer.parseInt(String.valueOf(chars[1]));

        int[][] move = {{-2, -1}, {-2, 1}, {2, -1}, {2, 1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};

        for (int i = 0; i < move.length; i++) {
            if (indexX + move[i][0] >= min && indexX + move[i][0] <= max) {
                if (indexY + move[i][1] >= min && indexY + move[i][1] <= max) {
                    answer++;
                }
            }
        }

        System.out.println(answer);
    }
}

파이썬

index = input()

indexX = int(ord(index[0]) - int(ord('a')) + 1)
indexY = int(index[1])
answer = 0

move = [[-2, -1], [-2, 1], [2, -1], [2, 1], [1, 2], [1, -2], [-1, 2], [-1, -2]]

for i in move:
    nextX = indexX + i[0]
    nextY = indexY + i[1]
    if nextX<= 8 and nextX >= 1 and nextY <=8 and nextY >= 1:
        answer += 1
print(answer)

실전 문제 - 게임 개발

자바

파이썬

알고리즘 공부를 더하고 접근해보도록 해야겠다.