[Algorithm] 구현 - 시뮬레이션

* Python을 기준으로 합니다

---

구현 - 시뮬레이션 (Simulation)

- 개념

• 시뮬레이션 : 문제에서 주어진 과정을 하나씩 차례대로 직접 수행해 나가는 유형 
  • 시뮬레이션 문제 접근하기
    - 주어진 문제를 최대한으로 분리하기
    - 예외 처리는 독립적인 함수로 구분하기
  • 특히 시뮬레이션 문제는 2차원 배열을 활용하는 경우가 많으므로 행렬 연산을 응용해서 사용할 수도 있음
    - 문제가 길기 때문에 잘 분석해야함

- 구현

1. 행렬 연산

• 행렬 덧셈, 뺄셈, 곱셈

#행렬 덧셈
def matrix_sum(a,b):
    result = []
    for arow ,brow in zip(a, b):
        row = []
        for aele, bele in zip(arow, brow):
            row.append(aele+bele)
        result.append(row)
    
    return result

#행렬 뺄셈
def matrix_diff(a,b):
    result = []
    for arow ,brow in zip(a, b):
        row = []
        for aele, bele in zip(arow, brow):
            row.append(aele-bele)
        result.append(row)
    
    return result

#행렬 곱셈
def matrix_multiply(a,b):
    result = [[0]*len(a[0]) for _ in range(len(a))]

    for i in range(len(a)): 
        for j in range(len(b[0])): 
            for k in range(len(a[0])): 
                result[i][j] += a[i][k] * b[k][j]
    return result

• 행렬 회전, 전치

#행렬 회전 (시계방향)
def matrix_rotate(a):
    result = [[0]*len(a) for _ in range(len(a))]

    for i in range(len(a)):
        for j in range(len(a)):
            result[j][len(a)-i-1] = a[i][j]
    
    return result


#행렬 전치
def matrix_transpose(a):
    result = [[0]*len(a) for _ in range(len(a))]

    for i in range(len(a)):
        for j in range(len(a)):
            result[j][i] = a[i][j]
    
    return result

• 결과 확인

A = [
    [1,2,3],
    [4,5,6],
    [7,8,9]
]

B= [
    [9,8,7],
    [6,5,4],
    [3,2,1]
]

print(matrix_sum(A,B)) #[[10, 10, 10], [10, 10, 10], [10, 10, 10]]
print(matrix_diff(A,B)) #[[-8, -6, -4], [-2, 0, 2], [4, 6, 8]]
print(matrix_multiply(A,B)) #[[30, 24, 18], [84, 69, 54], [138, 114, 90]]
print(matrix_rotate(A)) #[[7, 4, 1], [8, 5, 2], [9, 6, 3]]
print(matrix_transpose(A)) #[[1, 4, 7], [2, 5, 8], [3, 6, 9]]

2. 예시 문제

• 프로그래머스 - 키패드 누르기 

키패드 누르기 문제

def dist(a,b):
    return abs(a[0]-b[0]) + abs(a[1]-b[1])

def solution(numbers, hand):
    phone = { 
    1: [0, 0], 2: [0, 1], 3: [0, 2],
    4: [1, 0], 5: [1, 1], 6: [1, 2],
    7: [2, 0], 8: [2, 1], 9: [2, 2],
    "*": [3, 0], 0: [3, 1], "#": [3, 2]
    } #키패드 좌표
    
    result = []
    left = phone["*"] #왼손
    right = phone["#"] #오른손
    
    for num in numbers: #각 숫자별로
        if num in [1, 4, 7]: #왼쪽 1,4,7 누르기
            left = phone[num] #왼손 위치 update
            result.append('L')
        elif num in [3, 6, 9]: #오른쪽 3,6,9 누르기
            right = phone[num] #오른손 위치 update
            result.append('R')
        else: #가운데 번호이면
            if dist(right, phone[num]) < dist(left, phone[num]): #거리계산시 오른손이 가까우면
                right = phone[num] #오른손으로 누르고 update
                result.append("R")
            elif dist(right, phone[num]) > dist(left, phone[num]): #왼손이 가까우면
                left = phone[num] #왼손으로 누르고 update
                result.append('L')
            else: #거리도 같으면
                if hand == "right": #오른손 잡이
                    right = phone[num] #오른손으로 누르고 update
                    result.append("R")
                else: #왼손 잡이
                    left = phone[num] #왼손으로 누르고 update
                    result.append('L')
                    
    return ''.join(result)

• 프로그래머스 - 롤케이크 자르기 

롤케이크 자르기 문제

import collections

def solution(topping):
    answer = 0
    
    counter = collections.Counter(topping)
    half_topping = set()
    
    for top in topping: #각 토핑에 대해
        half_topping.add(top) #절반만큼 토핑을 넣음
        counter[top] -= 1 #넣은 토핑 수 -1
        
        if counter[top] == 0: #토핑 개수가 0이면
            counter.pop(top) #pop
        
        if len(half_topping) == len(counter): #토핑 개수가 같아지면
            answer += 1 

    return answer

• 프로그래머스 - 스킬트리 

스킬트리 문제

import collections

def solution(skill, skill_trees):
    answer = 0
    
    for skill_tree in skill_trees: #각 스킬 트리에 대해
        prev = collections.deque(skill) #선행스킬 큐
        flag = True
        
        for s in skill_tree: 
            if s in skill and s != prev.popleft(): #스킬 트리가 선행스킬과 일치하지 않으면
                flag = False #불가능한 스킬 트리
                break 
        if flag: #가능한 스킬 트리이면
            answer += 1
            
    return answer