[이것이 코딩 테스트다] CH04. 구현

<구현 시 고려해야 할 메모리 제약 사항>

• C/C++에서 변수의 표현 범위
• Python에서 리스트 크기

- 보통 Python이 C언어에 비해 난이도는 낮지만, 동작 속도가 느리다.

---

예제 4-1. 상하좌우

시뮬레이션 유형: 개체를 차례대로 이동시킴.

여행자 A가 가장 왼쪽 위 = (1,1)에서 상, 하, 좌, 우 방향으로 이동하는 계획서에 따라 도착 지점의 좌표를 출력하시오. (단, N*N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다.)

 

<내가 푼 답안>

X, Y = 1, 1
N = int(input())
plans = input().split

for moving in plans:
    if moving == 'L':
    	if Y ==1:
        	continue #해당 반복 벗어남.
        Y -= 1
    elif moving == 'R':
    	if Y == N:
        	continue
        Y += 1
    elif moving == 'U':
    	if X == 1:
        	continue
        X -= 1
    else:
    	if X == N:
        	continue
        X += 1

print(X,Y)

<책 답안>

n = int(input())
x, y = 1, 1
plans = input().split()

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

시간 복잡도 = O(N), 연산 횟수는 이동 횟수에 비례하게 된다.

point: 각 방향을 정의한다.

※ 행렬 표현이라 2차원 좌표 평면 x, y와는 조금 다를 수 있다. ※

 

예제 4-2. 시각

완전 탐색 알고리즘: 가능한 경우의 수를 모두 검사해보는 탐색 방법

00시 00분 00초 ~ N시 59분 59초까지의 모든 시각 중에 3이 포함된 경우의 수

 

<내가 푼 답안>

## 경우의 수 문제 풀 듯이 구현했음.
N = int(input())

if N <3:
	result = (N+1)*6*10*6*10 - (N+1)*5*9*5*9
else:
	result = (N+1)*6*10*6*10 - N*5*9*5*9

print(result)

<책 답안>

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)

point: 하나하나 다 살펴봄.

 

실전 4-2. 왕실의 나이트

1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기

2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기

8*8 좌표 평면 상에서 현재 나이트의 좌표가 주어졌을 때 나이트는 1 또는 2의 방법으로 밖에 이동하지 못하는 경우, 이동할 수 있는 경우의 수를 구하여라

 

input_data = input()

row = int(input_data[1])
column = int(ord(input_data[0])) - int(ord('a')) + 1 #ord('문자'): 유니코드 정수를 반환
steps = [(-2,-1), (-2,1), (-1,-2), (-1,2), (1,-2), (1,2), (2,-1), (2,1)] #가능한 모든 경우의 수

result = 0
for step in steps:
    next_row = row + step[0]
    next_col = column + step[1]
    if next_row < 1 or next_row > 8 or next_col < 1 or next_col > 8:
    	continue
    result += 1
    
    """
    if next_row >= 1 and next_row <= 8 and next_col >= 1 and next_col <= 8:
    	result += 1
    """

print(result)