1. 구현
구현 자체는 문제에 대한 방안, 알고리즘을 실제 코드로 옮기는 과정을 의미한다.
보통 모든 경우의 수를 생각하거나, 빠짐없이 상황을 탐색하고자 할 때를 의미하는데 알고리즘 구현은 곧 생각한 알고리즘을 실제로 구현하는 과정이 어려운 경우를 일컫는다.
- 방안/알고리즘을 떠올리기는 쉽지만 소스코드로 옮기기 어려운 경우
- 알고리즘 자체는 간단한데 코드가 지나치게 길어지는 경우
→ 이는 보통 라이브러리의 활용, 프로그래밍 언어의 적용 관점에서 불가피하게 나타나는 경우가 많으므로 라이브러리를 평소에 많이 알고있다면 해법에 도움이 많이 된다. - 실수 연산을 다루고, 특정 소수점까지 구해야 하는 경우
- 문자열을 특정 기준에 따라 부분적으로 값(부분문자열)을 도출해야하는 경우
- 2차원 행렬을 이용하는 경우
2. 2차원 행렬
특히 2차원 행렬 등 이동할 수 있는 모든 경우의 수를 찾는 알고리즘은 전형적인 구현, 완전탐색에 해당한다.
현재 위치를 x,y로 하고 이동할 수 있는 경우의 수(dx,dy 혹은 튜플 형태로 각 이동할 수 있는 변위벡터를 설정)를 적용하는 방안을 마련하는 것이 가장 중요하다.
key point:
- 방향벡터를 사용하는지(튜플로 설정, 별도의 dx dy가 아닌 특별한 경우의 수가 존재할 때)
- 일반적인 dx, dy(행렬에서 기본적으로 이동할 수 있는 방향벡터를 동,서,남,북 경우에 따라 설정)를 사용하는지
2-1. 상하좌우로의 이동
여행가 A는 N*N크기의 정사각형 공간위에 서있다고 한다.
이 공간의 최좌상단 좌표는 1,1이고 최우하단 좌표는 N,N이고, 여행가 A가 상,하,좌,우 방향으로 이동할 수 있으며 시작좌표는 항상 1,1이다.
여행가 A가 이동할 수 있는 이동명세서는 다음과 같다.
- L : 왼쪽 1칸, R : 오른쪽 1칸, U : 위쪽 1칸, D : 아래쪽 1칸
이때 최종 좌표를 구하는 알고리즘은 무엇인가?
단, 정사각형 공간을 벗어나는 움직임은 pass한다.
import sys
#입력값
N = int(input())
plans = list(map(str, sys.stdin.readline().split()))
#현재위치
x, y = 1, 1
#L, R, U, D에 따른 명세서
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
moveTypes = ['L', 'R', 'U', 'D']
#이동 계획에 따라 그대로 x+dx and y+dy
for plan in plans:
for i in range(len(moveTypes)):
if plan == moveTypes[i]:
nx = x + dx[i]
ny = y + dy[i]
#nx, ny가 공간을 벗어나는 경우엔 무시
if nx < 1 or ny < 1 or nx > N or ny > N:
continue #강제로 다음 반복을 수행
x,y = nx, ny
print(x,y)→ 일반적인 방향벡터를 사용하는 경우이다.
2-2. 체스 나이트의 이동
왕국의 왕실 정원이 8*8의 좌표평면의 크기를 가진다고 가정한다.
이때 정원 안에 있는 나이트가 이동할 수 있는 모든 경우의 수를 출력하는 알고리즘은?
- 정원밖으로는 나갈 수 없다.
- 행의 위치는 양의 정수로(1,2,3..), 열의 위치는 알파벳 문자로(a,b,c..) 표현한다
- 현재 위치는 열행으로 표현한다(예를 들어 a2)
- 단, 나이트는 특정 위치에서 다음과 같은 2가지 경우로 이동가능하다.
#수평으로 2칸 이동한 후 수직으로 1칸 이동하기
#수직으로 2칸 이동한 후 수평으로 1칸 이동하기
기본적으로 이동하는 문제는 갈 수 있는 dx, dy를 잘 표현할 수 있는가가 중요하다.
매번 갈 수 있는 경로가 가능한 경우인지 확인할 수 있으면 된다.
INPUT = input()
#행
row = int(INPUT[1])
#열(*아스키코드 형태로 바꾸기)
column = int(ord(INPUT[0]))-int(ord('a'))+1
#나이트가 이동할 수 있는 8가지 방향(*튜플)
#각 이동할 수 있는 행/열의 값임
steps = [(-2,-1),(-1,-2),(1,-2),(2,-1),(2,1),(1,2),(-1,2),(-2,-1)]
result = 0
for step in steps:
nextRow = row + step[0]
nextColumn = column + step[1]
#경계조건
if nextRow>8 or nextRow<1 or nextColumn>8 or nextColumn<1:
result = result + 1
print(result)2-3. 특정 숫자가 포함된 모든 시간 경우의 수
정수 N이 입력되면, 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중 N이 하나라도 포함되어있는 모든 경우의 수를 구하는 알고리즘은?
모든 경우의 수를 구하는 완전탐색(구현유형, Brute Forcing)의 유형이다.
참고로 python에서 수용하는 1초 연산횟수는 약 2천만번이고, 가능한 모든 경우의 수를 탐색하는 방법은 이 수용하는 범위 내에서 구할 수 있으면 좋다.
H = int(input())
count = 0
#시 - 분 - 초
for i in range(H + 1):
for j in range(60):
for k in range(60):
#시간, 분, 초에 대해 문자열을 만들고, 해당 문자가 포함되어있는지 아래와 같이 기술
if str(H) in str(i)+str(j)+str(k):
count = count + 1
print(count)2-4. 문자열 재배열하기
알파벳대문자와 숫자로 구성된 문자열이 주어진다.
이때 모든 알파벳을 오름차순으로 출력하고, 그 뒤에 모든 숫자의 합을 붙인 문자열을 출력한다.
INPUT = input()
#알파벳은 별도의 리스트에 저장
#숫자는 따로 합을 구해서 리스트에 append
result = []
value = 0
for string in INPUT:
#이러한 메소드들을 잘 활용할 수 있어야 한다
#아스키코드 이렇게 복잡하게 생각할 필요가 없음
if string.isalpha():
result.append(string)
else:
value = value + int(string)
#알파벳 오름차순 정렬
result.sort()
#숫자가 하나라도 존재한다면 뒤에 그대로 삽입
if value != 0:
result.append(str(value))
#이상태는 리스트 형태
print(result)
#이를 문자열로 변환하여 출력
#리스트에 포함되어있는 문자열들을 join(쭉 나열)
#기준에 맞추어 나열('' -> 공백없이)
print(' '.join(result))이때 중요한 것은 isalpha()(문자확인)나 ''.join(list)(list를 문자열형태로 일괄적으로 나열된 형태, ''은 나열기준)와 같이 라이브러리를 적재적소에 잘 활용한다면 코드가 길어지는 것을 방지할 수 있다는 점이다.
