구현?
코딩 테스트에서 구현이란, 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 어떤 문제를 풀던 간에 소스코드를 작성하는 과정은 필수이므로, 지엽적인 개념이라고도 볼 수 있다. 그러나 문제 해결 분야에서의 구현은 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미한다.
구현을 위해선느 프로그래밍 언어의 문법을 정확히 인지하고 있어야 한다. 또한 문제 속의 조건이나 요구사항을 잘 충족하는지 고려해야 한다. 본 교재에서는 두 가지 유형의 구현 알고리즘을 다루고 있는데, 모든 경우의 수를 전부 계산하는 완전 탐색 알고리즘과, 문제에서 제시한 알고리즘을 한 단계식 차례대로 수행하는 시뮬레이션 알고리즘이다.
주의사항
파이썬 환경에서는 다른 언어들과 달리 정수 길이에 따른 자료형을 고려할 필요는 없지만, 데이터 처리량이 많을 때는 메모리 제한을 고려해야 한다. 컴퓨터 메모리 구조 쪽을 공부해 보는 것도 좋을 듯 하다.
예제4-1 (C4Q1-1) 상하좌우
문제
여행가 A는 NxN의 정사각형 공간 위에 서 있다. 이 공간은 1x1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1,1)이며, 가장 오른쪽 좌표는 (N,N)에 해당한다. 상하좌우 방향으로 이동할 수 있으며 이는 계획서에서 U,D,L,R로 표현된다. 그러나 NxN 크기의 정사각형 공간을 벗어나는 움직임 명령은 무시된다.
입력 조건
1. 첫째 줄에 공간의 크기를 나타내는 N이 주어진다. (1<=N<=100)
2. 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다. (1<=이동횟수<=100)
출력 조건
1. 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표를 공백으로 구분하여 출력한다.
내 코드
n = int(input())
cmd = list(input().split())
col=1
row=1
# 행과 열을 좌표로
# L,R은 col 제어
# U,D는 row 제어
for i in range(len(cmd)):
if(cmd[i]=='L' and col>1):
col-=1;
elif(cmd[i]=='R' and col<n):
col+=1;
elif(cmd[i]=='U' and row>1):
row-=1;
elif(cmd[i]=='D' and row<n):
row+=1;
print(row,col)해설 입력받은 방향 리스트를 if문을 통해 비교하고, 지도 밖을 넘지 않는 선에서 좌표를 이동시켰다. 리스트 크기만큼 반복문을 돌려 좌표를 이동하였고 반복문이 끝나면 최종 이동된 좌표값을 출력한다.
분석 여느 때와 같이 map(int(input().split())을 통해 입력을 받으려고 하였다. 그러나 이를 if문 속 인자로 사용하는 과정에서 오류가 발생하였다. map함수는 int형으로 매핑되었지만 map이라는 다른 자료형태를 갖고 있음을 알 수 있었다. 그래서 정수로의 활용을 위한 입력을 받을 때는 int(input())을 사용해야 한다는 것을 알게 되었음.
교재 코드
n = int(input())
x,y = 1,1
plans = input().split()
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)교재해설 교재에서는 좌표의 이동 수치와 방향을 리스트로 저장해놓았다. 리스트를 전부 돌며 입력 방향과 비교하여 좌표를 이동시켰고, 추가로 지도 밖으로 나갈 때의 제한을 걸어 주었다. 이러한 문제는 일련의 명령에 따라 개체를 차례대로 이동시킨다는 점에서 시뮬레이션 유형으로 분류된다. 이 문제를 요구사항대로 구현하면 이동횟수에 비례하는 O(N)의 시간 복잡도를 갖는다.
예제4-2 (C4Q1-2) 시각
문제
정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하라.
입력 조건
1. 첫째 줄에 정수 N이 입력된다. (0<=N<=23)
출력 조건
1. 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다.
교재 코드
n = int(input())
result = 0
for i in range(n+1):
for j in range(60):
for k in range(60):
if '3' in str(i) + str(j) + str(k):
result+=1
print(result)해설 문자열을 분리해 3이 있는지 찾아보자는 아이디어는 떠올릴 수 있었지만, Syntax부분에서 막혔다. 그래서 문제의 유형이 구현이 아닌가 싶다. 그래서 if문으로 모든 경우에 조건을 거는 비효율적인 방법을 떠올렸다. (ex. i=3 or i=13 or i=23 or i=33.....) 그리고 문자열속에 원하는 문자가 있는지 확인하는 문법을 배웠다... '문자' in str(문자열)은 Boolean 값을 반환한다.
