구현 (Implementation)

개념

머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정

• 모든 문제에 포함되는 개념
• 코딩테스트에서는 구현을 중심으로 하는 문제가 출제되어 따로 분류함
  • 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제 유형을 의미함

코딩테스트에서의 구현

풀이를 떠올려도 소스코드로 옮기기 어려운 문제 유형

피지컬을 요구

<aside> 💡 코딩테스트의 피지컬

프로그래밍 언어 문법에 능숙하고 코드 작성 속도가 빠른 사람을 의미

</aside>

문자열 처리나 큰 수 처리등 구현에 어려움이 없는 파이썬이 유리

대표적인 까다로운 구현 문제들

• 알고리즘은 간단하지만 코드가 지나치게 길어지는 문제
• 특정 소수점 자리까지 출력하는 문제
• 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣는(파싱) 문제
• 완전 탐색
  • 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
• 시뮬레이션
  • 문제에서 제시한 알고리즘을 한 단계씩 차례로 직접 수행해야하는 문제

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

전통적 프로그래밍 언어의 정수형 - int(integer)

• 4Byte
• -2,147,483,648 ~ 2,147,483,647

큰 수를 처리하는 방법

C/C++

• long long 사용
  • 9,223,372,036,854,775,807 까지 가능
  • 이보다 큰 수는 BigInteger클래스를 구현해야 함

Java

• BigInteger 클래스 표준 라이브러리 사용

Python

• 기본 자료형으로 지원

파이썬의 리스트 크기 - 1당 약 4바이트

• 크기가 1000만 이상인 리스트가 있다면 메모리 초과 가능성이 있음

채점 환경

• 파이썬
  • C/C++ 에 비해 2배의 수행 시간 제한을 적용하기도 함
  • 3.7기준 1초에 2,000만번의 연산 수행을 가정하면 됨
    • 제한 시간 1초에 데이터의 갯수가 100만 개라면 시간 복잡도 O(NlogN) 이내 알고리즘을 이용해야함

구현 문제 접근 방법

구현 문제 특징

• 사소한 입력 조건 등을 전부 명시
• 문제의 길이가 길어짐

→ 고차원적인 사고력을 요구하는 문제는 나오지 않는 편이라 문제의 길이를 보고 지레 겁먹지 말고 알고 있는 문법을 이용해 조건을 만족시켜 해결한다

문제

상하좌우

외쪽 상단 (1, 1)에서 오른쪽 하단 (N, N) 좌표를 갖는 N * N 크기의 공간이 있을 때 다음 네가지 입력들에 대해 (1, 1)좌표에서 출발해 나중에 위치할 좌표를 출력 (단, 공간을 벗어나는 입력은 무시함)

1. L : 왼쪽으로 이동
2. R : 오른쪽으로 이동
3. U : 위로 이동
4. D : 아래로 이동

문제 해설

요구 사항 대로 구현한다면 연산 횟수는 이동 횟수에 비례 이동 횟수가 N번이라면 시간 복잡도는 O(N)으로 넉넉함

일련의 명령에 따라 개체를 차례로 이동시킨다는 점에서 시뮬레이션 유형으로 분류할 수 있음

입력 받은 이동 계획을 하나씩 확인하여 현재 위치를 그에 맞게 하나씩 바꿔준다. 단 (1, 1)에서 (n, n)까지의 범위 내에서만 수행한다.

코드

import sys
input = sys.stdin.readline

n = int(input())            # 공간 크기 입력
planer = input().split()    # 이동 계획 입력

# 이동 계획에 따라 (이동 축, 이동 방향)을 같는 딕셔너리
mapPlan = {'L':(1, -1), 'R':(1, 1), 'U':(0, -1), 'D':(0, 1)}
# 현재 좌표
coor = [1, 1]
# 이동 계획을 하나씩 수행
for i in planer:
    t = mapPlan[i]              # 이동 축, 이동 방향을 가져옴
    temp = coor[t[0]] + t[1]    # 이동 축에서 이동 방향으로 이동한 결과
    if temp > 0 and temp <= n:  # 범위를 벗어나지 않았다면
        coor[t[0]] = temp       # 현재 좌표에 적용
print(coor[0], coor[1])         # 최종 출력

시각

왕실의 나이트

게임 개발

백준

14503번: 로봇 청소기

16505번: 별