[Algorithm 이론] 구현(Implementation)

2024-06-10

머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정인 구현(Implementation)에 대해서 알아보자.

구현

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

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

[구현 시 고려해야할 메모리 제약 사항]

파이썬에서 리스트 크기
- 파이썬에서 여러 개의 변수를 사용할 때 리스트를 이용
  -> BUT!! 메모리 제한있음
- 수백만 개 이상의 데이터 처리하는 문제 -> 메모리 제한 염두해야함.
- 크기가 1,000만 이상인 리스트가 있다면 메모리 제한 걸릴 수 있음

데이터 개수(리스크 길이)	메모리 사용량
1,000 (천)	약 4KB
1,000,000 (백만)	약 4MB
10,000,000 (천만)	약 40MB

예제 4-1. 상하좌우 (시뮬레이션 문제)

여행가 A는 (N * N) 크기의 정사각형 공간 위에 서 있다. 이 공간은 (1 * 1) 크기의 정사각형들로 나누어져 있다.
가장 왼쪽 위 좌표 = (1, 1) / 가장 오른쪽 아래 좌표 (N, N)
A는 상, 하, 좌, 우 이동 가능, 시작 좌표는 항상 (1, 1)
L : 왼쪽으로 / R : 오른쪽으로 / U : 위쪽으로 / D : 아래쪽으로 한 칸 이동
$N*N$ 크기의 공간을 벗어나는 움직임 무시
계획서가 주어 졌을 때 A가 최종적으로 도착할 지점의 좌표 출력

[입력 조건]
첫째 줄 : 공간의 크기를 나타내는 N이 주어진다
둘째 줄 : A가 이동할 계획서 내용

[출력 조건]
A가 최종적으로 도착할 지점의 좌표를 공백으로 구분하여 출력

풀이-1

n = int(input())
plans = input().split()

# 시작 지점
x, y = 1, 1

# LRUD 이동 방향
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
move_type = ['L', 'R', 'U', 'D']

# 계획서에 따른 이동
for plan in plans:
    i = move_type.index(plan) # 어떤 이동인지 찾기

    nx = x + dx[i]
    ny = y + dy[i]

    # 공간 벗어나는 경우 pass
    if nx < 1 or nx > n or ny < 1 or ny > n:
        # continue를 함으로써 벗어나는 경우 '이동한 것을 적용'을 실행하지 않고 다음 for문 실행
        continue     

    # 이동한 것을 적용
    x, y = nx, ny

print(x, y)

3 4

풀이-2

n = int(input())
plans = input().split()

x, y = 1, 1
nx, ny = 1, 1
# 위 아래가 x좌표 -+1
# 좌 우가  y좌표 -+1
for plan in plans:
    if plan == 'R':
        ny = y + 1
    if plan == 'L':
        ny = y - 1
    if plan == 'U':
        nx = x - 1
    if plan == 'D':
        nx = x + 1
    
    if ny < 1 or ny > n or nx < 1 or nx > n:
        nx, ny = x, y

    x, y = nx, ny

print(x, y)

3 4

예제 4-2. 시각 (완전 탐색 문제)

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중 3이 하나라도 포함되는 모든 겨우의 수를 구하는 프로그램 작성

[입력조건]
첫째 줄 : 정수 N 입력 ($0<=N<= 23$)

[출력 조건]
00시 00분 00초 ~ N시 59분 59초까지의 모든 시각중 3이 하나라도 포함되는 모든 경우의 수 출력

풀이

def count_3(h):
    result = 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):
                    result += 1
    return result

count_3(5)

실전문제 4-1. 왕실의 나이트

왕실 정원 = 체스판과 같은 $8*8$ 좌표 평면
특정한 한 칸에 나이트가 서 있음 -> L자 형태로만 이동(정원 밖으로 나갈 수 없음)
- 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동
- 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동
나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램 작성

[입력 조건]
첫째 줄 : 현재 나이트가 위치한 고의 좌표를 나타대는 문자열 입력(열, 행)

[출력 조건] 나이트가 이동할 수 있는 경우의 수 출력

풀이

input_data = input()

