[구현] Chapter 04 구현 (p.103 ~ 121)

<이것이 취업을 위한 코딩테스트다 with 파이썬> 책의 내용을 정리한 것입니다.

 

이 책에서는 완전 탐색, 시뮬레이션 유형을 모두 '구현'의 유형으로 생각하여 다룬다.

완전 탐색: 모든 경우의 수를 다 계산하여 해결 하는 방법

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

 

파이썬에서는 일반적으로 정수의 범위를 고려하지 않아도 괜찮지만, 

C / C++ 의 경우는 정수의 범위를 고려해야 한다.

정수형 종류	자료형 크기	자료형 범위
int	4Byte	-2,147,483,648 ~ 2,147,483,648
long long	8Byte	-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,808
Biginteger (클래스)	가변	제한 없음

 

파이썬에서 리스트 크기

주로 128~512MB로 메모리를 제한하므로, 이를 고려하여 구현해야 한다.

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

 

따라서 리스트의 크기가 1,000만 이상인 리스트는 메모리 용량 제한이 있을 수 있음을 염두해야 한다.

 

[예제 4-1] 상하좌우 (P.110)

n = int(input())
plans = list(input().split())
x, y = 1, 1
nx, ny = 0, 0

#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 nx < 1 or nx > n or ny < 1 or ny > n:
            continue
        x, y = nx, ny

print(x, y)

 

[예제 4-2] 시각 (P.113)

n = int(input())
result = 0

for h in range(n + 1):
    for m in range(60):
        for s in range(60):
            if '3' in str(h) + str(m) + str(s):
                result += 1

print(result)

모두 확인하는 완전 탐색 알고리즘, 비효율적인 시간 복잡도 가짐

 

[예제 2] 왕실의 나이트 (P.115)

position = list(input())
alphabet_dict = {'a':1, 'b':2, 'c':3, 'd':4, 'e':5, 'f':6, 'g':7, 'h':8}
x, y = alphabet_dict[position[0]], int(position[1])
# x = int(ord(position[0])) - int(ord('a')) + 1 으로 구할 수 있음(유니코드 이용)

#이동 가능한 동선
dx = [-2, -2, 2, 2, -1, -1, 1, 1]
dy = [-1, 1, -1, 1, -2, 2, -2, 2]

result = 0

for i in range(8):
    nx = x + dx[i]
    ny = y + dy[i]
    if nx <1 or ny <1 or nx > 8 or ny > 8:
        continue
    result += 1

print(result)

 

[예제 3] 게임 개발 (P.118)

n, m = map(int, input().split())
x, y, direction = map(int, input().split())

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

# 캐릭터가 이동하여 방문한 곳 check용
check = [[0] * m for _ in range(n)]
check[x][y] = 1

# 북, 동, 남, 서 방향
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]


# 북->서->남->동->북 순서로 회전해야 함
def turn_left():
    global direction
    direction -= 1
    if direction < 0:
        direction += 4


result = 1
turn_time = 0
while True:
    turn_left()
    nx = x + dx[direction]
    ny = y + dy[direction]
    # 매뉴얼 1번 구현
    if board[nx][ny] ==0 and check[nx][ny] == 0:
        result += 1
        x, y = nx, ny
        check[nx][ny] = 1
        turn_time = 0
        continue
	# 매뉴얼 2번 구현
    else:
        turn_time += 1
	# 매뉴얼 3번 구현
    if turn_time == 4:
        nx = x - dx[direction]
        ny = y - dy[direction]

        if board[nx][ny] == 0:
            x, y = nx, ny
        else:
            break
        turn_time = 0
            
print(result)