구현

구현 알고리즘

• 구현 유형의 문제는 ‘풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제’를 의미

  ex) 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제

  ​ 특정 소수점까지 출력해야 하는 문제

  ​ 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱) 문제 등

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

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

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

파이썬에서 리스트 크기

int 자료형 데이터 개수에 따른 메모리 사용량

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

대체로 코딩 테스트에서는 128 ~ 512MB로 메모리를 제한하는데 데이터 처리량이 많을 때는 메모리 제한을 고려해야 한다.

시간제한

파이썬으로 제출한 코드가 1초에 2,000만 번의 연산을 수행한다고 가정하고 풀면 무리가 없다.

시간 제한이 1초이고, 데이터의 개수가 100만개인 문제가 있다면 일반적으로 시간 복잡도 O(NlogN)이내의 알고리즘을 이용하여 문제를 풀어야 한다.

따라서 시간제한과 데이터의 개수를 먼저 확인한 뒤에 어느 정도의 시간 복잡도의 알고리즘으로 작성해야 풀 수 잇을 것인지 예측할 수 있어야 한다.

예제) 상하좌우

• 여행가 A는 N × N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 × 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)이다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있다
• 계획서에는 하나의 줄에 띄어쓰기를 기준으로 L, R, U, D 중 하나의 문자가 반복적으로 적혀있다. 각 문자의 의미는 다음과 같다
  • L: 왼쪽으로 한 칸 이동
  • R: 오른쪽으로 한 칸 이동
  • U: 위로 한 칸 이동
  • D: 아래로 한 칸 이동
• 이때 여행가 A가 N × N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다 예를 들어 (1, 1)의 위치에서 L 혹은 U를 만나면 무시된다 다음은 N = 5인 지도와 계획이다

입력 조건: 첫째 줄에 공간의 크기를 나타내는 N이 주어진다. (1<= N <=100)

​ 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다.(1<= 이동 횟수 <=100)

출력 조건: 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표(X,Y)를 공백을 기준으로 구분하여 출력

# 입력예시
5
R R R U D D

# 출력예시
3 4

해결방법

1. L R U D에 따른 이동 방향에 따라 x와 y의 결과값을 리스트에 넣어둔다.
2. 이동 횟수에 따라 구현하면서 O(N)의 시간 복잡도로 문제를 푼다.

n = int(input())
move_plan = list(map(str, input().split()))

# L R U D에 따른 이동 방향
move = ['L','R','U','D']
ny = [-1,1,0,0]
nx = [0,0,-1,1] 

x = 0
y = 0
for plan in move_plan:
    for i in range(len(move)):
        if plan == move[i]:
            mx = x + nx[i]
            my = y + ny[i]
    if mx < 0 or mx > (n-1) or my < 0 or my > (n-1): # 공간을 벗어나는 경우 무시
        continue
    x, y = mx, my
    print(x,y)

print(x+1, y+1)