1. '구현'은 어떤 문제인가?

코딩 테스트에서 다루는 알고리즘 유형 중 하나인 '구현'은 크게 완전탐색, 시뮬레이션 문제로 나눠볼 수 있다.(이것이 코딩테스트다 - 나동빈 저에 따르면)
'완전탐색'은 모든 경우의 수 구하는 문제이며, '시뮬레이션'은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 유형이다. 두 유형의 문제는 풀이 방법에 따라서 시간, 공간 복잡도가 다양할 수 있으므르 시간제한과 데이터의 개수를 먼저 확인한 뒤 문제를 어느 정도의 시간 복잡도의 알고리즘으로 풀지 예측해야한다.(이거 어렵다)

2. 완전탐색

이 유형을 어떻게 풀어라는 없다. 그냥 문제를 해석하고 냅다 푸는 수 밖에... 완전탐색 유형 문제를 풀다가, 상하좌우[이것이 코딩테스트다 - 110p]라는 문제를 보았다. 내가 구현한 풀이와 저자의 풀이의 차이가 컸다. 완전탐색 유형은 저자의 풀이처럼 센스있는, 즉 시간적, 공간적으로 효율있는 코딩을 짜도록 많이 연습해야겠다.

2-1. [예제 1] 상하좌우 (강세훈 코드)

from sys import stdin
input = stdin.readline

if __name__ == "__main__":
    N = int(input())
    dir = list(input().strip().split())
    loc = [0,0]
    
    for d in dir :
        if d == "L":
            if loc[1]-1 >= 0 :
                loc = [loc[0], loc[1]-1]
        elif d == "R":
            if loc[1]+1 < N :
                loc = [loc[0], loc[1]+1]
        elif d == "U":
            if loc[0]-1 >= 0 :
                loc = [loc[0]-1, loc[1]]
        else :
            if loc[0]+1 < N :
                loc = [loc[0]+1, loc[1]]
    print(f'{loc[0]+1} {loc[1]+1}')

• 문제점 :
  1) for 구문 안에 조건 분기처리가 4개나 된다. 따라서 else의 경우, 이전 조건 3개를 타고 와야해서 비효율적이라고 생각했다.
  2) 조건 분기 내에 또 조건 분기가 있다. 그리고 그 조건 분기 내부에는 다른 조건 분기 부분과 구조가 같은 코드가 반복된다.
  => 코드 재사용성 0점

2-2. [예제 1] 상하좌우 (저자 코드)

from sys import stdin
input = stdin.readline

if __name__ == "__main__":
    N = int(input())
    dir = list(input().strip().split())
    loc = [1,1]
    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    plan = ['U','D', 'L', 'R']
  
    for d in dir :
        for p in range(len(plan)) : 
            if d == plan[p] :
                nx = loc[0] + dx[p]
                ny = loc[1] + dy[p]
                if 1<= nx <=N and 1<= ny <=N :
                    loc = [nx, ny]
                else :
                    continue
    print(loc)

• 배울 점
  1) plan에 따른 dx, dy값을 index 기준으로 통일시켰다(-1, 0, "U" : plan이 "U"이면 x-=1, y+=0). 따라서 분기처리가 필요없다.
  => 코드의 가독성 증가

2-3. [예제 2] 왕실의 나이트 (강세훈 코드)

앞선 문제(상하좌우)에서의 개선점을 유념해서 이번 문제를 풀었다. 문제는 [이것이 코딩테스트다 - 115p]를 참고했다.

from sys import stdin
input = stdin.readline

if __name__ == "__main__":
    N = input().strip()
    dx = [1,1,-1,-1,2,2,-2,-2]
    dy = [2,-2,2,-2,1,-1,1,-1]
    
    loc = [ord(N[0])-96, int(N[1])]
    count = 0
    
    for i in range(8):
        x,y = loc
        if 1<=x+dx[i]<=8 and 1<= y + dy[i] <=8:    
            count +=1
            
    print(count)

• 잘한 점
  1) dx, dy에 각 배열을 초기화하여 인덱스에 따라 위치를 결정해주도록 설정했다. 이번 문제의 성격에 맞게 dx와 dy를 잘 설정했다.

3. 시뮬레이션

이런 유형처럼 조건이 길어지는 문제들에 항상 어려움을 느꼈다. 이후에 제시할 '게임 개발'문제도 푸는데 총 38분이 걸렸는데, 이렇게 시간이 걸린 가장 큰 원인은 '집중력 부족'에 있었다. 집중력이 부족해 문제 해석이 어려웠다고 판단된다. 많이 풀어서 익숙해지자.

3-1. [예제 3] 게임 개발 (강세훈 코드)

# 23:02 ~ 23:40(38m)
from sys import stdin;
input = stdin.readline;

if __name__ == "__main__":
    row, col = map(int, input().split());
    x, y, dir = map(int, input().split());
    field = [list(map(int, input().split())) for _ in range(row)];
    visited = [[False] *(col+1) for _ in range(row +1)];
    visited[x][y] = True;
    
    dx = [-1, 0, 1, 0];
    dy = [0, 1, 0, -1];
    
    isOver = False
    cnt = 1;
    
    while not isOver: 
        for _ in range(4):   
            dir = 3 if (dir - 1) < 0 else (dir-1);            
            nx = x + dx[dir];
            ny = y + dy[dir];
            
            if not visited[nx][ny] and field[nx][ny] == 0:
                x = nx;
                y = ny;
                cnt+=1;
                visited[nx][ny] = True;
                break;            
          
        x = x - dx[dir]
        y = y - dy[dir]
        
        if field[x][y] == 1:
            isOver = True;
        else :
            cnt += 1;
            visited[x][y] = True;
                    
    print(cnt)

4. 느낀점

이번 구현 문제는 많이 풀어보는 것보다 좋은 것이 없을 것 같다. 특히 조건들이 많아지는 문제는 집중력을 잃을 수 있으니 더 자주 문제를 풀어서 최대한 친해져봐야겠다.