구현

구현

머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정.
이를 위해 언어의 문법을 정확히 알고 있어야 하며 문제의 요구사항에 어긋나지 않는 답안 코드를 실수 없이 작성해야 한다.

• 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제
• 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
• 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
• 적절한 라이브러리를 찾아서 사용해야 하는 문제

완전 탐색, 시뮬레이션은 ‘구현’ 유형으로 묶을 수 있다.
완전 탐색(Brute Force Search) : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계식 차례대로 직접 수행

구현 문제에 접근하는 방법

보통 구현 유형의 문제는 사소한 입력 조건 등을 문제에서 명시해주며 문제의 길이가 꽤 길다.
구현 유형의 문제는 C/C++나 Java로 문제를 풀 때 더 어렵게 느껴진다. 문자열을 처리하거나 큰 정수를 처리하는 문제가 출제되는 경우가 많은데, C/C++은 Python에 비하여 문자열 처리가 까다롭고, 큰 정수를 처리하는 라이브러리를 별도로 사용해야 하기 때문이다.

코딩 테스트 환경에서 점점 PyPy3를 지원하는 곳이 늘고 있다. PyPy3는 Python3의 문법을 그래도 지원하며, C/C++에 견줄만큼 Python3보다 실행 시간이 빠르다. 코딩 테스트 환경이 Python3만 지원하는지, 혹은 PyPy3도 지원하는지 확인하고 만약 PyPy3도 지원한다면 이를 이용하도록 한다.

C/C++에서 변수의 표현 범위

Python에서는 직접 자료형을 지정할 필요가 없으며 매우 큰 수의 연산 또한 기본으로 지원.
다만, Python에서의 실수형 변수는 다른 언어와 마찬가지로 유효숫자에 따라서 연산 결과가 원하는 값이 나오지 않을 수 있다.

---

상하좌우

문제 설명 :

풀이 방법 :

n = int(input())
curX, curY = 1, 1
plans = input().split()

# 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 = curX + dx[i]
            ny = curY + dy[i]
    # 공간을 벗어나면 무시
    if nx < 1 or ny < 1 or nx > n or ny > n :
        continue
    # 이동 후 좌표 업데이트
    curX, curY = nx, ny

print(curX, curY)

---

왕실의 나이트

문제 설명 :

문제 풀이 :

    # 현재 나이트의 위치 입력받기
user_input = input()
row = int(user_input[1])
col = int(ord(user_input[0])) - int(ord('a')) + 1 # ord() : ascii값으로 바꿔주는 함수

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

# 8가지 방향에 대하여 각 위치로 이동이 가능한지 확인
result = 0
for step in steps:
    next_row = row + step[0]
    next_cal = col + step[1]

    # 해당 위치로 이동이 가능하다면 result += 1
    if next_row >= 1 and next_row <= 8 and next_cal >= 1 and next_cal <= 8 :
        result += 1

print(result)

---

게임 개발

문제 설명 :

문제 풀이 :

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

# 전체 맵 정보를 입력받기
array = []
for i in range(n) :
    array.append(list(map(int, input().split())))

array[x][y] = 2 # 현재 좌표 방문 처리

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

# 왼쪽으로 회전 
def turn_left() :
    global direction
    direction -= 1
    if direction == -1 : # 북쪽이었으면 -1이 될 테니까 3으로(서쪽으로)
        direction = 3

# 시뮬레이션 시작
cnt = 1
turn_time = 0

while True :
    turn_left()
    nx = x + dx[direction]
    ny = y + dy[direction]
    
    # 회전 이후 정면에 가보지 않은 칸이 존재한다면, 이동
    if array[nx][ny] == 0 : 
        array[nx][ny] = 2
        x = nx
        y = ny
        cnt += 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
            turn_time = 0
        # 뒤로 갈 수 없다면 종료
        else :
            break
print(cnt)