구현 알고리즘 (Implementation Algorithm)

구현

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

   -> 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념

   -> 프로그래밍 문법 숙지, 라이브러리 사용 경험을 늘려야 함.

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

· 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행

 

 

메모리 제약 사항

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

   (int 4바이트, long 8바이트 -> 파이썬 X, 자바 BigInteger, C++ 외부 라이브러리 필요)

- 파이썬에서 리스트 크기

    (데이터의 개수 1000 -> 메모리 4KB / 백만 -> 4MB / 천만 -> 40MB)

 

 

채점 환경

- 파이썬은 C/C++에 비해 동작 속도 느림. 1초에 2,000만 번의 연산을 수행한다고 가정하면 크게 무리 없음.

- 시간 제한 1초, 데이터의 개수 100만 개 -> O(NlogN)

- 이처럼 알고리즘 문제를 풀 때는 시간 제한과 데이터의 개수를 먼저 확인한 후 어느 정도 시간 복잡도로 작성할지 예측

 

 

구현 문제에 접근하는 방법

- 보통 구현 유형의 문제는 사소한 입력 조건 등을 문제에서 명시해주며 문제의 길이가 꽤 긴 편임.

- 파이썬은 구현 난이도는 쉬운 편이지만 프로그램 실행 시간이 긴 편. (↔ C/C++)

- Pypy3는 파이썬3의 문법 지원, 실행속도 빠름.

- API 개발 문제 (+ 웹 서버, 데이터 분석에 대한 지식)

 

 

예제1. 상하좌우 

- 내 코드: L, R, U, D 하나하나 비교해서 연산함.

n = int(input())
move = list(input().split())

x = 1
y = 1

for i in move:
    if i == 'L':
        if y != 1:
            y -= 1
    elif i == 'R':
        if y != n:
            y += 1
    elif i == 'U':
        if x != 1:
            x -= 1
    else:
        if x != n:
            x += 1

print(x, y)

 

- 교재 코드: 배열을 이용해서 L, R, U, D 비교해서 연산 수행. 기존 값 + 수정값

n = int(input())
x, y = 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 = 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)

 

 

예제2. 시각

- 내 코드: 전체 시각 - 3이 포함되지 않는 시각 (숫자연산)

n = int(input())
a = (n+1) * 6 * 10 * 6 * 10

if n >= 3:
    b = n * 5 * 9 * 5 * 9
else:
    b = (n+1) * 5 * 9 * 5 * 9
    
print(a-b)

 

- 교재 코드: 모든 시각의 경우를 하나씩 모두 셈. 단순히 시각을 1씩 증가시키면서 3이 하나라도 포함되어 있는지 확인 -> 완전탐색

                   모든 경우는 86,400가지밖에 존재하지 않기 때문에 제한 시간 안에 문제 풀 수 있음.

h = int(input())

count = 0
for i in range(h+1):
    for j in range(60):
        for k in range(60):
            # 매 시각 안에 '3'이 포함되어 있다면 카운트 증가
            if '3' in str(i) + str(j) + str(k):
                count += 1

print(count)

 

 

예제3. 왕실의 나이트

- 내 코드: 최대 이동 횟수 8, 이동 배열 정의 -> 각각 x, y값에 더한 후 주어진 좌표를 벗어나면 이동 수를 감소시킴

p = input()
x = int(p[1])
y = int(ord(p[0]) - ord('a')) + 1

move = [(-2, 1), (-2, -1), (2, 1), (2, -1), (1, -2), (1, 2), (-1, -2), (-1, 2)]
count = 8

for i, j in move:
    mx = x - i
    my = y - j

    if mx < 1 or my < 1 or mx > 8 or my > 8:
        count -= 1

print(count)

처음엔 원래 각각 남은 칸의 변수 L, R, U, D를 정의해서 if문 돌려서 풀려고 했으나,,

스케치 한 후 막상 코드 짜려다 보니 코드가 너무 지저분해지고 비효율적이어서 다시 바꿈

 

- 교재 코드: 이동 배열 정의 후 각 위치로 이동이 가능한지 확인

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

# 나이트가 이동할 수 있는 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_column = column + step[1]
    # 해당 위치로 이동이 가능하다면 카운트 증가
    if next_row >= 1 and next_row <= 8 and next_column >= 1 and next_column <= 8:
        result += 1

print(result)

내가 푼 코드랑 비슷하다. 나는 돌아가면서 카운트를 감소시켰고 교재는 돌아가면서 카운트를 증가시킴.

 

 

예제4. 게임 개발

# N, M을 공백을 기준으로 구분하여 입력받기
n, m = map(int, input().split())

# 방문한 위치를 저장하기 위한 맵을 생성하여 0으로 초기화
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)

 

- 전형적인 시뮬레이션 문제 -> 별도의 알고리즘이 필요하기보다는 문제에서 요구하는 내용을 오류없이 성실하게 구현

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

- 2차원 리스트를 선언할 때는 컴프리헨션을 이용하는 것이 효율적

- 내 코드와 비교: 왼쪽으로 회전하는 부분을 함수로 처리함.

                           회전해서 전진하는 부분 방향 변수로 처리 가능... + 회전 횟수 변수 사용

                           (방향 리스트를 0, 1, 2, 3 순서로 만듦.

                            나는 for문으로 회전->전진해서 회전 방향으로 만듦.)

내 알고리즘,,