아이디어를 코드로 바꾸는 구현

이것이 취업을 위한 코딩 테스트다 with 파이썬을 공부하면서 정리한 내용입니다.

---

피지컬로 승부하기

• 구현이란 머릿속에 있는 알고리즘을 소스 코드로 바꾸는 과정
• 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념
• 흔히 문제 해결 분야에서 구현 유형의 문제는 풀이를 떠올리는 것은 쉽지만 소스 코드로 옮기기 어려운 문제를 의미
• 완전 탐색과 시뮬레이션을 구현 유형에 포함
  • 완전 탐색: 모든 경우의 수를 다 계산하는 해결 방법
  • 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 문제 유형

---

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

파이썬에서 리스트 크기

• 파이썬에서 리스트를 이용할 때 코딩 테스트의 메모리 제한을 고려해야 함
• 코딩 테스트에서는 대체로 128 ~ 512MB로 메모리를 제한
• int 자료형 데이터의 개수에 따른 메모리 사용량

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

• 데이터 처리량이 많을 때는 메모리 제한을 고려

---

채점 환경

• 파이썬을 기준으로 코드가 1초에 2,000만 번의 연산을 수행한다고 가정하고 문제를 풀면 실행 시간 제한에 안정적
• 제한 시간이 1초이고, 데이터의 개수가 100만 개인 문제가 있다면 일반적으로 시간 복잡도 $O(NlogN)$ 이내의 알고리즘을 이용해서 문제를 풀어야 함
• 자동 채점 방식을 이용하는 코딩 테스트 환경에서 Pypy를 지원하는 곳이 늘고 있음
• Pypy는 파이썬의 문법을 그대로 지원하며, 대부분 파이썬보다 실행 속도가 더 빠름
• 특히 반복문이 많을수록 Pypy와 파이썬의 속도가 차이 커지는데, 코딩 테스트 환경에서 Pypy를 지원한다면 이용하는 것도 하나의 방법

---

구현 문제에 접근하는 방법

• 보통 구현 유형의 문제는 사소한 입력 조건 등을 문제에서 명시해주며 문제의 길이가 꽤 긴 편
• 고차원적인 사고력을 요구하는 문제는 잘 안 나와서 문법에 익숙하다면 쉽게 풀 수 있음

---

예시 문제 1: 상하좌우

문제 내용

• 여행가 A는 $N \times N$ 크기의 정사각형 공간 위에 있음
• 이 공간은 $1 \times 1$ 크기의 정사각형으로 나누어져 있음
• 가장 왼쪽 위 좌표는 $(1, 1)$이며, 가장 오른쪽 아래 좌표는 $(N, N)$
• 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며 시작 좌표는 $(1, 1)$
• 여행가 A가 이동할 계획서가 있는데, 이 계획서에는 하나의 줄에 띄어쓰기를 기준으로 L, R, U, D 중 하나의 문자가 반복적으로 적혀 있음
  • L: 왼쪽으로 한 칸 이동
  • R: 오른쪽으로 한 칸 이동
  • U: 위로 한 칸 이동
  • D: 아래쪽으로 한 칸 이동
• 여행가 A가 $N \times N$ 크기의 정사각형 공간을 벗어나는 움직임은 무시됨
• 계획서가 주어졌을 때 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성

입력 조건

• 첫째 줄에 공간의 크기를 나타내는 N이 주어짐
• 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어짐

출력 조건

• 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 $(X, Y)$를 공백으로 구분하여 출력

입력 예시

5
R R R U D D

출력 예시

3 4

문제 해설

• 문제를 요구사항대로 구현하면 연산 횟수는 이동 횟수에 비례
• 이동 횟수가 N번인 경우 시간 복잡도는 $O(N)$
• 이 문제는 일련의 명령에 따라서 개체를 차례대로 이동시킨다는 점에서 시뮬레이션 유형

소스 코드

# n을 입력받기
n = int(input())
x, y = 1, 1
plans = input().split()

# L, R, U, D에 따른 이동 방향
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
move_types = ['L', 'R', 'U', 'D']

# 이동 계획을 하나씩 확인
for plan in plans:
    # 이동 후 좌표 구하기
    for i in range(len(move_types)):
        if plan == move_types[i]:
            nx = x + dx[i]
            ny = y + dy[i]
    # 공간을 벗어나는 경우 무시
    if nx < 1 or ny < 1 or nx > n or ny > n:
        continue
    # 이동 수행
    x, y = nx, ny

print(x, y)

나의 풀이

• 계획서에서 어디로 움직일지 하나씩 꺼냄
• 꺼낸 방향이 상하좌우 중 어떤 것인지 판별
• 정사각형 공간을 벗어나지 않는 영역에서 각 방향에 맞춰 움직임 조정

소스 코드

import sys

n = int(sys.stdin.readline().rstrip())
plans = (sys.stdin.readline().rstrip().split())
point = [1, 1]

for direction in plans:
    if direction == 'U':
        if point[0] != 1:
            point[0] -= 1
    elif direction == 'D':
        if point[0] != n:
            point[0] += 1
    elif direction == 'L':
        if point[1] != 1:
            point[1] -= 1
    elif direction == 'R':
        if point[1] != n:
            point[1] += 1

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

---

예시 문제 2: 시각

문제 내용

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

입력 조건

• 첫째 줄에 정수 N이 입력됨

출력 조건

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

입력 예시

5

출력 예시

11475

문제 해설

• 모든 시각의 경우를 하나씩 모두 세서 풀 수 있음
• 하루는 86,400초로, 00시 00분 00초부터 N시 59분 59초까지의 모든 경우를 확인해도 100,000개를 넘기지 않으므로 시간 제한 안에 문제를 풀 수 있음
• 단순히 시각을 1씩 증가시키면서 3이 하나라도 포함되어 있는지 확인
• 전체 시, 분, 초에 대한 경우의 수는 $24 \times 60 \times 60$이며 3중 반복문을 이용
• 이 문제는 가능한 경우의 수를 모두 검사해보는 완전 탐색 알고리즘 유형
• 일반적으로 완전 탐색 알고리즘은 비효율적인 시간 복잡도를 가지고 있으므로 데이터 개수가 큰 경우 동작하지 않을 수 있음
• 알고리즘 문제를 풀 때 확인(탐색)해야 할 전체 데이터의 개수가 100만 개 이하일 때 완전 탐색을 사용하면 적절

소스 코드

# H를 입력받기
h = int(input())

count = 0
for i in range(h + 1):
    for j in range(60):
        for k in range(60):
            # 매 시각 안에 '3'이 포함되어 있다면 카운트 증가
            if '3' in str(i) + str(j) + str(k):
                count += 1

print(count)

나의 풀이

• 시각을 1초씩 늘리면서 시, 분, 초를 문자열 자료형으로 변환하고 3이 있는지 확인

소스 코드

import sys

n = int(sys.stdin.readline().rstrip())

result = 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):
                result += 1

print(result)