이것이 코딩 테스트다 - Chapter4 구현 정리

 

"구현" 이란 

머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램으로 작성하기

 

구현 파트는 다른 파트와는 다르게 별다른 특별한 방법없이 "묵묵히 주어진대로 구현" 하는 파트이다.

하지만 그래도 몇가지 특징이 있다.

 

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

✓ 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례로 직접 수행

 

일명 "피지컬" 이라고 불릴만큼 차근차근 잘 풀어내는 스킬이다.

 

여기서 개인적으로 느낀 키포인트는 

" 반복문을 통해 전체 케이스를 올바르게 잘 나눌 수 있는가? "

이렇게 느껴진다.

 

여기서 중요한점은 " 입력 숫자의 범위 "와 " 제한된 용량 ", " 제한된 시간 "을 주의해야 한다는 점이다.

다른언어의 경우 int형을 벗어나는 경우 long long 형 등 자료형을 고려해야 하지만, 파이썬의 경우 범위제한이 크게 없기 때문에 비교적 자유롭게 다룰 수 있다.

 

하지만 숫자를 저장하는 리스트의 경우 용량을 생각하며 작성해야 한다.

" 메모리 제한 : 128MB "

보통의 문제의 경우 128MB를 제한으로 둔다. 이때, 1,000만 : 약 40MB를 차지하므로

" 리스트 길이를 최대 10,000,000 으로 두고 작성해야 한다 " 

이러한 점이 특징이다.

 

또한, 시간제한 역시 고려를 해야한다.

"시간 제한 : 1초 "

보통의 문제의 경우 1초가 기준점이 되는데 이 실행시간은 채점시스템의 컴퓨터 사양과 관련이 있지만 대개 

" 약 20,000,000회 연산, 시간복잡도 O(NlogN) "

이렇게 고려하고 작성하면 될것이다.

 

 

 

자, 다시 돌아와서 구현을 다시금 정리하자면

" 반복문을 통해 완전탐색, 또는 시뮬레이션을 구현하며, 리스트 크기와 시간복잡도를 고려해야 한다 "

이렇게 요약할 수 있겠다.

 

 

 

다음으로는 몇가지 예시를 가지고서 필요한 코드적 스킬을 정리하겠다.

 

1. "이동" + "시뮬레이션"

 

5✕5 크기의 지도에서 현재 (1,1) 위치에 있다. 명령어 "L", "R", "U", "D"를 통해 사방으로 움직인 후 최종위치를 출력한다. (다만, 지도를 벗어나는 명령어의 경우 무시된다)

-> 명령어 : R R R U D D

 

이 문제의 경우 명령에 따라 한번씩 "이동" 시키는 대표적인 "시뮬레이션" 유형의 문제이다.

이러한 이동이 있는 문제의 경우 아래 두가지 문법 중 하나를 사용하게 된다

 

1) dx, dy 리스트 방법

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

-> 이동시 쓰이는 코드

nx = x + dx[i]
ny = y + dy[i]

 

2) move 리스트 방법

move = [(0,-1), (0,1), (-1,0), (1,0)]

-> 이동시 쓰이는 코드

nx = x+move[i][0]
ny = y+move[i][1]

나는 사실 move 형식이 좀더 직관적으로 보이기 때문에 move 형식을 사용한다. 하지만 큰 차이는 없는것 같아 원하는형식으로 사용하면 될 것 같다.

 

또한, 같이 쓰이는 방법 중 하나로, 명령어가 주어지는 경우 하나하나 if 문을 통해 체크하는 방법보다는

move_types = ['L', 'R', 'U', 'D']

이렇게 명령어를 리스트로 만들어 for문을 통해 index로 접근하는 것이 더욱 깔끔하다.

 

따라서 위의 이동 기술에 따라 코드를 구현하자면

move = [(0,-1), (0,1), (-1,0), (1,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 + move[i][0]
      ny = y + move[i][1]
      
    if nx < 1 or ny < 1 or nx > 5 or ny > 5 : #이동 후 위치가 지도를 벗어나는 경우
      continue #이동하지 않고 다음 명령을 본다
    x, y = nx, ny #정상범위인 경우 이동한다

print(x, y)

1. for 문을 통해 명령어 리스트와 비교하여 인덱스 구하기

2. 해당 인덱스의 방향을 가져와 다음위치 구하기

3. 문제 지시에 따라 다음위치가 적절한지 여부에 따라 행동하기

이정도로 요약이 되겠다.

 

 

 

"이동" + "시뮬레이션" 문제를 또하나 보겠다.

 

행 : 1~8, 열 : a~h인 8✕8 크기의 체스판의 특정위치에 나이트가 위치해 있다.

나이트는 [수평방향 2 + 수직방향 1] 또는 [수평방향 1 + 수직방향 2] 로 이동이 가능하다.

이때, 현재위치를 열행이 합쳐진 문자(ex : a1)을 입력받았을 때, 이동가능한 회수를 구한다.

 

이 역시 이동이 필요한 문제이므로

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

이렇게 이동에 관한 리스트를 작성하겠다.

 

이 문제에서 "a1" 과 같은 형식으로 입력을 받는데 이를 위치인 (1,1)로 변환하기 위해서는 또하나의 스킬이 필요하다.

column = int(ord(input_data[0])) - int(ord('a'))+1

이 코드는, a를 1로 변환해주는 코드이다.

 

이제 위의 문제와 마찬가지로 현재 위치를 구한다음 다음위치를 각각 구하여 진행해보면 되겠다.

input_data = input()
row = int(input_data[1]) #행
column = int(ord(input_data[0])) - int(ord('a'))+1 #열

steps = [(-2,-1), (-1,-2), (1,-2), (2,-1), (2,1), (1,2), (-1,2), (-2,1)]
result = 0 #이동 가능한 회수 저장

for step in steps : #이동리스트의 모든 경우를 확인한다
  next_row = row+step[0]
  next_column = column+step[1]

  if next_row >= 1 and next_row <= 8 and next_column >= 1 and next_column <= 8 :
    result += 1 #이동 후 위치가 체스판 내부일 경우 회수를 증가시킨다

print(result)

다음위치를 구한 후 다음위치가 적절한지 여부(체스판 내부에 위치하는지 여부)에 따라 행동(count 세기)하기 가 되겠다.

 

 

하나 더 "이동" + "시뮬레이션" 문제를 보겠다.

 

첫 줄에 맵의 행, 열 크기를 입력 받고, 둘째줄에 시작위치와 방향을 입력받는다. (방향 0 : 북, 1 : 동, 2 : 남, 3 : 서)

그리고 맵 크기만큼 맵을 입력받는다. 이때, 맵은 육지인 0과 바다인 1로 입력이 되는데

플레이어가 다음 규칙에 따라 현재위치를 포함하여 이동한 위치의 수를 반환한다.

  규칙1) 현재 방향을 기준으로 반시계방향(왼쪽)으로 회전하며 갈 곳을 확인한다.

  규칙2) 회전 후 바라보는 방향이 안가본 칸인 경우 전진한다. 바다, 또는 가본칸의 경우 규칙1을 다시 반복한다.

  규칙3) 만약 4번 회전이 된경우(사방으로 못움직이는 경우) 방향을 유지한 채로 뒤가 바다가 아닌경우 뒤로 이동한다.

  이때 바다인 경우 게임이 종료된다.

 

