구현(완전 탐색, 시뮬레이션) with 파이썬

in Algorithm on Basics

1. 개요

코딩 테스트에서 구현이란 ‘머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정’이다. 어떤 문제를 풀든 간에 소스코드를 작성하는 과정은 필수이므로 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다.

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


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

대체로 코딩 테스트에서는 128 ~ 512 MB로 메모리를 제한하는데 알고리즘 문제 중 때로는 수백만 개 이상의 데이터를 처리해야하는 문제가 출제된다. int 자료형의 데이터 개수에 따른 메모리 사용량을 확인해보자. 파이썬에서는 정수 데이터를 사용할 때 int와 같은 별도의 자료형을 명시해줄 필요가 없지만 시스템 내부적으로는 다음 표에서 보여주는 것과 유사한 크기만큼 메모리를 차지한다.

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

크기가 1,000만 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 풀 수 없게 되는 경우도 있다는 점을 기억하자. 일반적인 기업 코딩 테스트 환경에서는 파이썬으로 제출한 코드가 1초에 2,000만 번의 연산을 수행한다고 가정하면 크게 무리가 없다는 점도 기억하자.
시간 제한이 1초이고 데이터의 개수가 100만 개인 문제가 있다면 일반적으로 시간 복잡도가 NlogN 이내의 알고리즘을 이용하여 풀어야 한다. 실제로 N이 백만일 때 NlogN은 약 2천만이기 때문이다. 따라서 알고리즘 문제를 풀 때는 시간 제한과 데이터의 개수를 먼저 확인한 뒤에 이 문제를 어느 정도의 시간 복잡도 알고리즘으로 작성해야 풀 수 있을 것인지에 대해 예측할 수 있어야 한다.

3. 구현 문제에 접근하는 방법

구현 유형의 문제는 사소한 입력 조건 등을 문제에서 명시해주며 문제의 길이가 꽤 긴 편이다. 하지만 고차원적인 사고력을 요구하는 문제는 나오지 않는 편이라 문법에 익숙하다면 오히려 쉽게 풀 수 있다.
Pypy3는 파이썬3의 문법을 그대로 지원하며, 대부분 파이썬3 보다 실행 속도가 빠르다. 이 말은 코딩 테스트에서 Pypy3를 선택한다면 파이썬3와 동일한 코드를 제출해서 실행 시간을 줄일 수 있다는 의미이다. 따라서 코딩 테스트에서 Pypy3를 지원한다면 Pypy3를 이용하도록 하자.

4. 예제

문제 : 상하좌우

여행가 A는 N * N 크기의 정사각형 공간에 있고 출발 좌표는 항상 (1,1)이다. 한 칸씩 이동을 기준으로 하여 L(왼쪽), R(오른쪽), U(위), D(아래)로 이동한다. 만약 정사각형 공간 범위를 넘어가면 움직임은 무시된다.

  • 첫째 줄에 공간의 크기 N이 주어진다. (1~100)
  • 둘째 줄에 여행가의 이동 계획서가 주어진다. (1<= 이동횟수 <=100)
  • 여행가가 최종적으로 도착할 지점의 좌표를 출력한다.
입력 예시
5
R R R U D D

출력 예시
3 4

풀이

N = int(input())
plan = input().split()
direction = ['U','D','R','L']
dx = [-1,1,0,0] # x,y좌표계는 오른쪽으로 90도 회전한 것으로 고려할것
dy = [0,0,1,-1]
x=y=1
for i in range(len(plan)):
    for j in range(len(direction)):
        if plan[i] == direction[j]:
            px = x + dx[j]
            py = y + dy[j]            
            break
    if py<1 or py>N or px>N or px<1:       
        continue
    x,y =px, py    
print(x,y)

이동 관련 완전 탐색의 경우 이동에 대한 경우를 리스트 로 만들어 놓고 이동했을 때의 변수를 따로 선언 해서 이동연산 후의 위치가 조건에 맞으면 본 위치에 대입하고 아니면 넘어가는 형식을 이용한다는 것을 기억해두자.

문제 : 시각

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

  • 첫째 줄에 정수 N이 입력된다. (0 <= N <= 23)
  • 3이 하나라도 포함되는 모든 경우의 수를 출력
입력 예시
5

출력 예시
11475

풀이

N = int(input())
count=0
for hour in range(N+1):
    for min in range(60):
        for sec in range(60):
            if '3' in str(hour)+str(min)+str(sec):
                count+=1
print(count)

해당 숫자가 포함되었는지 확인할때는 str을 이용해 문자열로 변환시키고 in을 활용하자.
00시 00분 00초 부터 23시 59분 59초까지의 모든 경우는 86,400가지밖에 존재하지 않기 때문에 파이썬의 문자열 연산을 이용해 하나씩 세서 쉽게 풀 수 있다.


