[구현] 알고리즘 - 구현 (Implementation)

구현

문제에 대한 알고리즘을 소스코드로 만드는 과정이 구현이다.

어떤 문제를 풀든 간에 소스코드를 작성하는 과정은 필수적이므로 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다.

구형 유형의 문제는 풀이는 떠올리는 것은 쉽지만 그것을 소스코드로 옮기는 과정이 어려운 문제를 의미한다.

 

구현 유형

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

 

구현 문제 풀이시 생각해야 될 점

1. 메모리 제약 사항
2. 채점 환경
3. 접근 방법

•  파이썬의 경우 1초에 2*10^7(2000만번)의 연산을 수행한다.
• pypy3 지원시 사용하면 1초에 1억번의 연산을 수행할 수 있다.

pypy3의 속도는 c/c++에 견줄만큼 빠르기 때문에 pypy3를 지원한다면 이를 이용하면된다.

 

EX)  상하좌우

Q. NxN 크기의 정사각형 공간이 주어지고 왼쪽 가장 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)이다.

(1, 1)에서 이동하는 사람은 상(U), 하(D), 좌(L), 우(R)로 이동할 수 있다.

만약 정사각형 공간을 벗어나서 이동하는 움직임은 무시된다.

N과 이동 할 계획이 주어지고 최종적으로 도착한 좌표를 출력해라.

 

해설. 문제를 요구사항 대로 구현하면 연산 횟수는 이동 횟수에 비례하므로 이동 횟수가 N인 경우 시간 복잡도는 O(N)이 된다.

문제 유형은 명령에 따라 개체를 차례로 이동시키는 점에서 시뮬레이션 유형으로 분류되며 구현이 중요한 문제이다.

 

코드

n = int(input()) # 공간 입력
x, y = 1, 1
plans = input().split() # 이동 경로 입력

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 == i:
        	nx = dx[i] + x
            ny = dy[i] + y
    #공간을 벗어나는 경우
	if nx < 1 or ny < 1 or nx > n or ny > n:
		continue
    #이동 수행
    x, y = nx, ny
print(x, y)

 

---

 

구현 문제 

https://www.acmicpc.net/problem/21608

21608번: 상어 초등학교

 

풀이

https://h-castle.tistory.com/entry/%EB%B0%B1%EC%A4%80-baekjoon-%EB%B0%B1%EC%A4%80-21608%EB%B2%88-%EC%83%81%EC%96%B4-%EC%B4%88%EB%93%B1%ED%95%99%EA%B5%90-by-%ED%8C%8C%EC%9D%B4%EC%8D%ACPython-%EA%B5%AC%ED%98%84

[백준 baekjoon] 백준 21608번 상어 초등학교 by 파이썬(Python) : 구현