Python 알고리즘 - 구현 1탄:상하좌우

구현 문제의 핵심은 라이브러리 사용 경험이다.

 

부족하다면, 구현 유형의 문제를 풀 때 감이 오지 않을 것이다. 

 

예를 들어, n개의 원소가 들어 있는 리스트에서 r개의 원소를 뽑아 한 줄로 세우는 모든 경우(순열)를 구해야 하는 문제를 만난다고 가정해보자.

 

다양한 기능을 사용할 수 있겠지만, 간단하게 itertools (표준 라이브러리)로 쉽게 짤 수도 있다.

 

즉, 언어의 문법을 잘 이해하고 경험이 있어야만, 생각의 전환과 발상이 바로 떠오른다.

 

구현 유형은 2가지로 풀 수 있다.

 

첫째, 완전 탐색이다.

- 모든 경우의 수를 주저 없이 다 계산하느 해결 방법

 

둘째, 시뮬레이션이다.

- 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제이다

 

---

메모리 제약 사항

 

#1 기본적인 정수형은 4바이트이다.

 

표현 범위는 -2,147,483,648 ~ 2,147,438,647 이다.

 

+ 더 큰 정수형은 long long 이며, 8바이트이다.

+ BigInteger(클래스) 는 자료형의 크기가 가변적이며, 범위는 제한이 없다

 

위의 기준은 C와 C++ 기준이며, Python 에서는 자료형을 지정할 필요가 없다

다만, 유효숫자에 따라 연산 결과가 다르게 나올 수 있다는 점을 고려하면 된다.

 

유효숫자 다루기

 

알아야할 개념 : g, f, round함수

 

형식을 갖는 문자열을 만드는 연산자:     %

형식을 갖는 문자열을 만드는 메소드:     format()

위의 개념을 탑재하고서, 다음을 이해하자.

 

출처 : https://rfriend.tistory.com/328

1) f

부동소수형 실수 (floating point real number)

.2f : give 2 digits after the point

 

 

 

2) g

%f(부동소수형 실수)와 %e (소문자 'e' 지수 표기) 단축형

 

.1g : give 1 significant digits
.2g : give 2 significant digits

 

 

3) round

 

# d,f,g
print("%05d" %1)

print("%5d" % 1)

print("%5d" % 1234)

print("%.3f" % 1)

print("%.3f" % 123)

print("%.3f" %0.12345)

import math

print("%f" %math.pi)

print("%.3f" %math.pi) # f 소수점 이후로 3자리

print("%.3g" %math.pi) # g 전체 범위를 포함

 

 

print(math.pi)

print(round(math.pi))

print(round(math.pi, 2))

 

---

#2. 메모리 제한 - 리스트

 

코딩 테스트에서 주로 128 ~ 512 MB 로 메모리 제한이 걸린다. 수백만 개 이상의 데이터 처리시 문제가 될 수 있다.

그렇기에 int 자료형 데이터 개수 확인해야 하며, 별도의 자료형을 명시해줄 필요가 없다.

시스템 내부적으로는 다음 표에서 보여주는 것과 유사한 크기만큼 메모리를 차지한다.

 

 

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

리스트 길이가 1000인 경우, 4 KB

 

리스트 길이가 1,000,000 인 경우, 4 MB

 

리스트 길이가 10,000,000 인 경우, 40 MB

 

하지만, 문제를 풀때 최적화를 요구하는 것보다 완벽하게 solve 할 생각을 하는게 나한테 좋을 것 같다.

 

---

시간

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

1초에 2000만번~1억번 정도의 연산 처리할 수 있으므로, 감안하기~요즘은 Pypy3 가능함 <파이썬 3보다 빠름

 

---

 

1. 구현 - 상하좌우

 

문제 : 

N x N 크기의 정사각형 공간 위에서, 시작점의 좌표는 좌측맨위에 (1,1) 이다.

가장 오른쪽 아래 좌표는 (N,N) 이다. 시작점에서 상,하,좌,우 방향으로 이동할 수 있다.

계획서에는 어떤 방향으로 이동하는지가 적혀 있다.

U,D,L,R 하나의 문자가 반복적으로 띄어쓰기를 기준으로 적혀 있다.

정사각형에서 바깥으로 나가려는 움직임을 제외한다.

예를들어, 처음에 L 혹은 U를 만나면 무시한다.

 

계획서가 주어졌을 때, 시작점에서 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하기

 

입력 조건 : 

첫째 줄에 공간의 크기를 나타내는 n이 주어짐(1 <= n <= 100)

둘째 줄에 시작점에서 이동할 계획서 내용이 주어진다. (1 <= 이동 횟수 <= 100)

 

출력 조건 :

첫째 줄에 시작점에서 최종적으로 도착할 지점의 좌표를 (X, Y)라고 할때, 공백으로 구분하여 값을 출력한다.

 

입력 예시 :

5

R R R U D D

 

출력 예시 :

3 4

 

 

 

예를들어,

 

R 인 경우 (1, 1) 에서 (1, 2) 로 가기 떄문에 (0, +1) 이다

 

L 은 (1, 2) 에서 (1, 1)로 이동하기 때문에, (0, -1 ) 이다

 

U는 (2,2) 에서 (1,2) 로 이동하기 때문에, (-1, 0)이며,

 

D는 (2,2)에서 (3, 2) 로 이동하기 때문에, (+1, 0) 이다

 

 

코드는 다음과 같다

 

# n 정사각형의 차원을 받기
n = int(input())
x, y = 1, 1 # 초기 시작값은 (1,1)
plans = input().split() # 이동할 좌표

#U D L R ( 상 하 좌 우)에 따른 이동 방향
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
nx, ny = 0, 0

move_types = ['U', 'D', 'L', 'R']

#이동 계획을 확인
for plan in plans:
    # 1. 이동 먼저 하기
    # 2. 좌표 구하기
    
    
    for i in range(len(move_types)):
        if plan == move_types[i]:
            nx = x + dx[i]
            ny = y + dy[i]
        
        # 공간을 벗어나는 경우는 무시
        # 시작할때, 좌측으로 가는 경우 or 위로 가능 경우
        # n 정사각형을 벗어날때
        if nx < 1 or ny < 1 or nx > n or ny > n:
            continue
        
        #이동 실시
        x, y = nx, ny
        
print(x, y)

 

이동 횟수가 n 번이면, 시간 복잡도는 O(N) 이다.

 

주어진 명령(좌우상하) 에 따라 이동하는 것으로부터 '시뮬레이션' 유형이라고 한다.

 

난이도가 낮은 만큼, 반드시 풀어야 하는 알고리즘 문제이다.