이것이 취업을 위한 코딩 테스트다 with 파이썬 책을 읽고 작성하였습니다.

구현 알고리즘

1. 피지컬로 승부하기

코딩테스트에서 구현(implementation)이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정' 입니다. 어떤 문제를 풀든 간에 소스코드를 작성하는 과정은 필수이므로 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념입니다.

그런 의미에서 알고리즘 교재에서는 대부분 구현을 별도의 유형으로 다루지 않지만, 코딩 테스트에는 구현이 중심이 되는 문제가 자주 출제됩니다.

이 책에서는 완전 탐색과 시뮬레이션 유형을 모두 '구현' 유형으로 묶고 있습니다.
완전 탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미하고, 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 문제를 의미합니다.

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

파이썬은 C/C++와 자바와 다르게 직접 자료형을 지정할 필요가 없어서 매우 큰 수의 연산 또한 기본으로 지원합니다. 다만, 파이썬에서의 실수형 변수는 다른 언어와 마찬가지로 유효 숫자에 따라서 연산 결과가 원하는 값이 나오지 않을 수 있다는 점을 기억해야합니다.

2.1 파이썬에서 리스트의 크기

파이썬에서 여러 개의 변수를 사용할 때는 리스트를 이용합니다. 따라서 리스트를 이용할 때에 고려사항이 있습니다. 대체로 코딩 테스트에서는 128 ~ 512MB로 메모리를 제한하는데 알고리즘 문제 중 때로는 수백만 개 이상의 데이터를 처리하는 문제가 출제되곤 합니다. 이럴 때는 메모리 제한을 생각해야 하는데, 파이썬에서 int와 같은 별도의 자료형을 명시해 줄 필요는 없지만, 시스템 내부적으로는 다음과 같은 메모리를 차지합니다.

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

만약 메모리 처리량이 많으면 꼭 메모리 제한을 고려해야 합니다. 리스트를 여러 개 선언하고, 그중에서 크기가 1,000만 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 풀 수 없게 되는 경우도 있다는 점을 기억해야 합니다.

결론은 일반적인 코딩 테스트에서는 메모리 사용량 제한보다 더 적은 크기의 메모리를 사용해야 한다는 점입니다.

3. 시각예제

문제

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다.

• 00시 00분 03초
• 00시 13분 30초

반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각이다.

• 00시 02분 55초
• 01시 27분 45초

입력 조건 : 첫째 줄에 정수 N이 입력된다(0 <= N <= 23)
출력 조건 : 00시 00분 00초부터 N시 59분 59초까지의 모든 시작 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다

소스코드

# 시간 입력
n = int(input())
# 3을 포함한 수를 세기 위한 결과 변수
result = 0

# N시 59분 59초이므로 n + 1로 범위를 지정 
for hour in range(n + 1):
    # 분을 측정하기 위한 for문
    for minute in range(60):
        # 초를 측정하기 위한 for문
        for second in range(60):
            # 문자열로 합치고 3이 포함되어 있으면 result 변수 1 증가
            if '3' in str(hour) + str(minute) + str(second):
                result += 1

print(result)

문제 풀이

문제에서 나와있듯이 모든 경우의 수를 출력해야 하므로 무든 경우의 수를 주저 없이 다 계산하는 완전 탐색 유형의 문제입니다. 일반적으로 완전 탐색 알고리즘은 비효율적인 시간 복잡도를 가지고 있으므로 데이터 개수가 큰 경우에 정상적으로 동작하지 않을 수 있습니다. 그래서 일반적으로 알고리즘 문제를 풀 때는 확인(탐색)해야 할 전체 데이터의 개수가 100만 개 이하일 때 완전 탐색을 사용하면 적절합니다.