[알고리즘] 구현

구현

머릿속의 알고리즘 -> 소스코드

유형

완전탐색(브루트 포스) - 모든 경우의 수 계산

시뮬레이션 - 문제에서 제시한 알고리즘 차례대로 수행

메모리 사용량

데이터의 개수	메모리 사용량
1,000	약 4KB
1,000,000	약 4MB
10,000,000	약 40MB

 

수행시간

	1초당 연산량
Python 3	20,000,000
pypy 3	100,000,000

 

체크리스트

어떤 알고리즘을 채택했는가?

• 완전탐색(브루트 포스)
• 시뮬레이션
• 알고리즘을 어떻게 구현하였는가?

백준 문제

3190번- 뱀

• 시뮬레이션을 이용하여 구현
• 뱀의 머리가 갈 위치에 보드의 끝이거나 뱀의 몸통이 있는지 확인
• 사과에 도착할 경우 사과 집합에서 제거 

if (nx,ny) in apples: d_set= set() d_set.add((nx,ny)) apples = apples-d_set

전체 코드

n = int(input()) # 보드
A = int(input()) # 사과
apples = set()
for _ in range(A):
    apples.add(tuple(map(int,input().split())))
L = int(input())
moves = []
for _ in range(L):
    s,d = input().split()
    if d == 'L':
        d = -1
    else:
        d = 1
    s = int(s)
    moves.append([s,d])
D = [(0,1),(1,0),(0,-1),(-1,0)]

snakes = []
t = 0
cur_d = 0
x,y = 1,1
while True:
    snakes.append((x,y))
    if moves and t == moves[0][0]: # 방향전환 정보
        cur_d = (cur_d+ moves[0][1])%4
        moves.pop(0)
    nx,ny = x+D[cur_d][0], y + D[cur_d][1]
    if nx and ny and nx<=n and ny<=n and (nx,ny) not in snakes : # 보드끝에 닿지 않고 뱀이 끝에 닫지 않는 경우
        if (nx,ny) in apples:
            d_set= set()
            d_set.add((nx,ny))
            apples = apples-d_set
        else:
            snakes.pop(0)
    else:
        t+=1 # 다음 진행에 부딪히므로 시간+1
        break

    x,y = nx,ny
    t+=1
print(t)

14500번 - 테크로미노

• 완전탐색(브루트 포스)를 이용하여 구현
• 현재 위치에서 만들 수 있는 테크로미노의 값 계산

 

 

L 모양

    max_n = max(max_n,sum-G[i][j]-G[i][j+1],sum-G[i][j+1]-G[i][j+2],sum-G[i+1][j]-G[i+1][j+1],sum-G[i+1][j+1]-G[i+1][j+2])

 

 

N 모양

    max_n = max(max_n,sum-G[i][j]-G[i+1][j+2],sum-G[i][j+2]-G[i+1][j])

 

ㅜ 모양

    max_n = max(max_n,sum-G[i][j]-G[i][j+2],sum-G[i+1][j]-G[i+1][j+2])

 

전체 코드

def number_check(G,i,j,result):
    
    if i <= N-3 and j <= M-2:
        result = max(result,three_by_two(G,i,j))
    if i <= N-2 and j <= M-3 :
        result = max(result,two_by_three(G,i,j)) 
    if  j <= M-4 :
        result = max(result,one_by_four(G,i,j)) 
    if i <= N-4 :
        result = max(result,four_by_one(G,i,j)) 
    if i <= N-2 and j <= M-2 :
        result = max(result,two_by_two(G,i,j)) 
    return result

def two_by_three(G,i,j):
    max_n = 0
    sum = 0
    for x in range(i,i+2):
        for y in range(j,j+3):
            sum += G[x][y]
    max_n = max(max_n,sum-G[i][j]-G[i][j+1],sum-G[i][j+1]-G[i][j+2],sum-G[i+1][j]-G[i+1][j+1],sum-G[i+1][j+1]-G[i+1][j+2])
    max_n = max(max_n,sum-G[i][j]-G[i+1][j+2],sum-G[i][j+2]-G[i+1][j])
    max_n = max(max_n,sum-G[i][j]-G[i][j+2],sum-G[i+1][j]-G[i+1][j+2])
    return max_n
def three_by_two(G,i,j):
    max_n = 0
    sum = 0
    for x in range(i,i+3):
        for y in range(j,j+2):
            sum += G[x][y]
    max_n = max(max_n,sum-G[i][j]-G[i+1][j],sum-G[i+1][j]-G[i+2][j],sum-G[i][j+1]-G[i+1][j+1],sum-G[i+1][j+1]-G[i+2][j+1])
    max_n = max(max_n,sum-G[i][j]-G[i+2][j+1],sum-G[i+2][j]-G[i][j+1])
    max_n = max(max_n,sum-G[i][j]-G[i+2][j],sum-G[i][j+1]-G[i+2][j+1])
    return max_n
def two_by_two(G,i,j):
    sum = 0
    for x in range(i,i+2):
        for y in range(j,j+2):
            sum+=G[x][y]
    return sum
def one_by_four(G,i,j):
    sum = 0 
    for y in range(j,j+4):
        sum+= G[i][y]
    return sum
def four_by_one(G,i,j):
    sum = 0
    for x in range(i,i+4):
        sum+= G[x][j]
    return sum


N, M =  map(int,input().split())

G = []
for _ in range(N):
    inp = list(map(int,input().split()))
    G.append(inp)

max_n = 0
for i in range(N):
    for j in  range(M):
        max_n = number_check(G,i,j,max_n)

print(max_n)​

 

