구현 알고리즘이란?
풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제.
알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제.
(ex. 특정 소수점 자리까지 출력, 문자열 입력을 한 문자 단위로 파싱 등 )
사소한 조건 설정이 많은 문제일 수록 코드로 구현하기 까다로움.
프로그래밍 문법을 정확히 숙지하고 라이브러리 사용 경험이 풍부해야 함.
* 구현이 핵심이 되는 유형
- 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
- 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행
구현 시 고려해야 할 메모리 제약 사항
1. int 크기 제약
대체로 long long 에서 다룰 수 있는 수보다 더 큰 정수를 처리하는 문제는 잘 출제되지 않는다.
Java -- long long, BigInteger(클래스. 범위제한없음)
Python -- 직접 자료형을 지정할 필요가 벗으며 매우 큰 수의 연산 또한 기본으로 지원
2. 파이썬에서 리스트 크기
대체로 코딩 테스트에서는 128 ~ 512MB로 메모리 제한하고
문제 중 때로는 수백만 개 이상의 데이터를 처리해야 하는 문제가 출제되곤 함.
즉, 메모리 제한을 염두에 두고 코딩을 해야 함.
일반적인 코딩 테스트 수준에서는 메모리 사용량 제한보다 더 적은 크기의 메모리를 사용해야 한다.
구현 문제에 접근하는 방법
보통 문제에서 사소한 입력 조건 등을 명시해주기 떄문에 문제 길이가 꽤 긴 편.
그러나 고차원적인 사고력을 요구하는 문제는 나오지 않아서
문법에 익숙하면 오히려 쉽게 풀 수 있다.
파이썬은 기본 문법만 알아도 상대적으로 구현 유형의 문제를 쉽게 해결할 수 있다.
다만, C/C++ 이나 Java 에서는 문자열 처리가 까다롭고 큰 정수를 처리하는 라이브러리를 별도로 사용해야 하기 때문에
더 어렵게 다가올 수 있다.
# N x N 크기의 정사각형 공간에서 입력 방향대로 움직임
def up_down_left_right():
position = [1, 1]
N = int(input("5 -- "))
direction = list(input("R R R U D D -- ").split())
for d in direction:
if d == 'L':
if position[1] > 1:
position[1] -= 1
elif d == 'R':
if position[1] < N:
position[1] += 1
elif d == 'U':
if position[0] > 1:
position[0] -= 1
elif d == 'D':
if position[0] < N:
position[0] += 1
return position
print(*up_down_left_right())
'''
# 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)):
if plan == move_types[i]:
nx = x + dx[i]
ny = y + dy[i]
# 공간을 벗어나는 경우 무시
if nx < 1 of ny < 1 or nx > n or ny > n:
continue
# 이동 수행
x, y = nx, ny
print(x, y)
'''