[알고리즘] python - 구현

'코딩 테스트에서 구현(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별도의 리스트를 만들어 방향을 설정하는 것이 효과적이다.

이처럼 작성하면, 반복문을 이용하여 모든 방향을 차례대로 확인할 수 있음!!!