.png)
구현
코딩 테스트에서 구현(implementation)이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다.
완전 탐색
모든 경우의 수를 주저 없이 다 계산하는 해결 방법
시뮬레이션
문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야하는 문제 유형
구현 시 고려해야 할 메모리 제약 사항
C/C++에서 변수의 표현 범위
- 전통적으로 프로그래밍 언어에서 정수형을 표현할 때는 int 자료형을 주로 사용하며 int형의 크기는 4바이트이다.
- 기본 int 자료형의 표현 범위는 -2,147,483,648 ~ 2,147,438,647
- 더 큰 수를 사용하려면 long long과 같은 자료형 사용
C/C++/자바에서 정수형 종류에 따른 범위
| 정수형 종류 | 자료형의 크기 | 자료형의 범위 |
|---|---|---|
| int | 4바이트 | -2,147,483,648 ~ 2,147,483,647 |
| long | 4바이트 | 2,147,483,648 ~ 2,147,483,647 |
| long long | 8바이트 | 9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 |
- 파이썬에서는 직접 자료형을 지정할 필요 없고 매우 큰 수의 연산 또한 기본적으로 지원한다.
파이썬에서 리스트 크기
- 대체로 코딩 테스트에서는 128~512MB로 메모리를 제한한다.
int자료형 데이터의 개수에 따른 메모리 사용량
| 데이터의 개수(리스트의 길이) | 메모리 사용량 |
|---|---|
| 1,000 | 약 4KB |
| 1,000,000 | 약 4MB |
| 10,000,000 | 약 40MB |
채점 환경
- 파이썬은 C/C++에 비해 동작 속도가 느리다.
- 파이썬은 1초에 2000만 번의 연산을 수행한다고 가정하면 크게 무리가 없다.
구현 문제에 접근하는 방법
- 자동 채점방식을 이용하는 코딩 테스트 환경에서는 점점 Pypy3를 지원하는 곳이 늘고 있다.
- Pypy3는 파이썬3의 문법을 그대로 지원하고 파이썬3보다 실행속도가 더 빠르다.
- 대략 1초에 2000만 번에서 1억 번 정도의 연산을 처리할 수 있다.
- 만약 Pypy3를 지원한다면 이를 이용하도록 하자!
예제1 상하좌우
문제
여행가 A는 N × N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 × 1 크기의 정사각형으로 나누어져 있다.
가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다.
여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)이다. 우리 앞에는 여행가 A가
이동할 계획이 적힌 계획서가 놓여 있다.
계획서에는 하나의 줄에 띄어쓰기를 기준으로 L, R, U, D 중 하나의 문자가 반복적으로 적혀있다.
각 문자의 의미는 다음과 같다.
- L: 왼쪽으로 한 칸 이동
- R: 오른쪽으로 한 칸 이동
- U: 위로 한 칸 이동
- D: 아래로 한 칸 이동
이때 여행가 A가 N × N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다.
입력 조건
첫째 줄에 공간의 크기를 나타내는 N이 주어집니다. (1<=N<=100)
둘째 줄에 여행가 A가 이동할 계획서 내용이 주어집니다. (1<=이동 횟수<=100)
출력 조건
첫째 줄에 게임의 룰에 맞게 선택한 카드에 적힌 숫자를 출력
입력 예시
5
R R R U D D
출력 예시
3 4
풀이
- dictionary에 상하좌우로 이동할때마다 더해줄 값을 저장해둔다.
- 입력받은 계획을 돌면서 해당하는 키값에 있는 값을 1,1에 더해준다.
- 더해주었을 때 정사각형 범위를 벗어나면 다시 돌려놓는다.
코드
N = int(input())
lst = input().split()
arr = [1,1]
dic = {'L':[0,-1],'R':[0,1],'U':[-1,0],'D':[1,0]}
for i in lst:
arr[0] += dic[i][0]
arr[1] += dic[i][1]
if arr[0] == 0:
arr[0] = 1
if arr[0] == N+1 :
arr[0] == N
if arr[1] == 0:
arr[1] = 1
if arr[1] == N+1 :
arr[1] == N
print(arr)예제2 시각
문제
정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는
모든 경우의 수를 구하는 프로그램을 작성하라.
입력 조건
첫째 줄에 정수 N이 입력된다.(0<=N<=23)
출력 조건
00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다.
입력 예시
5
출력 예시
11475
풀이
3중 for문을 이용했다
최대 경우의 수는 24 x 60 x 60으로 3중 for문을 사용해도 된다.
N = int(input())
cnt = 0
for i in range(N+1):
for j in range(60):
for k in range(60):
s = str(i) + str(j) +str(k)
if '3' in s:
cnt+=1
print(cnt)