-1) 시뮬레이션 문제 풀이 노하우
시뮬레이션이란 문제에 주어진 상황을 완벽하게 이해하고 이를 코드로 구현하는 과정
다른 알고리즘은 성능에 중점을 둔 반면, 시뮬레이션은 구현에 중점을 맞춤
시뮬레이션 문제를 푸는 방법
시뮬레이션 문제는 문제 자체에 접근하는 방식을 공부해야함
아래 두 가지 염두에 두고 문제 풀기
-
하나의 문제를 최대한 여러 개로 분리하기
조급한 마음에 문제를 분리하지 않은 상태에서 구현하려고 하면 하나의 함수에 문제에서 제시한 모든 동작을 구현하게 되어 코드가 복잡해짐 -
예외 처리가 필요하다면 독립 함수로 구현하기
시뮬레이션 문제 특성상 구현할 부분이 많음
이때 기본으로 동작하는 부분과 예외 처리 부분의 코드가 섞이면 구현과 디버깅이 어려워짐
행렬 연산
시뮬레이션 문제에 행렬 연산은 굉장히 많이 활용하는 기법임 !
행렬 덧셈과 뺄셈, 그리고 곱셈
각 행렬에서 같은 위치에 있는 값끼리 더하거나 빼는 연산
-> 사용하는 두 행렬의 크기가 같아야 함
( 만약 두 행렬의 행 또는 열의 크기가 서로 다르면 행렬 덧셈과 뺄셈은 할 수 없음 )
** 행 : 각 리스트의 가로방향 -> 전체 리스트의 개수
열 : 각 행에서 원소의 개수
def matrix_add (matrix1, matrix2):
# 순서대로 행 개수와 첫번째 행의 열의 개수
if len(matrix1) != len(matrix2) or len(matrix1[0]) != len(matrix2[0]:
raise ValueError("Matrices must be of the same dimensions for addition.")
return [[matrix1[i][j] + matrix[i][j] for j in range (len(matrix1[0]))] for i in range(len(matrix))]
def matrix_sub (matrix1,matrix2):
if len(matrix1) != len(matrix2) or len(matrix1[0]) != len(matrix2[0]):
raise ValueError("Matrices must be of the same dimensions for subtraction.")
return [[matrix1[i][j] - matrix2[i][j] for j in range(len(matrix1[0]))] for i in range(len(matrix1))]
행렬 곱셈은 A의 각 행과 B의 각 열을 곱해서 만든다 !
- 곱셈 순서가 중요하며 A->B 순서로 곱했다면 행렬 A의 열, 행렬 B의 행 크기가 일치에야 하고
- 곱셈의 결과는 행렬 A의 행 x 행렬 B의 열 크기
def matrix_multi(matrix1,matrix2):
if len(matrix1[0]) != len(matrix2):
raise ValueError("Number of columns in the first matrix must equal the number of rows in the second matrix for multiplication.")
result = [[0 for _ in range(len(matrix2[0]))] for _ in range(len(matrix1))]
for i in range(len(matrix1)):
for j in range(len(matrix2[0])):
# 첫 번째 행렬의 열과 두 번째 행렬의 행을 연결하는 역할
for k in range(len(matrix2)):
result[i][j] += matrix1[i][k] * matrix2[k][j]
return result 전치행렬
arr[i][j]를 arr[j][i]로 바꾸는 연산, 즉 행과 열의 위치를 바꾸는 연산
def transpose (matrix):
return [[matrix[j][i] for j in range((len(matrix))] for i in range len(matrix[0]))]좌표 연산
시뮬레이션 문제에는 조건에 따라 이동을 구현하는 경우가 많음
이때 2차원 좌표를 사용하면 유용
좌표 배열로 표현하기
(3,4) 위치는 배열 arr[4][3]=1과 같이 저장됨
좌표 이동 오프셋값으로 쉽게 표현하기
좌표를 활용하는 대부분 문제는 현재 위치를 이동하는 문제가 많음
다만 좌표의 이동을 if문의 연속으로 표현하면 구현해야 하는 양이 너무 많음
# dx와 dy가 오프셋 값
for i in range(1,9):
arr[curr_y+dy[i]][curr_x+dx[i]]대칭, 회전 연산
좌우 대칭 : 행은 그대로 유지하면서 열의 순서가 반대로 뒤집힘
A[i,j]=A[i,(N-1)-j]
N은 열의 총개수, j는 현재 열 -> 0~N-1, 대칭 위치는 N-1-j
상하 대칭 : 열은 그대로 유지하면서 행의 순서가 반대로 뒤집힘
A[i,j]=A[(M-1)-i,j]
90도 반시계 방향 : 기존 행은 순서가 뒤집힌 새로운 열이 되고 기존 열은 행이 됨
A[i,j]=A[j,(N-1)-i]
90도 시계 방향 : 기존 행은 순서가 새로운 열이 되고 기존 열은 순서가 뒤집힌행이 됨
A[i,j]=[(M-1)-j,i]
