[알고리즘] 구현

[인트로]

우리는 모든 경우의 수를 다 계산하는 bruteforce방법과 문제에서 제시한 알고리즘을 한 단계씩 수행하는 simulation을 공부할 것이다.

 

원래 알고리즘 문제를 풀때는 시간제한 and 데이터의 개수를 확인해서 문제를 어떤 시간복잡도의 알고리즘을 작성하여 풀 수 있을 지 예상가능해야한다.

 

예를 들어서, 100만개를 nlogn으로 풀면 2천만이다.

 

 

[구현문제 특징]

문제가 길어 주어진 조건이 많다. 쫄 필요없이 그대로 수행

 

 

[구현문제 예제]

상하좌우

- 일련의 명령에 따라서 개체를 차례대로 이동시킨다는 점이 시뮬레이션 유형

- 연산횟수는 이동횟수 N

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_types = ['l','r','u','d']

for plan in plans:
#나는 전부다 if문으로 하나하나 확인하려고 했는데 이렇게 하면 더 빠르다.
    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)

 

[구현문제 예제]

시각

- 00 00 00 ~ 23 59 59, 24 * 60 * 60가지로 아무리 많아도 86400개다. 따라서 문자열 연산으로 3이 시각에 포함되어있는지 확인해도 시간복잡도가 낮다.

-완전 탐색: 이 문제처럼 하나하나 확인할 숫자가 100만 개 이하인 경우에만 사용한다. 예를 들어서 조합같이 지수형태에서는 무시한다.

#시각

h = int(input())

count = 0

#i는 시간으로 0 ~ h 표현한다.
#j,k는 0 ~ 60 으로 초부터 차례대로 올라간다 진짜 천재같다 이런 표현은 와... 우
for i in range(h + 1):
    for j in range(60):
        for k in range(60):
            if '3' in str(i) + str(j) + str(k):
                count += 1
                
            
print(count)

 

[왕실의 나이트]

-위의 상하좌우 문제와 유사하다.

-8가지라서 완전탐색으로 가능하다.

-이동할 때 dx,dy 혹은 steps로 두 가지 형태가 있다는 것을 기억하자.

-ord를 기억하자.

#왕실의 나이트

input_data = input()
#열과 행으로 들어오기 때문에 열, 행 변수를 만들어서 넣어준다.
#이때, column으로 들어오는 문자를 어떻게 숫자로 바꿔주는 지를 잘보자.

row = int(input_data[1])
#key point! -> ord는 아스키코드인 97로 a를 바꿔준다.
column = int(ord(input_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:
    ncolumn = column + step[0]
    nrow = row + step[1]
    if ncolumn < 1 or nrow < 1 or ncolumn > 8 or nrow > 8:
        continue
    else:
        count+=1
        
print(count)

[게임개발]

-어려웠다.

-이런 구현문제는 최대한 문제에 주어진 순서에 맞게 구현하는 것이 핵심이다.

#게임개발

n, m = map(int, input().split())
x, y, d = map(int, input().split ())

matrix = []
for _ in range(n):
    matrix.append(list(map(int,input().split())))
    
matrix[x][y] = -1

direction = [0,1,2,3] #북 동 남 서
steps = [[0,-1],[-1,0],[0,1],[1,0]] #서 북 동 남
steps_back = [[1,0],[0,-1],[-1,0],[0,1]]
result = 0
count = 0

while True:
    #현재 바라보고 있는 방향의 왼쪽 방향을 nx,ny로 나타냈다.
    nx = x + steps[d][0]
    ny = y + steps[d][1]
    print(str("nx,ny"),nx, ny)
    #막혀있거나 가본적이 없다면 이동한다.
    if matrix[nx][ny] == -1 or matrix[nx][ny] == 1:
        count += 1
        d = (d + 3) % 4
        #만약에 4방향을 다 돌았다면, 뒤로 간다.
        if count == 4:
            nx = x + steps_back[d][0]
            ny = y + steps_back[d][1]
            #근데, 뒤 방향으로 못간다면 탈출한다.
            if matrix[nx][ny] == 1 or matrix[nx][ny] == -1:
                break
            x = nx
            y = ny
        continue
    #그 방향으로 이동한다.
    result +=1
    x = nx
    y = ny
    d = (d + 3) % 4
    count = 0
    matrix[x][y] = -1
    print(x,y)
    
print(result)

4 4
1 1 0
1 1 1 1
1 0 0 1
1 1 0 1
1 1 1 1
nx,ny 1 0
nx,ny 2 1
nx,ny 1 2
1 2
nx,ny 0 2
nx,ny 1 1
nx,ny 2 2
2 2
nx,ny 2 3
nx,ny 1 2
nx,ny 2 1
nx,ny 3 2
2

개선된 답안

- d = [[0] * m for _ in range(n)] 방문 배열은 이렇게 만들 수 있다.

- matrix[x][y] = -1 방문표시를 꼭 하자

- 회전 방법은 나처럼 d = (d + 3) % 4로 할 수 도 있고 1씩 빼는 방법도 있다.

- turn time을 통해서 회전 횟수를 기록하여 네 방향을 이미 다 시도했다는 것을 표현할 수 있다.

n, m = map(int, input().split())

d = [[0] * m for _ in range(n)]

d[x][y] = 1

array = []
for i in range(n):
    array.append(list(map(int,input().split())))
    
dx = [-1,0,1,0]
dy = [0,1,0,-1] #북 동 남 서

def turn_left():
    global direction
    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
        trun_time = 0
        continue
    else:
        turn_time +=1
    
    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)