코딩테스트 - Chapter 04

구현

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

1. 아이디어를 코드로 바꾸는 구현

구현 (Implementation)

• 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정

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

상하좌우

💡 명령에 따라 개체를 차례대로 이동시킨다는 점에서 시뮬레이션 유형 = 구현이 중요

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

move_type = ['L', 'R', 'U', 'D']
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

# 이동 계획 확인
for plan in plans :
    for i in range(len(move_type)) :
        if plan == move_type[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)

시각

💡 3중 반복문 이용. 완전 탐색 유형 = 가능한 경우의 수를 모두 검사해보는 탐색 방법

n = int(input())

count = 0

# 0 부터 n까지 탐색
for i in range(n + 1) :
    # 0 부터 59까지 탐색
    for j in range(60) :
        for k in range(60) :
            if '3' in str(i) + str(j) + str(k) :
                count += 1

print(count)

2. 왕실의 나이트

왕실의 나이트

💡 반복문 처리

data = input() # 행(문자) + 열(숫자)
row = int(data[1])

# ord() : 문자의 유니코드 값 반환
# 입력받은 문자 ASCII - a의 ASCII + 1
column = int(ord(data[0])) - int(ord('a')) + 1

# 나이트가 이동할 수 있는 8가지 방향
steps = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]

count = 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 :
        count += 1
    
print(count)

3. 게임 개발

게임 개발

💡 시뮬레이션 문제

n, m = map(int, input().split()) # n X m

d = [[0] * m for _ in range(n)]
# 현재 캐릭터의 x, y 좌표
x, y, direction = map(int, input().split())
d[x][y] = 1 # 현재 좌표 방문 처리

array = []
for i in range(n) :
    array.append(list(map(int, input().split())))

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

def turn_left() :
    global direction
    direction -= 1
    if direction == -1 :
        direction = 3

count = 1
turn_time = 0

while True :
    turn_left()
    nx = x + dx[direction]
    ny = y + dy[direction]

    if d[nx][ny] == 0 and array[nx][ny] == 0 :
        d[nx][ny] = 1
        x = nx
        y = ny
        count += 1
        turn_time = 0
        continue
    else :
        turn_time += 1
    # 네 방향 모두 갈 수 없는 경우
    if turn_time == 4 :
        nx = x - dx[direction]
        ny = y - dy[direction]

        if array[nx][ny] == 0 :
            x = nx
            y = ny
        else :
            break
        turn_time = 0

print(count)