[이코테] 구현

  구현

• 코딩 테스트에서 구현이란 '머리속에 있는 알고리즘을 소스코드로 바꾸는 과정'
• 문제 해결 분야에서 구현 유형의 문제는 '풀이는 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미
• 문제가 구현하기 어려운 문제는 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제, 특정 소수점 자리까지 출력해야 하는 문제, 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야(파싱) 하는 문제, 적절한 라이브러리를 찾아서 사용해야 하는 문제 등이 있음
• [이코테] 책에선 완전 탐색, 시뮬레이션 유형을 모두 '구현' 유형으로 묶어서 다룸. 완전탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미, 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형을 의미함

 

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

  C/C++에서 변수의 표현 범위

 C/C++ 과 JAVA에서는 자료형의 표현 크기와 범위를 신경써서 알고리즘 문제를 구현해야하지만, 파이썬의 경우 직접 자료형을 지정할 필요 가 없기 때문에 고민할 필요가 없다

 

  파이썬에서 리스트 크기

파이썬에서 리스트를 이용할 때 코딩 테스트의 메모리 제한을 고려해야 한다. 대부분 코딩 테스트에서 128 ~ 512MB로 메모리를 제한하는데, 이러한 제한들을 염두해 두고 코딩 해야한다. 파이썬은 다른 언어에 비해 구현상의 복잡함이 적으나, 데이터 처리량이 많을 때 꼭 메모리 제한을 고려해야 한다. 리스트를 여러 개 선언하고, 그 중에서 크기가 1,000만 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 풀 수 없게 되는 경우도 있다는 점을 기억해야 한다. 다음은 int 자료형에서 유사한 크기만큼의 메모리 사용량을 보여준다.

 

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

 채점 환경

코딩 테스트 환경에서는 시간제한과 메모리 제한의 대한 정보가 적혀 있다. 여기서 시간 제한이 1초일 때, 데이터의 개수가 100만 개인 문제가 있다면 일반적으로 시간 복잡도는 O(NlogN) 이내의 알고리즘을 이용하여 문제를 풀어야 한다. N=1,000,000 일 때 Nlog(2)N 은 약

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

 

 

[ 예제 4 -1 ] 상하좌우

시간 제한 : 1초 메모리 제한 : 128 MB 여행가 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번 일 때 시간 복잡도는 O(N)이며 시간 복잡도  는 매우 널널한 편임. 이러한 문제는 일련의 명령에 따라서 개체를 이동시킨다는 점에서 시뮬레이션 유형으로 분류되어 구현이 중요한 대표 적인 문제 유형임

: 이 문제의 중요한 포인트는 방향 L, R, U, D 이동 시 좌표를 구현하여 처리한다는 점. 예를 들어 동, 북, 서, 남을 처리할 때는 dx = [0, -1, 0, 1] dy = [1, 0, -1, 0] 로 처리하며 이동한다는 점이 포인트

: 또한 좌표 평면 즉, 공간을 벗어나는 경우는 무시한다는 것도 코드상 구현해주는 점도 포인트

 

# 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)

 

 

[ 예제 4 -2 ] 시각

시간 제한 : 2초 메모리 제한 : 128MB  정수 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

 

 

문제 접근

 

: 이러한 유형을 완선 탐색유형으로 분류 되며, 완전 탐색 알고리즘은 가능한 경우의 수를 모두 검사해보는 탐색 방식이며 이러한 방식은 비효율적인 시간 복잡도를 가지고 있기 때문에 확인(탐색) 해야할 전체 데이터의 개수가 100만 개 이하일 떄 완전 탐색을 이용하면 적절함

: 이 문제는 모든 시각의 경우를 하나씩 모두 세서 쉽게 풀 수 있는 문제임. 왜냐하면 하루는 86,400초로 00시 00분 00초부터 23시 59분 59초까지의 모든 경우의 수는 86,400가지 밖에 존재하지 않기 때문에 파이썬의 문자열 연산을 통해 3시각에 포함되어 있는지 확인해도 시간 제한 2초안에 문제를 해결할 수 있음

: 단순히 시각을 1씩 증가시키면서 3이 하나라도 포함되어 있는지 확인함. 따라서 전체 시-분-초에 대한 경우의 수 24 - 60 - 60 이며 3중 반복문을 통해 쉽계 계산이 가능함

: 소스 코드에서 포인트는 매 시각 문자열로 바꾼 다음 문자열에 '3'이 포함되어 있는지 체크하는 방식으로 해결함.

 

 

# 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)

 

 

 

Ellen's thinking

: 이러한 구현문제 또한 그리디 알고리즘처럼 특정한 방식이 존재하는 게 아니라 여러 개의 문제 유형이 존재하는 것 같다. 따라서 구현 문제도 다양한 문제를 풀어보면서 어떤 문제로 접근해야하는지 생각의 힘을 기르면 좋을 것 같다.