14503번 - 로봇청소기

• 완전탐색(브루트 포스)를 이용하여 구현
• 현재 위치에서 4방향 체크
• 만약 이동할 수 없을 시 현재 방향 유지한 채 뒤로 이동

    tmp = (ini_d+2)%4
    nx = x+ D[tmp][0]
    ny = y + D[tmp][1]

    if G[nx][ny]: 
        break
    else: 
        x = nx
        y = ny

 

## 전체코드 

N,M = map(int,input().split())
x,y,d = map(int,input().split())

G = []
for _ in range(N):
    G.append(list(map(int,input().split())))

visited = [[0 for _ in range(M)] for _ in range(N)]
D = {0:[-1,0],1:[0,1],2:[1,0],3:[0,-1]}
cnt = 0
fault = 0
while True:
    visited[x][y] = True
    ini_d = d
    for i in range(d-1,d-5,-1):
        cur_d = i%4
        nx = x + D[cur_d][0]
        ny = y + D[cur_d][1]
        if not visited[nx][ny] and not G[nx][ny] : # 위치,방향 할당
            x = nx
            y = ny
            d = cur_d 
            break
    else :
        # 4방향 모두 확인 후 이동하지 못하는 경우
        tmp = (ini_d+2)%4
        nx = x+ D[tmp][0]
        ny = y + D[tmp][1]

        if G[nx][ny]: # 1에 도착
            break
        else: # 한 칸 후진
            x = nx
            y = ny
ans  = 0
for raw in visited:
    ans +=sum(raw)
print(ans)

15686번 - 치킨 배달

• 완전탐색(브루트 포스)를 이용하여 구현
• 표준 라이브러리(itertools)을 이용하여 치킨집 조합 생성
• availables = list(combinations(chickens,M))
• 각 집에 대하여 선택된 M개의 임의의 치킨집의 최소 맨하탄 거리 계산
• if G[i][j] == 1: one_distance = 1_000_000_000 for c in available: cx,cy = c one_distance = min(one_distance,manhattan_distance(i,j,cx,cy)) # 가장 짧은 치킨집 avail_dist+= one_distance

전체 코드

from itertools import combinations


def manhattan_distance(x1,y1,x2,y2):
    dist = abs(x1-x2) + abs(y1-y2)
    return dist 

G = []
N,M = map(int,input().split())
for _ in range(N):
    G.append(list(map(int,input().split())))

chickens = []
for i in range(N):
    for j in range(N):
        if G[i][j] == 2:
            chickens.append((i,j)) # 치킨 리스트
availables = list(combinations(chickens,M))
answer = 1_000_000_000
for available in availables:
    avail_dist = 0
    for i in range(N):
        for j in range(N):
            if G[i][j] == 1:
                one_distance = 1_000_000_000
                for c in available:
                    cx,cy = c
                    one_distance = min(one_distance,manhattan_distance(i,j,cx,cy)) # 가장 짧은 치킨집
                avail_dist+= one_distance 
    answer = min(answer,avail_dist) # 선택된 치킨집의 총 최소 거리와 비교

print(answer)

2206 - 벽 부수고 이동하기

• bfs을 이용하여 구현
• list.pop(0), deque.popleft() 차이
  • list의 pop(0) 의 경우 O(n)의 시간복잡도
  • deque의 popleft()의 경우 O(1)의 시간복잡도
  • 해당 알고리즘에서는 deque을 이용하여 반복문
• 해당 이동장소가 벽이라면 벽을 부수고 변수 b= 0으로 할당 (앞으로 벽을 부술 수 없음)

  if b and G[nx][ny]==1 : # 벽이라면 벽을 부숨(b=0)
               Q.append((nx,ny,0,c+1))
               visited[nx][ny] = True

• 벽을 부수고 지나온 길에 대하여 벽을 부수지 않고 지나갈 수 있을 경우 b=1( 벽을 부술 수 있음)

  if b and G[nx][ny]==0 and visited[nx][ny]: # 벽을 뚫고 지나온 길을 뚫지 않고 갈 수 있다면
              G[nx][ny] =2
              Q.append((nx,ny,b,c+1))
              visited[nx][ny] = True
  

전체코드

from collections import deque
N, M = map(int,input().split())
G = []
for _ in range(N):
    row = list(map(int,input()))
    G.append(row)
visited = [[False for _ in range(M)] for _ in range(N)]
moves = [[-1,0],[1,0],[0,1],[0,-1]]

visited[0][0] = True
Q = deque()

cnt = 0
Q.append((0,0,1,1))
while Q:
    x,y,b,c = Q.popleft() #(x,y,can_break,count)
    if x == N-1 and y == M-1:
        print(c)
        break
    for move in moves:
        nx,ny = x+move[0],y+move[1]
        if nx>=0 and ny>=0 and nx<N and  ny<M:
            if not visited[nx][ny] and G[nx][ny]==0 : # 방문하지 않은 길이라면
                Q.append((nx,ny,b,c+1))
                visited[nx][ny] = True
            if b and G[nx][ny]==0 and visited[nx][ny]: # 벽을 뚫고 지나온 길을 뚫지 않고 갈 수 있다면
                G[nx][ny] =2
                Q.append((nx,ny,b,c+1))
                visited[nx][ny] = True
            if b and G[nx][ny]==1 : # 벽이라면 벽을 부숨(b=0)
                Q.append((nx,ny,0,c+1))
                visited[nx][ny] = True

if not visited[-1][-1]:
    print(-1)

 

 

 

 

출처

 

이것이 취업을 위한 코딩 테스트다 with 파이썬