[ 이것이 코딩테스트다 ] 11일차

안영우·2021년 1월 7일

동빈나 코딩테스트

[ 이것이 취업을 위한 코딩 테스트다. with 파이썬 ]

목록 보기

11/39

✏️ 서론

어제는 그리디 알고리즘에 대해 배웠다.
오늘도 어제 못지않게 중요한 구현(implementation)알고리즘에 대해서 알아보자.

✏️ 본론

구현(implementation) 알고리즘은 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정을 뜻한다.

사실 어떤 알고리즘을 풀더라도 문제를 해결하기 위해 소스코드를 작성하므로 모든 범위의 문제 유형을 포함하는 개념이다.

코딩테스트에 한정해서 구현은 풀이를 떠올리긴 쉽지만 소스코드로 옮기기는 쉽지 않은 문제를 의미한다.

특히, 사소한 조건 설정이 많은 문제일수록 코드로 구현하기 까다롭다.

이 책에서는 완전 탐색, 시뮬레이션 유형을 모두 구현 유형으로 묶어서 다루고 있다.

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

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

대체로 코딩 테스트에서는 128~512MB로 메모리를 제한하는데 이럴 때는 메모리 제한을 염두해두고 코딩을 해야한다.

예를 들어 우리가 흔히 사용하는 int자료형의 데이터 개수는 다음과 같다.

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

파이썬은 다른 언어에 비해 구현상의 복잡함은 적지만, 데이터 처리량이 많을 때는 꼭 메모리 제한을 고려하자.

만약, 크기가 1,000 이상인 리스트가 있다면 메모리 용량 제한으로 풀 수 없게 되는 경우도 있다는 점을 기억하자.

일반적인 기업의 코딩 테스트 환경에서는 파이썬으로 제출한 코드가 1초에 20,000,000번의 연산을 수행한다고 가정하고 문제를 풀면 실행 시간 제한에 안정적이다.

📍 simulation

알고리즘을 각 한 단계씩 직접 수행하는 알고리즘. Brute_force와 함께 구현의 핵심 알고리즘이 되는 경우가 많다.
N x N Matrix 문제로 자주 출제 됨.

⚡️ [ 문제 ] 상하좌우

n = int(input())
directions = input().split()
vector = ['L', 'R', 'U', 'D']

# 최초위치
x, y = 1, 1

# 좌우상하 방향벡터 선언
# 행 Index
dx = [0, 0, -1, 1]
# 열 Index
dy = [-1, 1, 0, 0]

for direction in directions:
    for i in range(len(vector))
        if direction == vector[i]:
            nx = n + dx[i]
            ny = n + dy[i]
    
    if nx < 1 or ny < 1 or nx > n or ny > n:
         continue
    x, y = nx, ny

print(nx, ny)
👉🏽 입력
5 
R R R U D

👉🏽 출력
3 4

📍 brute_force

모든 경우의 수를 판단하는 알고리즘
브루트 포스(BruteForce)라고 불리며,
보통 데이터가 1,000,000개 이하 일때 완전탐색을 이용하면 적절하다.

⚡️ [ 문제 ] 시간

문제: 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초이하의 모든 시간 중 '3'이 포함되는 경우의 수를 찾아보세요.

n = int(input())
count = 0

for h in range(n+1):
    for m in range(60):
        for s in range(60):
            if '3' in str(h) + str(m) + str(s):
                count = count + 1
print(count)
👉🏽 입력
5

👉🏽 출력
11475