[알고리즘] 구현 정리

구현 → 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정

시뮬레이션, 완전탐색 위주

유형

• 알고리즘은 간단한데, 코드가 길어지는 문제
• 실수연산을 다루고, 특정 소수좀까지 출력하는 문제
• 문자열을 특정 기준에 따라서 끊어 처리하는 문제 ( 중요 )
• 적절한 라이브러리를 찾아 사용해야하는 문제

2차원 공간은 행렬(matrix)의 의미로 사용

• 2차원 배열, 리스트 → (앞,뒤) ⇒ for 앞 - 뒤 → col row → x,y로 생각하기
• 
• 방향 벡터가 자주 사용

# ->(가로) 열 (y)  , (세로) 행 (x)
# 동 북 서 남
dx = [0,-1,0,1] 
dy = [1,0,-1,0]

문제1) 상하좌우

수행과정

• N * N , 가장 왼쪽 좌표 (1,1) = 시작좌표 ( 1≤ N ≤ 100 )
• 공간을 벗어나는 것은 무시하고 다음 명령 따르기

n = int(input())
x,y = 1,1
plans = input().split()

# 서 동 남 북
dx = [-1,1,0,0]
dy = [0,0,-1,1]

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

# 이동 계획을 하나씩 확인하기
for plan in plans:
	for i in range(len(move_type)): #이동후 좌표 구하기
		if plan == move_type[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) 시각문제 ( 완전탐색 )

수행과정

• 정수 N, 00시 00분 00초 ~ N시 59분 59초까지의 모든 시각에서 3이 하나라도 포함되는 모든 경우의 수

h = int(input())
count = 0
for i in range(h+1):
	for j in range(60):
		for k in range(60):
			if '3' in str(i)+str(j)+str(k):
				count += 1
print(count)

문제3) 왕실의 나이트

수행과정

• 8 * 8 체스판, 나이트는 L자로 이동, 체스판 밖으로 이동안함
• 이동은 수직2칸 → 수평1칸 or 수평2칸 → 수직 1칸
• 나이트 위치에 따라 이동 가능한 경우의 수를 구하기

idea

• 방향 벡터 사용
• 다음 위치 값이 체스판을 벗어나지 않으면 카운트 값 증가

input_data = input()
row = int(input_data[1])
col = int(ord(input_data[0]) - int(ord('a')) + 1 #열을 숫자로 표현하다는 조건때문

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

res = 0
for step in steps:
	next_row = row + step[0]
	next_col = col + step[1]
	if next_row >= 1 and next_row <= 8 and next_col >= 1 and next_col <= 8:
		res += 1

print(res)

문제4) 문자열 재정렬

수행과정

• 입력: 문자의 대문자 + 숫자 (0~9)

idea

• 문자를 오름차순으로 정렬 후, 숫자만 더한값을 뒤에 정렬

data= input()
res = []
value = 0

for x in data:
	if x.isalpha(): #isalpha는 알파벳을 확인하는 내장함수
		res.append(x)
	else:
		value += int(x)

res.sort()
if value != 0:
	res.append(str(value))
print(''.join(res))