Untitled

Fold the Video

14강 구현 유형 개요

구현 유형의

대회나

흔히 구현유형의 문제는

구현 유형에 이에 해당합니다

파이썬이

문제들이 1번 혹은 2번에 많이 출제가 되곤 합니다

확 높아지는 문제도 존재합니다

모든 순열과

것을 미리 공부를 해놓으면 당연히 다양한 구현문제가 나왔을때 당황하지 않고 대응할수 있겠죠

파트를

7(Implementation)
일반적으로 알고리즘 문제에서의 2차원 공간은 행렬(Matrix)의 의미로 사용됩니다.
열(Column)
(0, 0) | (0, 1) | (0, 2)
(0, 3) (0, 4)
for i in range(5):
for j in range(5):
print('(', i, ',', j, ')', end=' ')
print()
(1, 0) | (1, 1) | (1, 2) | (1, 3) | (1, 4)
행
(Row)
(2, 0) | (2, 1) | (2, 2)
(2, 3)
(2, 4)
(3, 0) (3, 1)| (3, 2) | (3, 3) | (3, 4)
(4, 0) (4, 1) | (4, 2)
(4, 3) | (4, 4)
구현: 시뮬레이션과 완전 탐색

행 열

맵의 한 좌표의 존재하는

왼쪽

원소고요 이 세로축을 행이라고 하고 이 가로축을 열이라고 합니다.

열 위치가

완전탐색 혹은 시물레이션 예상문제를 접할때

첫번째 원소군아라는 점을 기억해 두시면 좋습니다.

문제 같은 경우는 사물 등이

7(Implementation)
시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용됩니다.
# 동, 북, 서, 남
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]
(0, 0) | (0, 1) | (0, 2) | (0, 3) | (0, 4)
(1, 0) | (1, 1) | (1, 2) | (1, 3) | (1, 4)
# 현재 위치
х, у %3D 2, 2
(2, 0) | (2, 1)-((2, 2) 2, 3)
(2, 4)
for i in range(4):
# 다음 위치
nx = x + dx[i]
ny = y + dy[i]
print(nx, ny)
(3, 0) (3, 1)| (3, 2) | (3, 3) | (3, 4)
(4, 0) | (4, 1) | (4, 2) | (4, 3) | (4, 4)
|문제 상황이 전개되는 경우가 많은데요
구현: 시물레이션과 완전 탐색 이제 그러한 문제를 해결하기 위해서 방향 벡터 가 자주 사용됩니다

행열과 동일하게 본다고 했을때

자 여기에서

dx 는 이 새로축을 의미하는 거고

이 와이는 이 가로축 즉 열을 의미한다고 보면 됩니다

행렬 기준으로 가만이 있고

그래서 이런식으로 특정위치가 x랑 y좌표로 정해져있다고 했을때

이 dx를 더해줌으로써

수 있습니다

로직이 사용됩니다.

동북서남 순서대로

7(Implementation)
시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용됩니다.
#동, 북, 서, 남
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]
(0, 0) | (0, 1) | (0, 2) | (0, 3)| (0, 4)
(1, 0) (1, 1) | (1, 2) | (1, 3) | (1, 4)
# 현재 위치
х, у %3D 2, 2
(2, 0) | (2, 1) (2, 2) 2, 3) (2, 4)
for i in range(4):
# 다음 위치
nx = x + dx[i]
ny = y + dy[i]
print(nx, ny)
(3, 0) (3, 1) | (3, 2) | (3, 3) | (3, 4)
(4, 0) | (4, 1) | (4, 2) | (4, 3)
(4, 4)
|자 그래서 실제로 특히 코딩 테스트 환경에서는 2차원 공간에서 의 방향
|벡터 가 많이 사용되고
구현: 시뮬레이션과 완전 탐색

dx와 dy는 차례대로 다이렉션 x 다이렉션 y 배열 혹은

상하좌우 문제를 보고 마치도록 하겠습니다

<문제> 상하좌우: 문제 설명
여행가 A는 N x N 크기의 정사각형 공간 위에 서 있습니다. 이 공간은 1×1 크기의 정사각형으로 나누
어져 있습니다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당합니다. 여행가 A
는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)입니다. 우리 앞에는 여행가 A가 이동
할 계획이 적힌 계획서가 놓여 있습니다.
계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀 있습니
다. 각 문자의 의미는 다음과 같습니다.
L: 왼쪽으로 한 칸 이동
R: 오른쪽으로 한 칸 이동
U: 위로 한 칸 이동
D: 아래로 한 칸 이동
구현: 시뮬레이션과 완전 탐색

이 상하좌우 문제를 확인해 보겠습니다

상하좌우 문제는 이렇게 n X n

1 x 1 크기의

왼쪽 위 자표는 1,1 이라고 합니다 우리가 2차원 리스트를

이러한 행렬

1,1 부터 출밯

인것 처럼 처리하도록 만들어서 코드를 작성할 수도 있습니다.

1컴마 1이거고 n컴마 n이라고 합니다

1컴마 1

이 여행가를 이동시키면 되는것인데요

이렇게 계획서에는 L R U D중 하나의 문자가 반복적으로 적혀있다고 해요 그래서 이렇게 차례대로 레프트 라이트 업 다운

여행가 a를 전체 nXn크기의

rrrudd 그래서 이렇게 오른쪽으로 3칸 이동합니다 그다음에 이제 u를 만났으니까

이렇게 위쪽으로 이동을 해야 하는데

이 3,4 에 위치에 도달을 하게 됩니다 그래서 정답으로 3,4를 출력하면 정답 판정을 받을 수 있겠죠


구현: 시뮬레이션과 완전 탐색

128mb 라고 합니다 이때 이렇게 n은 최대 100이기 때문에 100x100짜리

2차원 리스트를 만들면 총 만개 만큼의 위치가 존재한다고 할수 있겠네요

일단 내코드 (다시 해보자)

n = int(input())

d = list(input().split())

print(d)

x, y = 1, 0

#동, 북, 서, 남

dx = [0, -1, 0, 1]

dy = [1, 0, -1, 0]

for i in range(n):

for j in range(n):

print('(', i+1, ',', j, ')', end=' ')

print("")

일련에 시뮬레이션 유형의 문제

구현이 중요한 대표적인 문제 유형으로 분류할수 있습니다 다만 실제로

문제 유형을 서로 다르게 일컬을 수도 있습니다.

시물레이션 유형 구현 유형 (마지막줄 읽어줌)

구현 유형으로

x랑 와이변수가 사용되고요

lrud 이동하는 그 각각의 반향을 명시해주기위해서 이렇게 dx, dy를 사용하는 걸 확인할수 있구요

이 move_types중에서 move_types 맞는 다음 이dx, dy 값을

이 다음 위치값을 설정한 것을 확인할수 있습니다

파이썬 이 nx, ny가 사용되기전에

이 if문에서 이를 바로 참조할수 있습니다.

바로 이렇게

모든 이동계획을 결과를 출력하면

nx랑 ny를 초기화 해준다음에

nx랑 ny의 값을 실제

ny의 값이 공간을

c++, java 를 이용할때는 하나 유의할점이 있는데요

정수가 들어온뒤에

한줄의

c++ 코드까지 확인해 보았습니다

자바코드는 발표 자료에 넣기에 너무 길어서 깃허브에 올려놓았음

c++ 코드와

문법만 자바코드로 작성되어 있다고 보시면 되겠습니다

Last Updated:

Summarize & share videos seamlessly