'코딩 테스트에서 구현(Implementation)이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다'
완전 탐색과 시뮬레이션 유형을 모두 '구현'유형으로 묶어서 보자면, 완전 탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법이고, 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형을 의미한다.
예제 4-1. 상하좌우
▶ 입력 조건
- 첫째 줄에 공간의 크기를 나타내는 N이 주어진다. (1≤N≤100)
- 둘째 줄에 여행가 A가 이동할 계획사 내용이 주어진다. (1≤이동 횟수≤100)
▶ 출력 조건
- 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X,Y)를 공백으로 구분하여 출력한다.
n = int(input())
routes = input().split()
x,y = 1,1
for route in routes:
if(route=='R') :
if(y==n) : continue
else : y+=1
elif(route=='L') :
if(y==1) : continue
else: y-=1
elif (route=='U') :
if(x==1) : continue
else : x -=1
elif (route=='D') :
if(x==n) : continue
else : x+=1
print(x,y)
예제 4-2. 시각
▶ 입력 조건
- 첫째 줄에 정수 N이 입력된다. (0≤N≤23)
▶ 출력 조건
- 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다.
n = int(input())
count = 0
for i in range(n+1):
for j in range(60) :
for k in range(60) :
if '3' in str(i)+str(j)+str(k):
count+=1
print(count)
2. 왕실의 나이트
▶ 입력 조건
- 첫째 줄에 8×8 좌표 평면상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두 문자로 구성된 문자열이 입력된다. 입력 문자는
a1처럼 열과 행으로 이뤄진다.
▶ 출력 조건
- 첫째 줄에 나이트가 이동할 수 있는 경우의 수를 출력하시오.
data = input()
row = int(data[1])
col = int(ord(data[0]))-int(ord('a'))+1
steps = [(-2,-1),(2,1),(-2,1),(2,-1),(-1,-2),(1,-2),(1,2),(-1,2)]
count = 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 :
count += 1
print(count)
3. 게임 개발
▶ 입력 조건
- 첫째 줄에 맵의 세로 크기 N과 가로 크기 M을 공백으로 구분하여 입력한다. (3≤N, M≤50)
- 둘째 줄에 게임 캐릭터가 있는 칸의 좌표 (A, B)와 바라보는 방향 d가 각각 서로 공백으로 구분하여 주어진다. 방향 d의 값으로는
다음과 같이 4가지가 존재한다.
- 0 : 북쪽
- 1 : 동쪽
- 2 : 남쪽
- 3 : 서쪽
- 셋째 줄부터 맵이 육지인지 바다인지에 대한 정보가 주어진다. N개의 줄에 맵의 상태가 북쪽부터 남쪽 순서대로, 각 줄의 데이터는 서쪽부터 동쪽 순서대로 주어진다. 맵의 외곽은 항상 바다로 되어 있다.
- 0 : 육지
- 1 : 바다
- 처음에 게임 태릭터가 위치한 칸의 상태는 항상 육지이다.
▶ 출력 조건
- 첫째 줄에 이동을 마친 후 캐릭터가 방문한 칸의 수를 출력한다.
n, m = map(int, input().split())
d = [[0]*m for _ in range(n)] #가본 곳 체크하기 위한 배열
x,y,direction = map(int, input().split())
d[x][y] = 1
array = []
for i in range(n):
array.append(list(int, input().split()))
dx = [-1, 0, 1, 0] #북,동,남,서
dy = [0, 1, -1, 0]
def turn_left():
direction -=1
if direction == -1 :
direction = 3
count = 1
turn_time = 0
while True:
turn_left()
nx = x+dx[direction]
ny = y+dy[direction]
if d[nx][ny]==0 and array[nx][ny]==0:
d[nx][ny] =1
x = nx
y = ny
count += 1
turn_time = 0
continue
else :
turn_time = 0
if turn_time == 4:
nx = x - dx[direction]
ny = y - dy[direction]
if array[nx][ny] == 0:
x = nx
y = ny
else :
break
turn_time = 0
print(count)
일반적으로 '방향'을 설정해서 이동하는 문제 유형에서는 dx, dy별도의 리스트를 만들어 방향을 설정하는 것이 효과적이다.
이처럼 작성하면, 반복문을 이용하여 모든 방향을 차례대로 확인할 수 있음!!!
'알고리즘 > 스터디' 카테고리의 다른 글
[알고리즘] 다이나믹 프로그래밍 (0) | 2023.07.11 |
---|---|
[알고리즘] 이진 탐색 (0) | 2023.07.01 |
[알고리즘] 정렬 (0) | 2023.06.20 |
[알고리즘] python - DFS/BFS (0) | 2023.06.10 |
[알고리즘] 탐욕적(Greedy) 알고리즘 (0) | 2023.05.31 |