[알고리즘] 구현 (Implementation) / 예제 풀이

나동빈 님의 이것이 코딩테스트다 with 파이썬 를 보며 코딩테스트에 필요한 다양한 알고리즘 기법들을 복습하고 정리한 내용입니다.

코딩테스트에서 구현은 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정으로, 보통 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다.

보통 코딩 테스트에는 구현이 중심이 되는 문제가 자주 출제된다.

흔히 구현 문제는 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기는 어려운 문제를 의미한다. → ‘피지컬’을 요구하는 문제

이 책에서 제시하는 구현의 유형

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

구현 시 고려해야할 사항

정수의 표현 범위

C/C++과 JAVA 에서는 기본 int(정수)형은 4byte로 -2,147,483,628 ~ 2,147,483,647까지 표현이 가능한데, 이는 2,147,483,647 (약 21억)보다 큰 수는 처리할 수 없다.

그래서 long long형을 사용하는데 이는 9,223,372,036,854,775,807 (이거 몇임 ;;)까지 처리할 수 있다. 이보다 더 큰수는 BigInteger 클래스로 구현하면 되지만, 보통 long long보다 더 큰 수 까지의 처리는 잘 출제되지 않는다.

파이썬은 직접 자료형을 선언해줄 필요가 없고, 자동으로 매우 큰 수의 연산도 지원한다.

파이썬에서 리스트 크기

파이썬에서 여러 개의 변수를 사용할 때 리스트를 이용하는데, 이 때 꼭 메모리 제한을 고려해야한다. 대체로 문제들은 128 ~ 518MB의 메모리 제한을 두고, 수백만 개 이상의 데이터를 처리해야 하는 문제가 출제되곤 한다.

• int 자료형 데이터의 개수에 따른 메모리 사용량

  데이터 개수(리스트 길이)	메모리 사용량
  1,000	약 4KB
  1,000,000	약 4MB
  10,000,000	약 40MB

  리스트를 여러 개 선언하고, 그 중 크기가 1,000만 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 풀 수 없게 되는 경우도 있다. 하지만 이런 경우는 많지 않다.

  어쨋든 될 수 있다면 위 메모리 사용량과 메모리 제한을 고려해서 문제를 설계하자.

채점 환경

파이썬은 C/C++에 비해 속도가 느리다. 그래서 파이썬은 C/C++에 비해 2배의 수행 시간 제한을 적용한다. 파이썬 3.7을 기준으로 코드가 1초에 2,000만 번의 연산을 수행한다고 가정하고 문제를 풀면 된다!

그래서 시간 제한이 1초이고, 데이터의 개수가 100만 개인 문제가 있다면 일바적으로 시간 복잡도 O(NlogN) 이내의 알고리즘을 풀어야 한다. 그 이유는 N = 1,000,000일 때 NllogN = 20,000,000이기 때문이다.

예제

1. 상하좌우

 
import sys
N = int(sys.stdin.readline())

cur = [1, 1]

A = list(sys.stdin.readline().split())

for a in A :
    if a == 'R' and cur[1] <= N :
        cur[1] += 1
    elif a == 'L' and cur[1] > 1 :
        cur[1] -= 1
    elif a == 'U' and cur[0] > 1 :
        cur[0] -= 1
    elif a == 'D' and cur[0] <= N :
        cur[0] += 1

print(cur[0], cur[1])