알고리즘 / 자료구조’ 시리즈

[이.취.코] Chap 4. 구현 - 개념

  • 0
  • 0
0
0

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

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

생각해낸 문제 풀이 방법을 우리가 원하는 프로그래밍 언어로 정확히 구현해냈을 때 정답 처리를 받을 수 있다. 프로그래밍 언어의 문법을 정확히 알고 있어야 하며 문제의 요구사항에 어긋나지 않는 답안 코드를 실수 없이 작성해야 한다.

까다로운 구현 유형의 문제는 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제, 특정 소수점 자리까지 출력해야 하는 문제, 파싱하는 문제 등 사소한 조건 설정이 많은 문제일수록 코드로 구현하기가 까다롭다

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

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

a. 변수의 표현 범위

파이썬은 직접 자료형을 지정할 필요가 없으며 매우 큰 수의 연산 또한 기본으로 지원한다. 파이썬의 실수형 변수는 유효숫자에 따라서 연산 결과가 원하는 값이 나오지 않을 수 있다는 점을 기억하자.

b. 리스트의 크기 제약

코딩 테스트에서는 보통 128 ~ 512MB로 메모리를 제한한다. 수백만 개 이상의 데이터를 처리해야 하는 경우 메모리 제한을 염두에 두고 코딩해야 한다.

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

크기가 1000만 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 풀 수 없게 되는 경우도 있다.

c. 채점 환경

파이썬으로 제출한 코드가 1초에 2000만 번의 연산을 수행한다고 가정하면 크게 무리가 없다.

시간 제한이 1초이고, 데이터의 개수가 100만 개인 문제는 시간 복잡도 O(NlogN) 이내의 알고리즘을 이용하여 문제를 풀어야 한다. (N = 1,000,000의 Nlog_2N은 약 20,000,000)

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

d. 구현 문제에 접근하는 방법

구현 유형의 문제는 사소한 입력 조건 등을 문제에서 명시해주며 문제의 길이가 꽤 긴 편이다.

Pypy3는 파이썬3의 문법을 그대로 지원하며, 대부분 파이썬3보다 실행 속도가 더 빠르다. 대략 1초에 2000만 번에서 1억 번 정도의 연산을 처리할 수 있다.

API 개발 문제 또한 구현 유형과 상당히 맞닿아 있다. 이때 카카오 문제 풀이 서버와 통신하는 프로그램 모듈을 작성해야 한다. 이는 웹 서버나 데이터 분석에 대한 기초 지식도 필요하다.

A. 예제 1. 상하좌우

a. 문제
  • NxN 크기의 정사각형 공간이 있다.
    • 가장 왼쪽 위 좌표는 (1, 1)
    • 가장 오른쪽 아래 좌표는 (N, N)
  • 상, 하, 좌, 우로 이동할 수 있다.
    • L
      • 왼쪽으로 한 칸 이동
    • R
      • 오른쪽으로 한 칸 이동
    • U
      • 위쪽으로 한 칸 이동
    • D
      • 아래쪽으로 한 칸 이동
  • NxN 크기의 정사각형 공간을 벗어나는 움직임은 무시된다.
b. 입력 조건
  • 첫째 줄에 공간의 크기를 나타내는 N이 주어진다
    • 1 <= N <= 100
  • 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다
    • 1 <= 이동 횟수 <= 100
c. 출력 조건
  • 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X, Y)를 공백으로 구분하여 출력한다.
d. 테스트 케이스
  • 입력 예시

    
    5
    R R R U D D
    
    
  • 출력 예시

    
    3 4
    
    
e. 내 답안

n = int(input())  
plan_list = list(map(str, input().split()))  
  
position = [1, 1]  
  
for plan in plan_list:  
  if plan == "L" and position[1] > 1:  
    position[1] = position[1] - 1  
  elif plan == "R" and position[1] < n:  
    position[1] = position[1] + 1  
  elif plan == "U" and position[0] > 1:  
    position[0] = position[0] - 1  
  elif plan == "D" and position[0] < n:  
    position[0] = position[0] + 1  
  
print(position)

f. 문제 해설

연산 횟수는 이동 횟수에 비례하게 된다. 이동 횟수가 N번인 경우 시간 복잡도는 O(N)이다.

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

g. 책 답안

python-for-coding-test/1.py at master · ndb796/python-for-coding-test (github.com)

h. 회고

반성

  • 책 답안 Line 7~9
    • 리스트의 특성을 이용하여 x, y 좌표를 이용하지 못함.
    • 내 답도, 책 답도 잘 동작하지만, 차이점은 코드 가독성의 차이.

결론

  • 너무 바로 코드를 작성하지 말고, 조건들을 생각해서 연필로 밑그림을 그리고 작성하자.

B. 시각

a. 문제
  • 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하라.
b. 입력 조건
  • 첫째 줄에 정수 N이 입력된다
    • (0 <= N <= 23)
c. 출력 조건
  • 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력하라.
d. 테스트 케이스
  • 입력 예시

    
    5
    
    
  • 출력 예시

    
    11475
    
    
e. 내 답안

n = input()  
import time as ti  
  
start = ti.time()  
  
  
hh = "00"  
mm = "00"  
ss = "00"  
  
time = str(hh) + str(mm) + str(ss)  
count = 0  
  
while time != (n + "5959"):  
  for i in range(0, len(time)):  
    # print(time[i])  
 if time[i] == "3":  
      # print(count)  
 count = count + 1  
 break  
  
 hh = int(hh)  
  mm = int(mm)  
  ss = int(ss)  
  
  ss = ss + 1  
  
 if ss == 60:  
    mm = mm + 1  
 ss = ss - 60  
  
 if mm == 60:  
    hh = hh + 1  
 mm = mm - 60  
  
 time = str(hh) + str(mm) + str(ss)  
  
end = ti.time()  
  
print(end-start)  
  
print(count)

f. 문제 해설

모든 시각의 경우를 하나씩 모두 세서 쉽게 풀 수 있다. 하루는 86,400초로 경우의 수는 최대 86,400가지 밖에 존재하지 않는다.

이런 유형은 완전 탐색 유형. 가능한 경우의 수를 모두 검사해보는 탐색 방법. 구현이 중요한 대표적인 문제 유형. 일반적인 완전 탐색 알고리즘은 비효율적인 시간 복잡도를 가지므로 데이터 개수가 큰 경우에 정상적으로 동작하지 않을 수 있다.

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

g. 책 답안

python-for-coding-test/2.py at master · ndb796/python-for-coding-test (github.com)

h. 회고

반성

  • 책 답안 Line 9
    • in을 사용하여 문자열 검색을 쉽게 하였음.
    • 나는 아직까지도 파이썬 문법을 완벽하게 숙지하지 못한 것을 깨달음.

결론

  • 자주 써봐야겠다. 그럼 익숙해져서 자연스럽게 사용할 수 있겠지.

참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

#코딩테스트 #파이썬 #나동빈 #한빛미디어 #구현 #개념

0분전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.