first_loc = int(ord(input_data[0])) - int(ord('a')) + 1 # 문자열을 수치화(유니코드 정수)하기 위해
                                                        # int(ord('a')) = 97 
                                                        # (1, 1)이 가장 작은 좌표이므로 마지막에 +1
second_loc = int(input_data[1])

# 움직일 수 있는 경우의 수 = 8 가지
moves = [(2, 1), (2, -1), (-2, 1), (-2, -1) , (-1, 2), (1, 2), (-1, -2), (1, -2)] 
result = 0

for move in moves:
    first_loc_move = first_loc + move[0]
    second_loc_move = second_loc + move[1]

    if 0 < first_loc_move < 9 and 0 < second_loc_move < 9: # 좌표가 범위 안에 있으면
        result += 1

print(result)

실전문제 4-2. 게임 개발

게임 캐릭터가 맵 안에서 움직이는 시스템 개발
맵은 $N*M$ 크기의 직사각형, 각각의 칸은 육지 or 바다
- 바다로 된 곳은 이동 불가
- 상하좌우로 움직일 수 있음
캐릭터는 동서남북 중 한 곳을 바라본다.
각 칸 (A, B) : A = 북쪽으로부터 떨어진 칸의 개수 / B = 서쪽으로부터 떨어진 칸의 개수
캐릭터 움직임 메뉴얼
1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터
  차례대로 갈 곳을 정한다.
2. 캐릭터 바로 왼쪽 방향에 아직 가보지 못한 칸이 존재한다면,
  왼쪽 방향으로 회전한 다음 왼쪽으로 한칸 전진
  - 왼쪽 방향에 가보지 않은 칸이 없다면 왼쪽 방향으로 회전만하고 1)로 돌아감
3. 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우,
  바라보는 방향 유지한 채로 한칸 뒤로가고 1)로 돌아감
  - 뒤쪽 방향이 바다이면 stop!

[입력 조건]
첫째 줄: 맵의 세로크기 N과 가로크기 M을 공백으로 구분하여 입력 (3 <= 3, M <= 50>)
둘째 줄: 캐릭터가 있는 좌표와 바라보고 있는 뱡항 공백으로 구분하여 입력 (북:0/동:1/남:2/서:3)
셋째 줄: 맵이 육지 안지 바다인지에 대한 정보 (맵 외곽은 항상 바다, 육지:0/바다:1)

[출력 조건]
캐릭터가 방문한 칸의 수

Tip!!

문제에서 요구하는 내용을 오류 없이 성실하게 구현
방향을 설정해서 이동하는 문제 : dy, dy라는 별로 리스트를 만들어 방향을 정하는 것이 효과적

풀이

# n, m : 행의 수, 열의 수
# x, y, direction : 현재 좌표 , 바라보고 있는 방향
n, m = map(int, input().split())
x, y, direction = map(int, input().split())

# 방문한 위치 저장하기 위한 배열
d = [[0] * m for _ in range(n)] 

# 현재 위치는 방문했으므로 1로 변경(0이면 방문안한 곳)
d[x][y] = 1

# 실제 맵 정보 가져오기 ----- [[1, 0, 0, 0], [0, 1, 1, 0]] 2차 배열 형태임.
array = []
for i in range(n):
    array.append(list(map(int, input().split())))

# 방향을 정의해야 함
# 북, 동, 남, 서 (문제에 이 순서대로 나옴) - 이 순서대로 direction 지정할 예정
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 왼쪽 회전 (조건에 다라서 왼쪽으로 회전하는 경우 있음 - 시뮬레이션 가기전 미리 함수로 생성)
def turn_left():
    global direction
    direction += -1

    if direction == -1:
        direction = 3

# 시뮬레이션 start
turn_time = 0      # 4가 되면 뒤로가야함.
count = 1          # 방문한 칸 수 (현재 있는 곳도 방문했으므로 1부터 시작)

while True:
    # 왼쪽 회전
    turn_left()

    nx = x + dx[direction]
    ny = y + dx[direction]

    # 회전하고 정면에 가보지 않은 칸 존재 = 이동
    if d[nx][ny] == 0 and array[nx][ny] == 0:
        d[nx][ny] = 1  # 이동 했으니 이동한 좌표는 방문한 곳 = 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)

구현