구현

구현 알고리즘은 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭한다.
구현 유형으론 시뮬레이션 및 완전 탐색 문제가 있는데 이 두 문제는 2차원 공간에서의 방향 벡터가 자주 활용된다.
좌표를 기준으로 움직일때 표현할수 있는 방법중 하나이다. 예시로 동, 북, 서, 남을 들었지만 문제에서 좌표를 숫자가 아닌 문자로 주는 경우도 있고 왼쪽, 오른쪽, 위, 아래로 주는 경우가 있으니 적절히 활용해야한다.

#동북서남으로 움직일때 x와 y의 값으 변화(1칸 움직이는 기준)
dx = [0, -1, 0, -1]
dy = [1, 0, -1, 0]

#현재위치
x, y = 2, 2

# 다음위치 
for i in range(4):
	nx = x + dx[i]
    ny = y + dy[i]
    print(nx, ny)

시뮬레이션

상하좌우 문제

이문제는 시간안에 풀지 못해 해설을 보고 이해 했다. 해설을 보고 나니 간단한 문제였기 때문에 같은 유형의 다른 문제를 많이 풀어봐야겠다.

space = int(input())

# 시작위치
x, y = 1, 1

directions = input().split()
# L,R,U,D일때 x, y의 변화
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

move = ['L','R','U','D']

for direction in directions:
	for m in range(len(move)):
    	# 이동계획과 같은 move요소의 인덱스를 찾고 그 인덱스로 x,y의 이동 위치를 구한다.
		if direction == move[m]:
			res_x = x + dx[m]
			res_y = y + dy[m]
	# 범위를 벗어나면 다음 방향으로 넘어간다.
	if res_x < 1 or res_y < 1 or res_x > space or res_y > space:
		continue

	x = res_x
	y = res_y

print(x, y)

왕실의 나이트 문제

여기서는 알파벳을 알파벳 순서인 수로 바꾸는 방법을 알게 되었다. 나는 딕셔너리에 키와 밸류로 각 알파벳에 숫자를 지정해 주었는데 이렇게 할 필요 없이 int(ord(알파벳)) - int(ord('a')) +1 로 구할 수 있다.


내가 푼 방법

move = input()
re = {
	'a' : 1,
	'b' : 2,
	'c' : 3,
	'd' : 4,
	'e' : 5,
	'f' : 6,
	'g' : 7,
	'h' : 8
}

night = list(move)
night[0] = re[night[0]]
night[1] = int(night[1])
print(night)
# 나이트는 체스판 안에서 움직인다고 치면 8개 방향으로 갈 수 있다.

# x, y기준 이라고 할때

direc =  [
	( 1,  2),
	(-1,  2),
	( 1, -2),
	(-1, -2),
	( 2,  1),
	( 2, -1),
	(-2,  1),
	(-2, -1)
	]
count = 0
res = []
for i,j in direc:
	if 1 <= night[0]+i <= 8 and 1 <= night[1]+j <= 8:
		count += 1

print(count)

해설

move = input()
row = int(move[1])
column = int(ord(move[0])) - int(ord('a')) + 1

steps = [
	( 1,  2),
	(-1,  2),
	( 1, -2),
	(-1, -2),
	( 2,  1),
	( 2, -1),
	(-2,  1),
	(-2, -1)
	]

result = 0
for step in steps:
  next_row = row + step[0]
  next_col = column + step[1]
  if 1 <= night[0]+i <= 8 and 1 <= night[1]+j <= 8:
		result += 1
print(result)

완전탐색

3이 하나라도 들어간 시간 구하기

이문제의 경우 0시부터 n시까지의 모든 시간을 리스트로 만들고 리스트 안에 3과 33이 포함 되었는지 확인하는 방식으로 풀었었다. 해설을 보고 리스트를 만들 필요가 없었다는걸 알게 되었다.

n = int(input())
count = 0

for i in range(0, n+1):
	for j in range(60):
		for k in range(60):
			if '3' in str(i)+str(j)+ str(k):
				count += 1

print(count)

문자열 재정렬

이문제도 비슷 하게 풀었지만 해설 코드가 더 깔끔하기 때문에 해설 코드로 기록해 놓겠다.
''.join만 잘 기억해도 쉽게 풀 수 있는 문제이다.

s = input()
result = []
value = 0

for i in s:
	if i.isalpha():
		result.append(i)
	else:
		value += int(i)

result.sort()

if value != 0:
	result.append(str(value))

print(''.join(result))