2일차 - 구현

이 책에서는 완전 탐색, 시뮬레이션 유형을 모두 '구현' 유형으로 묶어서 다루고 있다.

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

시뮬레이션은 문제에서 제시한 알고리즘을 한 단계식 차례대로 직접 수행하는 해결방법이다.

 

코딩테스트나 여러 구현문제를 풀면서 느꼈던 점은

자료구조가 있으면 수행시간을 단축시킬 수 있는 장점이 있지만,

구현문제는 순수 피지컬 싸움이란것을 많이 느꼈다.

 

해당 책에서도 별도의 이론이 없다.

 

예제 4-1 상하좌우

유저의 시작좌표는 (1,1)이고 주어진 명령(R, L, U, D)을 통해서 이동된 좌표를 구하는 문제이다.

아래는 내가 작성한 코드이지만, 책의 저자는 더 깔끔하게 코드를 작성했다.

L, R, U, D에 따른 이동 방향을 list를 통해 나타냈다. BFS/DFS에서도 이런 식의 코드를 많이 봤는데,

방향이 나오는 문제는 아래 방식처럼 작성할것을 습관화하자.

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

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

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

 

num = int(input())
commands = list(input().split())

x = y = 1

for command in commands:
    if command == 'R' and x < num : 
        x += 1
    elif command == 'L' and x > 1:
        x -= 1
    elif command == 'U' and y > 1:
        y -= 1
    elif command == 'D' and y < num:
        y += 1

print(y, x)

 

 

예제 4-2 시각

00시 00분 00초부터 입력받은 N시 59분 59초까지 중 3이 포함된 경우의 수를 구하는 문제이다.

hour = int(input())

answer = 0

for i in range(hour + 1):
    for j in range(60):
        for k in range(60):
            if '3' in str(i) + str(j) + str(k):
                answer += 1
print(answer)

 

 

예제 4-3 왕실의 나이트

체스 게임을 하면 나이트의 움직임은 크게 8가지이다. 입력받은 좌표로부터 몇가지의 움직임을 가질 수 있는지 구현하는 문제이다.

position = input()
row = int(position[1])
column = int(ord(position[0])) - int(ord('a')) + 1

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

answer = 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:
        answer += 1

print(answer)

 

 

책을보면서 global이라는 키워드를 발견했다.

main함수에서 선언한 변수를 지역함수에서 사용하고싶을때 사용하는 키워드이다.

아래 코드가 예시이다.

direction = 1

def turn_left():
	global direction
    print(direction)