[Inplementation] 아이디어를 코드로 바꾸는 구현
카테고리: Algorithm
1. 아이디어를 코드로 바꾸는 구현
피지컬로 승부하기
구현(Implementaion) 이란 ‘머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정’
이를 위해서는, 프로그래밍 언어의 문법을 정확히 알고 있어야 하며 문제의 요구사항에 어긋나지 않는 답안 코드를 실수 없이 작성해야 한다.
책에서 이렇게 귀엽게 표시를 해놨네요😀
이 책에서는 완전 탐색, 시뮬레이션 유형을 모두 구현유형으로 묶어서 다루고 있다.
완전 탐색 은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 을 의미하고, 시뮬레이션 은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행 해야 하는 문제 유형을 의미한다.
2. 구현 시 고려해야 할 메모리 제약 사항
C / C++와 Java에서 정수형 종류에 따른 범위
위와 같이, C / C++ / Java의 경우에는 자료형의 범위에 따라서 사용해야하는 정수형이 달라지는 Python에서는 프로그래머가 직접 자료형을 지정할 필요가 없으며 매우 큰 수의 연산 또한 기본적으로 지원한다. 다만, Python에서의 실수형 변수는 다른 언어와 마찬가지로 유효숫자에 따라서 연산 결과가 원하는 값이 나오지 않을 수 있다는 점을 기억하자!
Python에서 리스트 크기
시스템 내부적으로는 다음 표에서 것과 유사한 크기만큼 메모리를 차지한다.
파이썬은 다른 언어에 비해서 구현상의 복잡함이 적은 편이지만 데이터 처리량이 많을 때는 꼭 메모리 제한을 고려하도록 하자.
다만, 일반적인 코딩 테스트 수준에서는 메모리 사용량 제한보다 더 작은 크기의 메모리를 사용해야 한다는 점 정도만 기억하면 된다.
3. 채점 환경
파이썬은 C/C++에 비해 동작 속도가 느리다. 그래서 파이썬을 선택했을 경우 C/C++에 비해 2배의 수행 시간 제한을 적용하기도 한다.
일반적인 기업 코딩 테스트 환경에서는 파이썬으로 제출한 코드가 1초에 2,000만 번의 연산을 수행한다고 가정하면 크게 무리가 없다는 점만 기억하자.
예를 들어, 시간 제한이 1초이고, 데이터의 개수가 100만 개인 문제가 있다면 일반적으로 시간 복잡도 O(NlogN) 이내의 알고리즘을 이용하여 문제를 풀어야 한다. 따라서, 알고리즘 문제를 풀 때는 시간 제한과 데이터의 개수를 먼저 확인한 뒤에 어느 정도의 시간 복잡도의 알고리즘으로 풀어야 할지 예측해야한다.
4. 구현 문제에 접근하는 방법
보통 구현 유형의 문제는 사소한 입력 조건 등을 문제에서 명시해준다. 그리고, 문자열이나 큰 정수를 처리하는 문제가 출제되는 경우가 많은데, C/C++, JAVA에 비해서 처리가 쉬워 기본 문법만 알아도 상대적으로 구현 유형의 문제를 쉽게 해결해 갈 수 있다.
구현 측면에서는 책에서는 아래와 같이 정리하고 있다.
예제1. 상하좌우
난이도 : ⭐
여행가 A는 N X N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 X 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)이다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있다.
계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여, L, R, U, D중 하나의 문자가 반복적으로 적혀있다. 각 문자의 이미는 다음과 같다.
- L : 왼쪽으로 한 칸 이동
- R : 오른쪽으로 한 칸 이동
- U : 위로 한 칸 이동
- D : 아래로 한 칸 이동
이때 여행가 A가 N X N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다. 예를 들어 (1, 1)의 위치에서 L 혹은 U를 만나면 무시된다. 다음은 N = 5인 지도의 계획서이다.
이 경우 6개의 명령에 따라서 여행가가 움직이게 되는 위치는 순서대로 (1, 2), (1, 3), (1, 4), (1, 4), (2, 4), (3, 4)이므로, 최종적으로 여행가 A가 도착하게 되는 곳의 좌표는 (3, 4)이다. 다시 말해 3행 4열의 위치에 해당되므로 (3, 4)라고 적는다. 계획서가 주어졌을 때 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오.
입력 조건
- 첫째 줄에 공간의 크기를 나타내는 N이 주어진다. (1 <= N <= 100)
- 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다. (1 <= 이동 횟수 <= 100)
출력 조건
- 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X, Y)를 공백으로 구분하여 출력한다.
입력 예시
5
R R R U D D
출력 예시
3 4
나의 풀이
n = int(input()) # 공간의 크기 입력 받기
move = list(map(str, input().split())) # 이동할 계획서 내용 입력 받기
length = len(move)
now_pos = [1, 1]
for moving in move:
if moving == "L":
if now_pos[1] == 1:
continue
else:
now_pos[1] -= 1
elif moving == "R":
if now_pos[1] == n:
continue
else:
now_pos[1] += 1
elif moving == "U":
if now_pos[0] == 1:
continue
else:
now_pos[0] -= 1
else:
if now_pos[0] == n:
continue
else:
now_pos[0] += 1
print(now_pos)
문제 해설
이 문제를 요구사항대로 구현하면 연산 횟수는 이동 횟수에 비례하게 된다. 예를 들어 이동 횟수가 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)
예제2. 시각
난이도 : ⭐
정수 N이 입력되면 00시 00분 00초부터 N시 59분 59까지의 모든 시각 중에서 3이 하나로도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다.
- 00시 00분 03초
- 00시 13분 30초
반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각이다.
- 00시 02분 55초
- 01시 27분 45초
입력 조건
- 첫째 줄에 정수 N이 입력된다. (0 <= N <= 23)
출력 조건
- 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나로도 포함되는 모든 경우의 수를 출력한다.
입력 예시
5
출력 예시
11475
나의 풀이
n = int(input()) # N 입력 받기
count = 0
for i in range(n + 1):
for j in range(60):
for k in range(60):
if '3' in str(i):
count += 1
elif '3' in str(j):
count += 1
elif '3' in str(k):
count += 1
print(count)
문제 해설
이 문제는 모든 시각의 경우를 확인해서 풀 수 있는 문제이다. 이유는? 하루는 86,400초로 모든 걸 다봐도 100,000개가 되지 않으므로 2초 안에 해결할 수 있다.
이러한 유형은 완전 탐색유형으로 분류되기도 한다. 완전 탐색 알고리즘은 가능한 경우의 수를 모두 검사해보는 탐색 방법이다. 일반적으로 완전 탐색 알고리즘은 비효율적인 시간 복잡도를 가지고 있으므로 데이터 개수가 큰 경우 정상적으로 작동하지 않을 수 있다. 그래서 확인해야할 전체 데이터가 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)
🐢 현재 공부하고 있는 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 저자 의 책을 학습하며 기록 및 정리를 하기위한 내용들입니다. 🐢
감사합니다.😊
댓글남기기