[이코테] 03. 구현(Implementation)

---

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다.

---

구현(Implementation)

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

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

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

변수의 표현 범위

int 자료형의 크기는 4바이트, long long 자료형은 8바이트이다.

더 큰 변수를 담기 위해 자바의 경우 BigInteger를 표준 라이브러리로 지원하지만, C++의 경우 표준 라이브러리에도 포함되어 있지 않다.

검색과 외부 라이브러리 사용이 가능한 환경인 경우 직접 작성하거나 가져와 사용하지만,
대체로 long long에서 다룰 수 있는 수보다 더 큰 정수를 처리하는 문제는 잘 출제되지 않는다.

파이썬에서는 직접 자료형을 지정할 필요가 없으며 매우 큰 수의 연산 또한 기본적으로 지원하기 때문에
자료형 표현 범위 제한에 깊게 이해하고 있지 않아도 괜찮다.

다만, 실수형 변수는 다른 언어와 마찬가지로 유효 숫자에 따라 원하지 않는 값이 나올 수 있다.

파이썬에서 리스트의 크기

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

 

리스트를 여러 개 선언하고, 그 중 크기가 1,000만 이상인 리스트가 있다면

메모리 용량 제한으로 문제를 풀 수 없게 되는 경우도 있다.

채점 환경

일반적으로 시간 제한이 1초이고, 데이터 개수가 100만 개인 문제가 있다면, 시간 복잡도 O(NlogN) 이내의 알고리즘을 이용하여 문제를 풀어야 한다.

알고리즘 문제를 풀 때는 시간 제한과 데이터의 개수를 먼저 확인한 뒤에 이 문제를 어느 정도의 시간 복잡도의 알고리즘으로 작성해야 풀 수 있을지 예측할 수 있어야 한다.

---

 

[ 예제1: 상하좌우 ]

공간의 크기 N과 이동할 계획서가 주어졌을 때, A가 최종적으로 도착할 지점의 좌표를 출력

나의 코드

N = int(input())
todo = list(map(str, input().split()))

# L 왼쪽, R 오른쪽, U 위로, D 아래로
dxy = {'L': (0, -1),
       'R': (0, 1),
       'U': (-1, 0),
       'D': (1, 0)}

sx, sy = 0, 0

for i in todo:
    dx, dy = dxy[i]
    nx, ny = sx + dx, sy + dy

    # 공간 밖이면 이동하지 않음
    if nx < 0 or nx >= N or ny < 0 or ny >= N:
        continue

    # 이동한 그 자리에서 다시 출발
    sx, sy = nx, ny

# 0, 0에서 시작했으므로 1, 1씩 더해줌
print(sx+1, sy+1)

문제 해설

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

요구사항대로 구현하면 연산 횟수는 이동 횟수에 비례한다. 따라서 시간 복잡도는 O(N)이다.

---

[ 예제2: 시각] 

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하기

나의 코드

N = int(input())
# N = 5 # 11475
# 0 <= N <= 23
# 00시 00분 00초 ~ N시 59분 59초 (N+1시 00분 00초)

cnt = 0
# 시
for h in range(N+1):
    # 분
    for m in range(60):
        # 초
        for s in range(60):
            if "3" in str(h) or "3" in str(m) or "3" in str(s):
                cnt += 1

print(cnt)

문제 해설

단순히 시각을 1씩 증가시키면서 문자열 연산을 이용해 "3"이 포함되어 있는지 확인하면 된다.

시, 분, 초에 대한 경우의 수는 24 X 60 X 60으로 3중 반복문을 이용해 계산한다.

최대 횟수인 00시 00분 00초부터 23시 59분 59초까지의 모든 경우는 86,400가지 밖에 존재하지 않기 때문에 시간제한 2초 안에 문제를 해결할 수 있다.

이러한 유형은 "완전탐색" 유형으로 분류되기도 하며 완전탐색 알고리즘은 가능한 경우의 수를 모두 검사해보는 탐색 방법이다.

일반적으로 전체 데이터의 개수가 100만개 이하일 때 완전탐색을 사용하면 적절하다.

 

---