문제를 딱 읽을때 내용이 길고 어려워 보이지만 역시 차근차근 나누면

" 현재위치에서 다음위치(회전 후 전방의 위치)를 구한 다음 다음위치가 적절한지(육지, 바다, 가본곳)인지 여부에 따라 행동(회전, 또는 이동)한다. "

 

이동이 있으므로 리스트를 만든다.

move = [(-1,0), (0,1), (1,0), (0,-1)] #방향에 따른 이동위치

그리고 여기서 회전이 있기 때문에 해당 함수를 만든다.

def rotation() : #왼쪽회전 함수
  global direction
  direction -= 1
  if direction == -1 :
    direction = 3

그리고나면 반복문을 통해 다음위치를 구하며 이동 가능한지 여부를 잘 나누어 계산하면 되겠다.

그렇게 코드를 작성하면 아래와 같이 되겠다.

N, M = map(int, input().split())
x, y, direction = map(int, input().split()) #시작위치, 방향 입력
map = [list(map(int, input().split())) for i in range(N)] #맵 저장

map_status = [[0 for i in range(M)] for j in range(N)] #플레이어 이동상태 기록
move = [(-1,0), (0,1), (1,0), (0,-1)] #방향에 따른 이동위치

def rotation() : #왼쪽회전 함수
  global direction
  direction -= 1
  if direction == -1 :
    direction = 3

result = 1 #이동회수
turn_count = 0 #회전회수

while True : #본게임
  map_status[x][y] = 1
  rotation() #왼쪽 회전
  turn_count += 1 #회전수 증가
  if turn_count == 4 : #만약 4방향 다 확인한 경우
    next_x = x-move[direction][0]
    next_y = y-move[direction][1]
    if map[next_x][next_y] == 0 : #뒤로 이동 가능한 경우
      x = next_x
      y = next_y
      turn_count = 0
      continue
    else : #게임 종료
      break
  else : #회전 후 확인작업
    next_x = x+move[direction][0]
    next_y = y+move[direction][1]
    if map[next_x][next_y] == 0 and map_status[next_x][next_y] == 0 : #육지이며 안가본 경우 움직인다
      result += 1
      x = next_x
      y = next_y
      turn_count = 0
      continue
    else : #못갈경우 다음회전 실행
      continue

print(result)

 

이렇게 "이동"과 "시뮬레이션" 형태의 구현을 접하면 되겠다.

 

 

다음으로 간단하지만, "완전탐색"의 형태의 예시를 보겠다.

 

2. "완전탐색"

 

정수 N이 입력되면 00:00:00 부터 N:59:59 까지의 시간 중에 숫자'3'이 하나라도 들어있는 시간이 몇번인지를 구한다.

 

이같은 완전탐색의 경우 첫번째로 "전체크기"를 먼저 살펴봐야 한다.

24시간의 경우 86,400 가지의 경우밖에 안되므로 전체를 다 살펴도 1초를 넘지 않는다.

 

그렇기 때문에 "시간", "분", "초" 를 각각 for문을 통해 숫자 3이 있는지 여부를 확인하면 되겠다.

 

여기서 해당 문자가 있는지 여부를 확인하는 스킬이 필요하다.

if '3' in str(i)+str(j)+str(k) : #문자열로 만들어 그 문자열 내에 해당 '3'이 있는 경우

이 스킬을 통하면 아주 간단히 해결이 될 수 있다.

H = int(input())
count = 0
for i in range(H+1) :
  for j in range(60) :
    for k in range(60) :
      if '3' in str(i)+str(j)+str(k) :
        count += 1
print(count)

 

 

이렇게 구현파트에 대해 살펴보았다.

 

삼정전자에서도 주로 출제되며 코딩테스트에 제일 의미상 적합한 내용이므로

차근차근 케이스를 잘 나누어 풀면 되겠다.

 

깃허브 - github.com/CodingTestStudy/FreeDeveloper_Cote/tree/main/구현

CodingTestStudy/FreeDeveloper_Cote