Implementation 알고리즘?
- 문제를 풀기 위한 머릿속 알고리즘을 코드로 작성하는 과정을 구현이라한다.
- 사실 모든 알고리즘 문제는 코드를 통한 해결이기에 모든 범주를 포함하는 유형이다.
- 논리적 사고를 판단할 수 있는 가장 기본 난이도 문제로 그리디와 같이 1~2번 문제로 자주 출제
- 문제유형 : 풀이를 떠올리기는 쉽지만, 코드구현이 복잡하거나 어려움.
-> 문법 또는 경험이 요구된다. - 피지컬을 요구하는 문제이다.
-> 피지컬 : 문법에 능숙하고 코드를 빠르게 작성하는 것 - 완전탐색, 시뮬레이션 문제가 포함될 수 있다.
-> 완전탐색 : 모든 경우를 다 계산하는 해결방법
-> 시뮬레이션 : 문제에서 요구되는 알고리즘을 한 단계식 직접 수행
구현하기 어려운 문제?
- 간단한 알고리즘이지만 구현 시 코드가 길어지는 문제
- 특정 소수점까지 출력을 요구하는 문제
- 문자열을 문자단위로 리스트에 파싱해야하는 문제
- 문제에서 사소한 조건들이 많은 문제
구현 문제 접근 방법?
| 구현 난이도 | 프로그램 실행 시간 | |
| 파이썬 | 쉬운 편 | 긴 편 |
| PyPy | 쉬운 편 | 다소 짧은 편 |
| C/C++ | 어려운 편 | 짧은 편 |
- PyPy는 Python3 문법을 그래도 지원하면서 실행 속도가 더 빠르다.
-> 코테에서 동일한 코드를 작성해도 무방하다 - 1초에 20,000,000 ~ 100,000,000 연산처리 가능
- 코테 시 PyPy가 지원된다면 적극 활용할 수 있다.
문제1. 상하좌우
문제 :
여행가 A는 N X N 크기의 정사각형 공간 위에 서 있따. 이 공간은 1 X 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1,1)이며, 가장 오른쪽 아래 좌표는 (N,N)에 해당한다. 여행가 A는 상, 하, 좌 ,우 방향으로 이동가능하며, 시작점은 (1,1)이다. 여행가에게 이동 계획서가 주어질 때, 최종 도달 위치를 출력하라.
계획서는 하나의 줄에 띄어쓰기를 기준으로 L, R, U, D 중 하나의 문자가 반복적으로 적혀 있으며, 이동 시 공간을 벗어나는 이동은 무시한다.
입력 :
- 첫째 줄에 공간의 크기를 나타내는 N이 주어진다. ( 1 <= N <= 100)
- 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다.(1 <= 이동횟수 <= 100)
출력 :
- 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X,Y)를 공백으로 구분하여 출력
제한조건 :
시간 제한 1초 | 메모리 제한 128MB
# 구현코드
# 지도 크기 N 입력받기
N = int(input())
# 여행가가 이동할 위치 계획 입력받기
plans = input().split()
# 초기 좌표 값
x,y = 1,1
#U R D L 순서로 이동할 크기
dx = [0,1,0,-1]
dy = [-1,0,1,0]
type = ["U","R","D","L"]
for p in plans:
# 타입 찾기
t = type.index(p)
# x좌표 이동량
nx = dx[t]
# y좌표 이동량
ny = dy[t]
# 이동 시 공간을 벗어나지 않으면 이동
if 0< x + nx <= N and 0 < y + ny <= N:
x += nx
y += ny
print(y,x)
#답안코드
# N을 입력받기
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)):
nx = ny = 0
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)
배운점
* x, y = nx, ny와 같이 한 줄에 매칭되는 형태로 값을 넣을 수 있다.
* nx, ny가 지역변수라서 if를 벗어나면 사용할 수 없는데 답안코드에 오타가 있었으며, 이를 통해서 파이썬에서도 지역변수 범위를 확인할 수 있었다.