[Algorithms] 구현

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

→ 결국 모든 범위의 코딩테스트 문제 유형을 포함하는 개념!

⁂ 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제! 피지컬이 중요!

 

ex) 크게 2가지 유형으로 나눌 수 있음

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

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

• 파이썬에서는 프로그래머가 직접 자료형을 지정할 필요X
• 매우 큰 수의 연산 또한 기본으로 지원
• but, 실수형 변수는 다른 언어와 마찬가지로 유효 숫자에 따라 연산 결과가 원하는 값이 나오지 않을 수 있음!

파이썬에서 리스트 크기

• 리스트 이용시 코딩테스트의 메모리 제한을 고려해야 함!
• int 자료형 데이터의 개수에 따른 메모리 사용량

데이터의 개수 (리스트의 길이)	메모리 사용량
1,000	약 4KB
1,000,000	약 4MB
10,000,000

채점 환경

일반적으로 시간 제한이 1초이고 데이터의 개수가 100만 개인 문제

→ 시간복잡도 O(NlogN)이내의 알고리즘 이용해야 함!

• 시간 제한: 1초
• 메모리 제한: 128MB

구현 문제에 접근하는 방법

In 파이썬, 구현 난이도는 쉬운 편, but, 프로그램 실행 시간은 길다!

파이썬에선 API 개발 문제 접근 easy!

예제 4-1. 상하좌우

• N X N 크기의 정사각형 공간, 상하좌우 움직일 수 있음! but, 공간을 벗어나는 움직임은 무시됨!
• 최종적으로 도착할 지점의 좌표 (X,Y)를 출력하면 됨!
• 일련의 명령에 따라서 개체를 차례대로 이동시키는 시뮬레이션 유형!

n = int(input()) # 공간의 크기 N 입력
x,y = 1,1 # 시작점
plans = input().split() # 이동 경로 입력

# L,R,U,D 에 따른 이동 방향
dx = [0,0,-1,1] # L,R,U,D x좌표
dy = [-1,1,0,0] # L,R,U,D y좌표
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)

→ 연산 횟수는 이동횟수에 비례

→ 시간 복잡도 : O(N)

예제 4-2 시각

• 정수 N이 입력되면 00시 00분 00초 부터 N시 59분 59초까지의 모든 시각 중 3이 하나라도 포함되는 모든 경우의 수 구하기
• 전체 경우의 수 86,400가지! → 문자열 연산을 이용해도 시간 제한 2초안에 해결 가능!
• 완전 탐색 유형 : 가능한 경우의 수를 모두 검사해보는 방법! → 데이터 개수가 큰 경우엔 bad
• 경우의 수가 100만개 이하일때 사용하면 적절!

# 정수 N이 입력되면 0시00분00초~ N시 59분 59초까지 모든 시각 중 3이 하나라도 포함되는 모든 경우의수

N = int(input())
count= 0

for i in range(N+1):
    for s in range(60):
        for j in range(60):
            if '3' in str(i) + str(s) + str(j) :
                count += 1

print(count)

 

2. 실전 문제 - 왕실의 나이트

• 8 X 8 좌표 평면, 나이트는 L자 형태로만 이동할 수 있고, 정원 밖으론 못 나감! 2가지 경우로 행동

1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기
2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기

나이트의 위치가 주어졌을 때, 나이트가 이동할 수 있는 경우의 수를 출력!

행위치: 1~8 / 열 위치 : a ~ h

# 미리 이동할 수 있는 방향 8가지를 배열에 저장해주기!
# 체스판은 8 X 8 크기 // 도착지가 체스판 안이면 경우의 수 +1

count = 0

now = input()
now_x = int(ord(now[0])) - int(ord('a')) + 1 
now_y = int(now[1])


steps = [(-2,-1), (-2,1), (2,-1),(2,1),(1,2),(1,-2),(-1,2),(-1,-2)]

for s in range(8):
    dx = now_x + steps[s][0]
    dy = now_y + steps[s][1]
    if (dx > 1 and dx < 8) and (dy > 1 and dy < 8) :
        count += 1

print(count)

3. 실전 문제 - 게임 개발

• N X M 크기의 직사각형
• 맵의 각 칸은 (A,B) , A: 북쪽으로부터 떨어진 칸의 개수, B: 서쪽으로부터 떨어진 칸의 개수
• 바다로 된 곳에는 갈 수 없음. 캐릭터는 상하좌우로 움직임

1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 갈 곳을 정한다
2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다.
3. 만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.

# 내 풀이
# NxM 크기의 직사각형
# 캐릭터는 동서남북 중 한 곳을 바라본다
# 맵의 각 칸 - (A,B)
#- 현재 위치에서 왼쪽 방향부터 차례대로 갈 곳을 정한다
#- 왼쪽 방향에 가보지 않은 칸이 있으면 왼쪽 회전, 없으면 왼쪽 회전만하고 1로
#- 네 방향 모두 가본칸이거나 바다이면 방향 유지한채로 한칸 뒤
#- 방향 d : 0 = 북쪽, 1 = 동쪽, 2 = 남쪽, 3 = 서쪽
#- 셋째줄부터 맵이 육지인지 바다인지에 대한 정보 주어짐 : 0=육지, 1=바다 

N, M = map(int, input().split())
A, B, d = map(int, input().split())

# 게임 환경 맵 입력받기
array = []

for i in range(N):
    array.append(list(map(int, input().split())))

direction = [(-1,0),(0,1), (1,0), (0,-1)] # 반시계방향 서남동북

count = 1
turn_count = 0

dx = A
dy = B

for k in range(N * M):
    for s in range(4):
        ix = dx + direction[s-d][0] 
        iy = dy + direction[s-d][1]
        if array[ix][iy] == 0:
            dx = ix
            dy = iy
            array[ix][iy] = 1
            count += 1
            d = abs(3-turn_count)
            turn_count = 0
            break
        else:
            turn_count += 1

        if turn_count == 4:
            ix = dx + direction[1-d][0] # 북동남서 -> 북서남동으로 바라봐야함 
            iy = dy + direction[1-d][1]
            if array[ix][iy] == 0:
                dx = ix
                dy = iy
                array[ix][iy] = 1
                count += 1
                break
            
print(count)

 

[참고자료]

• 이것이 취업을 위한 코딩 테스트다 with 파이썬 / 나동빈