구현

코딩 테스트에서 구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다.

보통 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭한다.

 

<'구현' 유형>
알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
문자열은 특정한 기준에 따라서 끊어 처리해야 하는 문제
적절한 라이브러리를 찾아서 사용해야 하는 문제 (순열과 조합을 찾는 경우 등)
-> 많은 연습이 필요한 분야이다.(프로그래밍 언어의 문법을 정확히 알고 있어야 한다.)

 

대표적으로 완전 탐색과 시뮬레이션 유형을 '구현' 유형으로 많이 사용한다.

완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법

-> 보통 데이터의 개수가 100만개 이하일 때 완전 탐색을 사용하면 적절하다. 일반적으로 DFS/BFS를 사용한다.

-> 만약 원소를 나열하는 모든 경우의 수를 고려해야 하는 경우 파이썬 itertools 라이브러리로 쉽게 구현할 수 있다.

시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행

 

주의 사항

 

<메모리 제약 사항>

c/c++ 과 java의 경우 정수형을 표현할 때 int 자료형을 주로 사용하며 이 자료형의 크기는 4byte이다. 즉, 4byte로 표현할 수 있는 범위를 넘어서는 정수에 대해서는 더 큰 크기의 자료형을 사용해야 한다.

반면에 파이썬에서는 프로그래머가 직접 자료형을 지정할 필요가 없으며, 매우 큰 수의 연산 또한 기본으로 지원한다.

다만, 파이썬에서의 실수형 변수는 다른 언어와 마찬가지로 유효숫자에 따라서 연산 결과가 원하는 값이 나오지 않을 수 있다는 점을 주의하자.

 

<파이썬에서 리스트 크기>

파이썬은 int와 같은 별도의 자료형을 명시해줄 필요가 없지만, 시스템 내부적으로는 다음과 유사한 크기만큼 메모리를 차지한다.

 

데이터의 개수(리스트의 길이)    메모리 사용량

1,000                                   약 4KB

1,000,000                              약 4MB

10,000,000                            약 40MB

 

대체로 코딩테스트에서는 128~512MB로 메모리를 제한하는데 크기가 1,000만 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 풀 수 없게 되는 경우가 있다.

하지만, 이런 문제는 드물며 보통 메모리 사용량 제한보다 더 적은 크기의 메모리를 사용하는 경우가 많다.

 

<채점 환경>

현재 파이썬의 경우 1초에 2,000만 번의 연산을 수행한다고 가정하면 크게 무리가 없다.

예를 들어, N=1,000,000인 경우 O(NlogN) 이내의 알고리즘을 이용하여 문제를 풀어야 한다. 실제로 1,000,000일 때, Nlog2N은 약 20,000,000이기 때문이다.

파이썬은 대체로 C/C++에 비해 실행 속도가 다소 긴 편이지만 최근 코딩테스트 환경에서 Pypy3를 지원하는 곳이 늘고 있다. Pypy3는 파이썬3의 문법을 그대로 지원하며, 대부분 파이썬3보다 실행 속도가 빠르다. 따라서 코딩 테스트 환경이 Pypy3를 지원한다면 이를 이용하도록 하자.

 

예제) 상하좌우

일반적으로 알고리즘 문제에서의 2차원 공간은 '행렬'의 의미로 사용된다.

시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용된다.
# 동, 북, 서, 남
dx=[0,-1,0,1]
dy=[1,0,-1,0]
# 현재 위치
x,y=2,2
for i in range(4):
    # 다음 위치
    nx=x+dx[i]
    ny=y+dy[i]
    print(nx,ny)

 

이를 기반으로 문제를 풀어본다.

Q. N*N 크기의 정사각형 공간에 (1,1)에서 출발하여 이동할 계획서를 토대로(U,D,L,R) 최종적으로 도착할 지점의 좌표를 출력한다.

 

Sol.

n=int(input())
data=list(input().split())
dx=[-1,1,0,0]
dy=[0,0,-1,1]
x,y=0,0
for direction in data:
  if direction=='U':
    if x>0:
      x=x+dx[0]
      y=y+dy[0]
  elif direction=='D':
    if x<n-1:
      x=x+dx[1]
      y=y+dy[1]
  elif direction=='L':
    if y>0:
      x=x+dx[2]
      y=y+dy[2]
  elif direction=='R':
    if y<n-1:
      x=x+dx[3]
      y=y+dy[3]
print(x+1,y+1)

 

구현 문제는 그리디 알고리즘 문제 유형과 비교했을 때 큰 차이가 느껴지지 않는다. 보통 구현 유형은 그리디 유형이 포함된 형태로 출제되는 경우가 많기 때문에 이를 유의하자.