[TAVE/이코테] ch04 구현 | 개념 정리 | 실전 문제

참고자료: 이것이 코딩테스트다

구현(Implementation)

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

👉🏻풀이를 떠올리는 것은 쉽지만 소스코드로 옮기는 과정이 어려운 문제를 칭한다.

• 완전탐색
• 시뮬레이션

👉🏻파이썬으로 코딩테스트를 치를 때 리스트 메모리 제한을 주의해야 한다. 리스트를 여러 개 선언할 수록 메모리 용량을 차지한다. 일반적인 코딩테스트에서 적은 크기의 메모리를 사용하는 것이 중요하다.

👉🏻1초에 2,000만번의 연산을 수행한다면 안정적인 코드라고 생각할 수 있다.

👉🏻PyPy가 Python3의 문법을 그대로 지원하며 실행 속도는 더 빠르다. 때문에 코딩 테스트 환경이 PyPy를 지원해준다면 이를 사용하자!

예제 - 상하좌우

def RLUD():
    location = [1, 1]
    num = int(input())
    direction_list = input().split()
    for direction in direction_list:
        if direction == 'R':
            if location[1] < num:
                location[1] += 1
        elif direction == 'L':
            if location[1] > 1:
                location[1] -= 1
        elif direction == 'U':
            if location[0] > 1:
                location[0] -= 1
        else:
            if location[0] < num:
                location[0] += 1
    print(location)

👉🏻 방향에 따라 이동하도록 하드코딩했다.

1. 미리 출발점 좌표를 location 리스트에 선언한다.
2. direction_list에 입력되는 방향을 저장하고 for문을 돌리면서 location 좌표를 옮겼다.

예제 - 시각

👉🏻하루의 모든 초를 세어도 86,400초이므로 경우의 수가 100,000개 이하이므로 문자열 연산을 이용해도 2초 안에 해결할 수 있다.

def book():
    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)

✍🏻때문에 3중 for문을 이용하면 풀 수 있다.

실전 - 왕실의 나이트

#실패 코드
def getLocationOfNight():
    current_location = input()
    direction_list = ['vertical', 'horizontal']
    movement_list = [1, 2]

    count = 0
    for direction_idx, direction in enumerate(direction_list):
        for movement in movement_list:
            if direction == 'vertical':
                pass

👉🏻수평과 수직 이동을 알파벳 그대로 받아들이려고 하니 어려웠다.. 책을 보니 책은 알파벳도 바로 좌표로 나타내서 푸는 것에 영감을 받아 다시 코드를 짜보았다.

def getLocationOfNight2():
    input_data = input()
    current_location = [int(ord(input_data[0])) - int(ord('a')) + 1, int(input_data[1])]

    movement_list = [(-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)]
    count = 0
    for movement in movement_list:
        location_x = current_location[0] + movement[0]
        location_y = current_location[1] + movement[1]
        if location_x < 1 or location_x > 8:
            pass
        elif location_y < 1 or location_y > 8:
            pass
        else:
            count += 1

    print(count)

1. current_location에 Input값을 리스트로 저장했다. 이때 알파벳은 ord함수를 이용해 숫자로 변환해 저장했다.
2. movement_list에 움직임을 저장했다. 첫 번째 인덱스가 수평으로 이동할 때, 두 번째 인덱스가 수직으로 이동할 때이다.
3. for문을 돌리면서 움직였을 때 위치를 각각 location_x와 location_y에 저장했다. 그리고 이 값들이 1 이상, 8 이하인지 확인하고 맞다면 count에 1씩 더했다.

실전 - 게임 개발

#왼쪽으로 회전
def turn_left():
    global direction
    direction -= 1
    if direction == -1:
        direction = 3

def book():
    n, m = map(int, input().split())

    d = [[0] * m for _ in range(n)] #4*4 육지를 만듦
    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] 

    count = 1
    turn_time = 0
    while True:
        turn_left()
        nx = x + dx[direction]
        ny = y + dy[direction]
book()

👉🏻일반적으로 방향을 설정해서 이동하는 문제 유형에서는 dx, dy라는 별도의 리스트를 만들어 방향을 만드는 것이 효과적이다.