네이버 부스트 캠프 코딩 테스트를 본 후 자극을 받아 "이것이 코딩 테스트다 with 파이썬" 책을 다시 피고 공부하기 시작했다. 아자아자
1. 구현이란
구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다. 보통 구현 문제 유형의 경우 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다. 또한 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미한다.
이 책에서 구현유형은 '완전 탐색', '시뮬레이션 유형' 이렇게 두 가지 유형으로 나누어서 설명하고 있다.
2. 구현 시 고려해야 할 제약 사항
내가 사용하는 언어는 파이썬이기 때문에 파이썬 사용시에 고려해야 할 제약 사항만 공부했다. 파이썬에서는 리스트 크기 제약을 중점으로 알아야 한다.
파이썬 리스트를 이용 할 때에는 메모리 제한을 고려해야 한다.
파이썬에서 int 자료형 데이터의 개수에 따른 메모리 사용량은 다음 표와 같다.
| 데이터의 개수(리스트 길이) | 메모리 사용량 |
|---|---|
| 1,000 | 4KB |
| 1,000,000 | 4MB |
| 10,000,000 | 40MB |
파이썬은 다른 언어에 비해 구현상의 복잡함이 적은 편이지만 데이터의 처리량이 많을 때는 메모리 제한을 고려하는 것이 좋다.
3. 구현 알고리즘 예시
- 시뮬레이션 유형 - 일련의 명령에 따라 개체를 차례대로 이동시킨다
<문제> 여행가 A는 N X N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 X 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1,1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)이다.
계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀있고,
L : 왼쪽으로 한 칸 이동
R : 오른쪽으로 한 칸 이동
U : 위로 한 칸 이동
D : 아래로 한 칸 이동
이때 A가 N X N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다. 예를 들어 (1,1)의 위치에서 L 혹은 U를 만나면 무시된다.
여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오.
입력 조건
첫째 줄에 공간의 크기를 나타내는 N이 주어진다.(1 <= N <= 100)
둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다.출력 조건
첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표(X,Y)를 공백으로 구분하여 출력한다.입력 예시 출력 예시
5 3 4
R R R U D D
작성한 코드는 다음과 같다
n = int(input())
route = input().split() // 이동할 계획이 담긴 리스트
x, y = 1, 1 // 가장 왼쪽 위 좌표 (1,1)
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1] // 상,하,좌,우
direct = ["U","D","L","R"]
for road in route:
for i in range(len(direct)):
if road = direct[i]:
nx = x + dx[i]
ny = y + dy[i]
if nx < 1 or nx > n or ny < 1 or ny > n: // NXN을 벗어났을 경우 무시
continue
x, y = nx, ny // x, y 갱신
print(x,y)이 문제를 위의 코드로 구현하면 연산 횟수는 결국 이동 횟수에 비례하게 된다. 그러므로 시간 복잡도는 O(N)이다.
-
완전 탐색 유형 - 가능한 경우의 수를 모두 검사해는 방법 (Bruteforce 라고도 한다.)
이 알고리즘의 경우에는 비효율적인 시간 복잡도를 가지고 있기 때문에 확인해야 할 전체 데이터의 개수가 100만 개 이하일 때 사용하면 적절하다.
<문제> 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오.
입력 조건
` 첫째 줄에 정수 N이 입력된다.(0<=N<=23)
출력 조건
` 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다.
입력 출력 예시
5 11475
이 문제의 경우는 위의 나온 것과 같이 완전 탐색을 통해 모든 경우의 수를 찾아 보면 된다.
주의할 점은 매 시각을 문자열로 바꾼 다음 '3'이 포함됐는지를 검사 해야 한다.
n = int(input())
cnt = 0
for i in range(0, n+1): // 시
for j in range(60): // 분
for k in range(60): // 초
if '3' in str(i) + str(j) + str(k):
cnt += 1
print(cnt)