[코딩테스트] 구현 : 시뮬레이션과 완전 탐색

16516 단어 이코테이코테

➕ 나동빈님 이코테에서 들은 내용을 기반으로 정리하고 공부한 게시글입니다.

✔ 구현이란?

구현(Implementation)은 머리속에 있는 알고리즘을 실제 코드로 바꾸는 과정을 뜻한다. 따라서 컴퓨터가 수행할 수 있도록 구현하는 일은 반드시 필요한 과정이다.
우리가 알고리즘에서 구현 유형의 문제는 풀이를 떠올리는 것은 쉽지만 소스 코드로 바꾸는 것이 어려운 문제를 지칭한다.

✔ 문제1 : 상하좌우

A는 N X N 크기의 정사각형 공간 위에 서있다. 그리고 이 공간은 1 X 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1,1), 가장 오른쪽 아래 좌표는 (N,N)이다. 시작좌표는 항상 (1,1)이며 A는 상,하,좌,우 방향으로 이동할 수 있다.( 1 <= N <= 100, 1 <= 이동횟수 <= 100)
이동 계획서에는 L, R, U, D의 문자가 반복적으로 적혀있다.
L : 왼쪽으로 한 칸 이동
R : 오른쪽으로 한 칸 이동
U : 위로 한 칸 이동
D : 아래로 한 칸 이동
다음은 N = 5인 지도와 계획서이다.

👉 문제해결과정

  • 일련의 명령에 따라서 개체를 이동시킨다는 점에서 시뮬레이션 유형으로도 분류된다.
  1. 먼저 이동계획서에 있는 문자들을 실제 x,y가 이동할 수 있는 숫자로 바꾼다.
  2. for문을 활용하여 계획서 순서에 따라 x,y가 이동할 수 있도록 한다.
# N 입력받기
n = int(input())
x, y = 1, 1 #현재위치
# plan 입력받기
plans = input().split()

# L, R, U, D에 따른 이동 방향
dx = [0, 0, -1, 1] # x축 direction
dy = [-1, 1, 0, 0] # y축 direction
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)

✔ 문제2 : 시각

정수 N이 입력되면 00시 00분 00초 부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하여라.

👉 문제해결과정

  • 가능한 경우의 수를 모두 검사해보는 탐색방법인 점에서 완전 탐색 유형으로도 분류된다.

모든 시각을 하나씩 다 출력해서 해당하는 시각이 나타나면 count를 올린다.

# N를 입력받기(hour에 해당함)
hour = int(input())

for i in range (hour+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)

✔ 문제3 : 왕실의 나이트

8 X 8 좌표평면에서 나이트는 L자 형태로만 이동할 수 있으며 좌표 평면 밖으로는 나갈 수 없다.
특정 위치에서는 다음과 같은 2가지 경우로 이동할 수 있다.(L자 형태)
1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기
2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기
8 X 8 좌표평면에서 나이트의 위치가 주어졌을 때, 나이트가 이동할 수 있는 경우의 수를 출력하라.

👉 문제해결과정

나이트의 위치에서 8가지 이동 방향 중 가능한 이동 방향의 수를 구한다.

night = input()

# 행열과 xy는 반대
# 나이트의 행
night_row = int(night[1]) 
# 나이트의 열
# 열은 a가 시작점이기에 a로 부터 얼마나 떨어져있는지 계산해야함
night_column = int(ord(night[0])) - int(ord('a')) + 1 

#나이트가 이동할 수 있는 방향 8개
steps = [(2,1),(1,2),(2,-1),(-1,2),(-2,1),(1,-2),(-2,-1),(-1,-2)]

count = 0
for step in steps:
    # 이동하고자 하는 위치 확인
    next_row = row + step[0]
    next_column = column + step[1]
    # 해당 위치로 이동이 가능하다면 카운트 증가
    if next_row >= 1 and next_row <= 8 and next_column >= 1 and next_column <= 8:
        count += 1

print(count)

✔ 문제4 : 문자열 재정렬

알파벳 대문자와 숫자(0~9)로만 구성된 문자열이 입력되면 모든 알파벳을 오름차순으로 정렬하여 출력하고, 그 뒤에 모든 숫자를 더한값을 이어서 출력하라.
예) K1KA5CB7 -> ABCKK13

👉 문제해결과정

문자열이 입력되면 앞에서 부터 하나씩 문자를 확인한다.
만약, 숫자일 경우 num에 더하고 알파벳일경우 리스트에 저장해 추후에 리스트를 오름차순으로 출력한다.

string = list(input())
alpha = []
num = 0

for i in string:
	if i.isalpha() :
    	alpha.append(i)
    else:
    	num += int(i)
        
alpha.sort() # 알파벳 오름차순으로 정렬

if num == 0:
	print(alpha)
else:
	alpha.appent(str(num))
	print(''.join(alpha))

🌱 결론

구현은 자신이 사용할 수 있는 라이브러리에 따라, 사용 언어에 따라 난이도가 달라진다. 따라서 많은 문제들을 풀어보며 언어에 따른 다양한 라이브러리를 경험해보는 것이 중요하다.

좋은 웹페이지 즐겨찾기