[코딩테스트] 구현 : 시뮬레이션과 완전 탐색
➕ 나동빈님 이코테에서 들은 내용을 기반으로 정리하고 공부한 게시글입니다.
✔ 구현이란?
구현(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인 지도와 계획서이다.
👉 문제해결과정
- 일련의 명령에 따라서 개체를 이동시킨다는 점에서 시뮬레이션 유형으로도 분류된다.
- 먼저 이동계획서에 있는 문자들을 실제 x,y가 이동할 수 있는 숫자로 바꾼다.
- 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이 하나라도 포함되는 모든 경우의 수를 구하여라.
👉 문제해결과정
- 가능한 경우의 수를 모두 검사해보는 탐색방법인 점에서 완전 탐색 유형으로도 분류된다.
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인 지도와 계획서이다.
# 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)
정수 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 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
👉 문제해결과정
알파벳 대문자와 숫자(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))
🌱 결론
구현은 자신이 사용할 수 있는 라이브러리에 따라, 사용 언어에 따라 난이도가 달라진다. 따라서 많은 문제들을 풀어보며 언어에 따른 다양한 라이브러리를 경험해보는 것이 중요하다.
Author And Source
이 문제에 관하여([코딩테스트] 구현 : 시뮬레이션과 완전 탐색), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@soy0830/코딩테스트-구현-999hbyoc저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)