[5일차] 이.코.테.다! Ch4 구현 Implementation

Ch4. 구현 implementation

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

      1-1. 피지컬로 승부하기

             - '코딩 테스트에서 구현이란?'

                : 머릿 속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다.
                  그렇기 때문에 대부분 구현을 별도의 유형으로 다루지 않지만, 코딩 테스트에서는 자주 출제가 된다.

             - '피지컬이 좋다'
               : 프로그래밍 문법을 정확하게 숙지하고, 라이브러리 사용 경험이 풍부하며, 코드 작성 속도(타자)가 빠를 때 

             - '구현 유형의 문제'
               : 풀이를 떠올리는 것은 쉽지만, 소스코드로 옮기기 어려운 문제
                 (알고리즘은 설계했는데 구현이 먼저 풀 수 있는 문제가 없을 때 푸는 것이 좋다)

                  1) 완전 탐색: 모든 경우의 수를 주저 없이 다 계산하는 해결 방법

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

              

      1-2. 구현 시 고려해야 할 메모리 제약 사항

             - '변수의 표현 범위'

                1) C/C++/Java
                    : int형, long long형, BigInteger 순으로 자료형의 표현 범위에 주의해야한다.

                2) Python
                    :  직접 자료형을 지정할 필요가 없고 매우 큰 수의 연산 또한 지원하므로 주의하지 않아도 된다.

             - '파이썬에서 리스트 크기'

                 : 파이썬에서 리스트를 이용할 때 코딩 테스트의 메모리 제한을 고려해야 한다. (그러나, 드물다)

 

      1-3. 채점 환경

             - 시간 제한이 1초이고, 데이터의 개수가 100만개인 문제가 있다면 일반적으로 시간 복잡도 O(NlogN)이내의

               알고리즘을 이용하여 풀어야 한다. N = 1,000,000(100만) -> NlogN = 약 20,000,000(2000만번)

               (제출한 코드가 1초에 2000만번의 연산을 수행한다고 가정하면 크게 무리가 없다)

             - 따라서 알고리즘 문제를 풀 때는 시간 제한과 데이터의 개수를 먼저 확인한 뒤 이 문제를 어느 정도의 시간 복잡도의

               알고리즘으로 작성해야 풀 수 있을 것인지 예측할 수 있어야 한다.

               

      1-4. 구현 문제에 접근하는 방법

             - 특징
               1) 문제의 길이가 길지만, 고차원적인 사고력을 요구하지 않기 때문에 문법에 익숙하다면 오히려 쉽게 풀 수 있다.

               2) 문자열을 처리하거나 큰 정수를 처리하는 구현 문제가 나올 때는 C/C++/Java보다 Python이 쉬울 수 있다.

              

      1-5. 상하좌우

             - 문제

             - 문제 해결
                : 요구사항대로 구현하면 연산 횟수는 이동 횟수에 비례하게 된다. 이동 횟수가 N번인 경우 시간 복잡도 O(N)이다.
                  일련의 명령에 따라 개체를 차례대로 이동시킨다는 점에서 simulation 유형으로 분류되며 구현이 중요한 문제다.

             - 소스 코드

 

      1-6. 시각

             - 문제

             - 문제 해결

               : 00시 00분 00초 ~ 23시 59분 59초까지의 모든 경우의 수는 86,400가지(24*60*60초)이다.

                 경우의 수가 100,000가지도 되지 않기 때문에 시간 제한 2초 안에 문제를 해결할 수 있다.

                 가능한 경우의 수를 모두 검사하는 방법으로 완전 탐색 유형이다.

                 일반적으로 탐색해야할 전체 데이터의 개수가 100만개 이하일 때 완전 탐색을 사용하면 적절하다.

             - 소스 코드

 

2. 왕실의 나이트

    - 문제

    - 문제 해결

       : 나이트가 위치한 곳을 문자열과 숫자의 조합이 아니라 같은 행과 열 형태로 들어올 수도 있었다. (예외처리 필요)

         이 문제는 나이트가 이동할 수 있는 경로를 하나씩 확인하여 이동하면서 결과를 확인하면 된다. 

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

          1) 수평으로 두 칸 이동 후 수직으로 한 칸 이동

          2) 수직으로 두 칸 이동 후 수평으로 한 칸 이동

가능한 움직임을 (x,y) 나타내면 (-1, -2), (1, -2), (-1, 2), (1, 2), (-2, -1), (2, -1), (-2, 1), (2, 1)로 8가지의 경우가 나온다.

 

상하좌우와 비슷한 문제지만 이동방향을 dx,dy를 사용하느냐,
특정 방향 값을 지정하여 방향을 설정하느냐 2가지 모두 자주 사용되므로 참고!

 

 

    - 소스 코드

 

3. 게임 개발

    - 문제 

    - 문제 해결

      :  문제가 길고 문제를 바르게 이해하여 소스 코드로 옮기는 과정이 간단하지 않기 때문에 반복적인 숙달이 필요하다.

    - 소스 코드

n, m = map(int, input().split())
visit = [[0] * m for _ in range(n)]

x, y, direction = map(int, input().split())
visit[x][y] = 1

arr = []
for i in range(n):
  arr.append(list(map(int, input().split())))

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

def turn_left():
  global direction
  direction -= 1
  if direction == -1:
    direction = 3

count = 1;
turn_time = 0
while True:
  turn_left()
  nx = x + dx[direction]
  ny = y + dy[direction]

  if visit[nx][ny] == 0 and arr[nx][ny] == 0:
    visit[nx][ny] = 1
    x = nx
    y = ny
    count += 1
    turn_time = 0
    continue
  else:
    turn_time += 1
  
  if turn_time == 4:
    nx = x - dx[direction]
    ny = y - dy[direction]
    if arr[nx][ny] == 0:
      x = nx
      y = ny
    else:
      break
    turn_time = 0

print(count)

#include <stdio.h>
using namespace std;

int N, M, x, y, dir;
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int arr[51][51];
int visit[51][51];

void turn_left() {
    dir -= 1;
    if (dir == -1) dir = 3;
}

int main() {
    scanf("%d %d", &N, &M);
    scanf("%d %d %d", &x, &y, &dir);
    visit[x][y] = 1;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++)
            scanf("%d", &arr[i][j]);
    }
    int count = 1;
    int turn_cnt = 0;
    while (true) {
        turn_left();
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        if (visit[nx][ny] == 0 && arr[nx][ny] == 0) {
            visit[nx][ny] = 1;
            x = nx; y = ny;
            count += 1; turn_cnt = 0;
            continue;
        }
        else turn_cnt += 1;

        if (turn_cnt == 4) {
            nx = x - dx[dir];
            ny = y - dy[dir];
            if (arr[nx][ny] == 0) {
                x = nx; y = ny;
            }
            else break;
            turn_cnt = 0;
        }
    }

    printf("%d", count);
    return 0;
}