출처 | https://www.youtube.com/watch?v=Mf0pYO8VAZk&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81
https://m.hanbit.co.kr/store/books/book_view.html?p_code=B8945183661
동빈나님 유튜브에서 이코테 정리한 내용이며 문제 시 삭제하겠습니다.
구현
- 풀이를 더올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭한다.
구현의 예시
-
알고리즘은 간단한게 코드가 지나칠 만큼 길어지는 문제
-
실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는문제
-
문자열을 특정한 기준에 따라서 끊어,처리해야하는문제
-
적절한 라이브러리를 찾아서 사용해야 하는 문제
일반적으로 알고리즘 문제에서의 2차원 공간을 행렬 의 의미로 사용된다.
for i in range(5):
for j in range(5):
print('(', i, ',', j, ')', end = ' ')
print()시물레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용된다.
#동, 북, 서, 남
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)<문제>
-
여행가 A는 N X N 크기의 정사각형 공간 위에 있다. 이 공간은 1 X 1 크기의 정사각형으로 나누어져있다. 가장 왼쪽 위 좌표는(1,1)이며, 가장 오른쪽 아래 좌표는 (N,N)에 해당한다.
-
여행가 A는 상,하,좌,우 방향으로 이동할 수 있으며, 시작 좌표는 항상(1,1)이다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있다.
-
계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L,R,U,D 중 하나의 문자가 반복적으로 적혀 있다.
- L: 왼쪽으로 한 칸 이동
- R: 오른쪽으로 한 칸 이동
- U: 위로 한 칸 이동
- D: 아래로 한 칸 이동
-
여행가 A가 N X N 크기의 정사각형 공간을 벗아나는 움직임은 무시된다. 예를 들어 (1.1)의 위치에서 L혹은 U를 만나면 무시된다. 다음은 N = 5인 지도와 계획서다.
key
-
요구사항대로 구현하면 되는 문제다.
-
일련의 명령에 따라서 개체를 차례대로 이동시킨다는 점에서 시뮬레이션 유형으로도 분류 되며 구현이 중요한 대표적인 문제 유형이다.
- 다만 알고리즘 교재나 문제 풀이 사이트에 따라서 다르게 일컬을 수 있으므로 코딩 테스트에서의 시뮬레이션 유형, 구현유형, 완전탐색유형은 서로 유사한 점이 많다는 정도로만 기억하자.
코드
n = int(input())
x,y = 1,1
plans = input().split()
#L,R,U,D에 따른 이동 방향이다.
dx = [0,0,-1,1]
dy = [-1, 1, 0, 0]
move = ['L', 'R', 'U', 'D']
# 이동 계획을 하나씩 확인한다.
for plan in plans:
#이동 후 좌표 구한다.
for i in range(len(move)):
if plan == move[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>
key
코드
a = int(input())
count = 0
for i in range(a+1):
for j in range(60): #분을 의미한다.
for k in range(60): #k는 초다. 3이 하나라도 포함되는지 확인하기 위해
if '3' in str(i) + str(j) + str(k): # 시 분 초를 3인걸 모두 포함하여 확인 한 것
count += 1
print(count)
+ 필자 분석
-
코드에서 i, j, k는 시간, 분, 초를 나타내며, 각각 0부터 a까지의 범위를 가진다.
-
여기서 문자열을 사용하여 시간, 분, 초를 나타내는 이유는 '3'이라는 문자를 포함하는지 확인하기 위해서사용. -> Python에서 문자열은 문자들의 연속이기 때문에, '3' in str(i) + str(j) + str(k)를 사용하여 시, 분, 초를 모두 합친 문자열에 '3'이 포함되어 있는지를 검사 진행.
예를 들어, i가 5, j가 30, k가 15인 경우를 생각해보면:
str(i)는 '5'
str(j)는 '30'
str(k)는 '15'
str(i) + str(j) + str(k)는 '53015'
따라서 '3' in str(i) + str(j) + str(k)는 '3' in '53015'로 변환된다. 이 때, '3'이라는 문자열이 포함되어 있으므로 조건이 참이 되고, count 변수가 증가하게 된다.
- 즉, 문자열을 사용하는 것은 시간, 분, 초의 값을 하나의 문자열로 합쳐서 '3'이 포함되어 있는지를 간단하게 확인하기 위해서 사용. 이렇게 하면 '3'이 포함된 모든 경우의 수를 찾아서 count 변수에 누적할 수 있다.
문제3 - 왕실의 나이트
설명
입출력
key
- 요구사항대로 구현하면 된다.
- 나이트의 8가지 경로를 하니씩 확인하며 각 위치로의 이동이 가능한지 확인한다.
- 리스트를 이용하여 8가지 방향에 대한 방향 벡터를 정의한다.
- 나이트의 8가지 경로를 하니씩 확인하며 각 위치로의 이동이 가능한지 확인한다.
코드
input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0])) - int(ord('a')) + 1
# 나이트가 이동할 수 있는 8가지 방향 정의
step = [(-2,-1), (-1,-2), (1,-2), (2,-1), (2,1), (1,2), (-1,2), (-2,1)]
# 8가지 방향에 대하여 각 위치로 이동이 가능한지 확인한다.
result = 0
for i in step:
#이동하고자 하는 위치 확인한다.
next_row = row + i[0]
next_column = column + i[1]
if next_row >= 1 and next_row <= 8 and next_column >= 1 and next_column <= 8:
result += 1
print(result)+ 필자분석
-
문자열의 두 번째 문자(숫자)를 정수로 변환하여 row 변수에 저장
-
ord(input_data[0]) - ord('a') + 1을 통해 첫 번째 문자(알파벳)에 대한 ASCII 코드 값을 가져와서 'a'의 ASCII 코드 값을 빼고 1을 더함으로써 열(column)을 나타내는 숫자로 변환하여 column 변수에 저장
문제4 - 문자열 재정렬
설명
입출력
key
data = input()
result = []
value = 0
#문자를 하나씩 확인한다.
for x in data:
#알파벳인 경우 결과 리스트에 삽입한다.
if x.isalpha():
result.append(x)
#숫자는 따로 더한다.
else:
value += int(x)
#알파벳을 오름차순으로 정렬한다.
result.sort()
#숫자가 하나라도 존재하는 경우 가장 뒤에 삽입한다.
if value != 0:
result.append(str(value))
#최종 결과 출력(리스트를 문자열로 변환하여 출력한다.)
print('',join(result))