5. 실전문제

문제 : 왕실의 나이트

체스판 8 * 8 에서 나이트는 다음과 같이 이동할 수 있다.

  • 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동
  • 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동
  • 행은 1~8 열은 a~h로 두고 위치는 a1(1행1열) 이런식으로 나타낸다.

입력 조건 : 첫째 줄에 현재 나이트의 위치를 입력
출력 조건 : 첫째 줄에 나이트가 이동할 수 있는 경우의 수를 출력

입력 예시
a1
출력 예시
2

풀이

a = input()

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

x = int(a[1]) - 1
y = ord(a[0]) - ord('a')

count = 0
for i in range(len(dx)):
    px = x + dx[i]
    py = y + dy[i]
    if 0 <= px and px <= 7 and 0 <= py and py <= 7:
        count += 1
print(count)

이동 관련 완전 탐색의 경우 이동에 대한 경우를 리스트 로 만들어 놓고 이동했을 때의 변수를 따로 선언 해서 이동연산 후의 위치가 조건에 맞으면 본 위치에 대입하고 아니면 넘어가는 형식을 이용한다는 것을 기억해두자. 이렇게 활용하지 않으면 일일이 조건문으로 나눠야하므로 코딩이 매우 길어진다.

cf) 문자 코드를 다루는 ord() 함수와 chr()함수
내장 함수 ord()는 단일한 문자를 전달받아 그 문자의 유니코드 코드 포인트를 정수로 반환한다. 예를 들어 ord(‘a’)는 정수 97을 반환한다. 또 이 함수의 변환을 거꾸로 수행하는 내장 함수는 chr()이다. 예를 들어 chr(97)은 문자 ‘a’를 반환한다.

문제 : 게임 개발

게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. n * m 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중에 한 곳을 바라본다. 맵의 각 칸은 (A,B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 수, B는 서쪽으로부터 떨어진 칸의 수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다. 캐릭터가 움직이는 메뉴얼은 다음과 같다.

  1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 갈 곳을 정한다.
  2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향으로 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 하고 1단계로 돌아간다.
  3. 만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈수 없는 경우에는 움직임을 멈추고 종료한다.

입력조건

  • 첫째 줄에 맵의 세로 크기와 가로 크기를 공백으로 구분하여 입력(N>=3, M<=50)
  • 둘째 줄에 게임 캐릭터가 있는 좌표(A, B)와 바라보는 방향d가 각각 서로 공백으로 구분하여 주어진다.
    • d 방향은 0(북쪽), 1(동쪽), 2(남쪽), 3(서쪽)이다.
  • 셋째 줄부터 육지인지 바다인지 입력한다. N개의 줄에 맵의 상태가 북쪽부터 남쪽 순서대로, 각 줄의 데이터는 서쪽부터 동쪽 순서대로 주어진다. 맵의 외곽은 항상 바다이다.
    • 0(육지), 1(바다)
  • 처음에 캐릭터의 위치는 항상 육지이다.

출력조건

  • 첫째 줄에 이동을 마친 후 캐릭터가 방문한 칸의 수를 출력한다.
입력 예시
4 4  # 4*4 맵 생성
1 1 0  # (1,1)에 북쪽을 바라보는 캐릭터
1 1 1 1 # 첫 줄은 모두 바다
1 0 0 1 # 바다 육지 육지 바다
1 1 0 1 # 바다 바다 육지 바다
1 1 1 1 # 모두 바다

출력예시
3

풀이

N,M = map(int,input().split())
A,B,d = map(int,input().split())
game_map = [] # 게임 맵 리스트 만들기, 나중에 append로 붙이기
dn = [-1,0,1,0] # 세로
dm = [0,1,0,-1] # 가로
count=0
rotate =0 # 회전횟수
for _ in range(N): # 맵 완성
    game_map.append(list(map(int,input().split())))

while True:    
    if rotate ==4:        
        pn = A + dn[(d+2)%4]
        pm = B + dm[(d+2)%4] 
        if game_map[pn][pm] == 2:
            game_map[A][B] = 2 # 이동하기 전 위치 2로 바꾸기
            A=pn
            B=pm
            rotate=0
            count+=1
            continue
        break        
    d = (d+3)%4    
    pn = A + dn[d]
    pm = B + dm[d]
    rotate +=1
    if game_map[pn][pm] == 0:
        game_map[A][B] =2 # 가본곳
        A=pn
        B=pm
        count+=1
        rotate = 0    

print(count)

전형적인 시뮬레이션 문제이다. 일반적으로 방향을 설정해서 이동하는 문제 유형에서는 dx, dy라는 별도의 리스트를 만들어 방향의 이동량을 정하고 활용하는 것이 효과적이다.


© 2021. By Backtony