"이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편 14장의 써머리입니다."

14. 시뮬레이션(Simulation)

1) 시뮬레이션 문제 풀이 노하우

시뮬레이션 : 문제에 주어진 상황을 완벽하게 이해하고 이를 코드로 구현하는 과정

시뮬레이션 문제를 푸는 방법

다른 알고리즘처럼 일반화한 방법으로 설명하거나 풀 수 없음 → 주어진 상황에 따라 해결 방식 결정

- 하나의 문제를 최대한 여러 개로 분리
- 예외 처리가 필요하다면 독립 함수로 구현

행렬 연산

시뮬레이션 문제에 행렬 연산은 굉장히 많이 활용하는 기법

행렬 덧셈과 뺄셈, 그리고 곱셈

각 행렬에서 같은 위치에 있는 값끼리 더하거나 빼는 연산

이 연산을 하려면 사용하는 두 행렬의 크기가 같아야 함, 다르면 덧셈, 뺄셈 불가능

행렬 곱셈은 곱셈 순서가 중요하며 A → B 순서로 곱했다면 행렬 A의 행, 행렬 B의 열 크기가 일치해야 하고 곱셈의 결과는 행렬 A의 열, 행렬 B의 행 크기가 됨

전치 행렬

전치 행렬은 arr[i][j]를 arr[j][i]로 바꾸는 연산을 의미, 쉽게 말해 행과 열의 위치를 바꾸는 것

좌표 연산

시뮬레이션 문제에서는 조건에 따라 이동을 구현하는 경우가 많음 → 2차원 좌표를 사용하면 유용

좌표 배열로 표현하기

좌표를 배열로 표현하는 방법은 좌푯값에 해당하는 배열의 위치를 활용하는 것

 eg. (3, 4) → arr[4][3] = 1

좌표 이동 오프셋값으로 쉽게 표현하기

좌표를 활용하는 대부분의 문제는 현재 위치를 이동하는 문제가 많음 But, 좌표의 이동을 if문의 연속으로 표현하면 구현해야 하는 양이 너무 많아 좋지 않음
  → 좌표의 이동을 오프셋값을 이용해 표현하면 훨씬 깔끔하게 코드 구현 가능
  eg. 오프셋 배열이 있으면 8번의 if문 대신 for문 한번만 돌리면 되므로 편리함

for i in range(1, 9):
	arr[curr_y + dy[i]][curr_x + dx[i]] 

대칭, 회전 연산

01) 대칭과 회전은 조금만 침착하게 생각하면 쉽게 구현 가능

 eg. arr[[4, 3, 2], [5, 6, 5], [1, 2, 4]]

02) 길이가 N인 정사각형 배열에서 좌우 대칭을 일반화하면 A[i, j] = A[i, (N - 1) - j]와 같이 표현 가능

 eg. arr[0][0] → arr[0][2], arr[0][2] → arr[0][0]

03) 길이가 N인 정사각형 배열에서 90도, 반 시계 방향으로 회전하는 것을 일반화하면 A[i, j] = A[i, (N - 1) - i]와 같이 표현 가능

 eg. arr[0][0] → arr[2][0], arr[0][1] → arr[1][0]

2) 몸 풀기 문제

문제 62) 배열 회전하기

2차원 배열 arr을 시계 방향으로 90도 * n 번 회전하는 함수 작성

def solution(arr, n):
  k = len(arr)
  n = n % 4
  
  for _ in range(n):
    res = [[0 for _ in range(k)] for _ in range(k)]
    for i in range(k):
      for j in range(k):
        res[j][k - 1 - i] = arr[i][j]
        
    arr = res

  return arr

assert solution(
	[
		[1, 2, 3, 4],
		[5, 6, 7, 8],
		[9, 10, 11, 12],
		[13, 14, 15, 16]
	], 1
) == [
	[13, 9, 5, 1],
	[14, 10, 6, 2],
	[15, 11, 7, 3],
	[16, 12, 8, 4]
]

assert solution(
	[
		[1, 2, 3, 4],
		[5, 6, 7, 8],
		[9, 10, 11, 12],
		[13, 14, 15, 16]
	], 2
) == [
	[16, 15, 14, 13],
	[12, 11, 10, 9],
	[8, 7, 6, 5],
	[4, 3, 2, 1]
]

3) 합격을 위한 모의 테스트

문제 65) 이진 변환

0과 1로 이루어진 문자열 s가 주어지고 s가 "1"이 될 때까지 계속해서 이진 변환을 할 때 이진 변환의 횟수와 변환 과정에서 제거된 모든 0의 개수를 배열에 담아 반환하는 함수 완성

def solution(s):

	transform = 0
    zero = 0
    
	while s != "1":
    	transform += 1
        zero += s.count("0")
        s = bin(s.count("1"))[2:]
        
	return [transform, zero]