배열 회전 알고리즘.
노가다 회전
def rotate(key, N):
def getNewValue(i, j, x, y):
key[j , N-i-1] = key[i ,j]
if (i == x and j == y):
return
getNewValue(N-j-1, i, x, y)
for i in range(0, int(N/2)):
for j in range(i, N-i-1):
print(i,j )
tmp = key[i,j]
getNewValue(N-1-j, i, i, j)
key[j, N-1-i] = tmpZIP을 사용한 깔끔한 회전
def zip_rotate(original):
rotated = np.array(list(zip(*original[::-1])))
return rotated
numpy를 이용해서 하는 방법도 있습니다. rot90을 이용하면 되는데요. 2차원 배열을 시계 방향으로 90도 회전시키기 위해서는, rot90의 2번째 인자에 3을 넣어주시면 되는데요. 이는, 반시계 방향으로 3번 회전시키겠다는 의미입니다.
먼저 4번째 줄에서, list를 numpy array로 바꿉니다. 다음에, np.rot90(o, 3)을 한 결과를 list로 바꾸는 것이 5번째 줄입니다. numpy의 ndarray에 tolist 메서드가 있음을 보시면 됩니다. 6번째 줄에 li를 출력하는데요. 이는 시계 방향으로 90도 회전한 결과를 출력하겠다는 의미입니다.
zip함수.
서로 다른 크기의 배열
numbersList = [1, 2, 3]
str_list = ['one', 'two']
numbers_tuple = ('ONE', 'TWO', 'THREE', 'FOUR')
# Notice, the size of numbersList and numbers_tuple is different
result = zip(numbersList, numbers_tuple)
# Converting to set
result_set = set(result)
print(result_set)
result = zip(numbersList, str_list, numbers_tuple)
# Converting to set
result_set = set(result)
print(result_set)위 코드의 결과값은 다음과 같다.{(1, 'ONE'), (2, 'TWO'), (3, 'THREE')}{(1, 'one', 'ONE'), (2, 'two', 'TWO')}
서로 다른 크기의 배열을 파라미터로 넣었을 때는 최소 크기에 맞춰서 묶음 후 반환한다.
주의!
zip이 반환해주는 튜플에는 순서가 없다. 때문에 같은 코드일지라도 실행할 때 마다 튜플의 순서가 뒤바뀌어 있다. 만약, 일정한 값을 원한다면, set 함수 대신 list를 사용하면 된다.result_set = list(result)
첫 번째 줄 출력은 set으로 변환하여서 순서가 계속 변한다.
반면, 두 번째 출력은 list로 변환하여 순서가 변하지 않는다.
zip()을 사용한 Unzip
coordinate = ['x', 'y', 'z']
value = [3, 4, 5]
result = zip(coordinate, value)
result_list = list(result)
print(result_list)
c, v = zip(*result_list)
print('c =', c)
print('v =', v)위 코드의 결과값은 다음과 같다.[('x', 3), ('y', 4), ('z', 5)]c = ('x', 'y', 'z')v = (3, 4, 5)
즉, 파라미터 앞에 ***** 를 붙이면 다시 여러 개의 iterable elements로 나누어지는 것이다. 만약 unzip을 계속한다면?
coordinate = ['x', 'y', 'z']
value = [3, 4, 5]
result = zip(coordinate, value)
result_list = list(result)
for i in range(0,4):
result_list= list(zip(*result_list))
print(result_list)위 코드의 결과는 아래와 같다.
[('x', 'y', 'z'), (3, 4, 5)]
[('x', 3), ('y', 4), ('z', 5)]
[('x', 'y', 'z'), (3, 4, 5)]
[('x', 3), ('y', 4), ('z', 5)][ : : -1] 과 unzip을 함께 사용한다면
rotated = np.array(list(zip(*original[::-1])))이 한줄이면 배열 회전이 된다. 설명을 위해 조금 나눠서 코드를 작성해보자.
original = [[1, 2, 3],[4, 5, 6],[7, 8, 9]]
for i in range(1, 5):
print("iterate : ", i)
tailToHead=original[::-1]
print(tailToHead)
original = list(zip(*tailToHead))
print("rotate")
print(original)결과
iterate : 1
[[1 2 3]
[4 5 6]
[7 8 9]]
[::-1]
[[7 8 9]
[4 5 6]
[1 2 3]]
rotate
[[7 4 1]
[8 5 2]
[9 6 3]]
iterate : 2
[[7 4 1]
[8 5 2]
[9 6 3]]
[::-1]
[[9 6 3]
[8 5 2]
[7 4 1]]
rotate
[[9 8 7]
[6 5 4]
[3 2 1]]
iterate : 3
[[9 8 7]
[6 5 4]
[3 2 1]]
[::-1]
[[3 2 1]
[6 5 4]
[9 8 7]]
rotate
[[3 6 9]
[2 5 8]
[1 4 7]]
iterate : 4
[[3 6 9]
[2 5 8]
[1 4 7]]
[::-1]
[[1 4 7]
[2 5 8]
[3 6 9]]
rotate
[[1 2 3]
[4 5 6]
[7 8 9]]알고리즘 문제를 풀면서 종종 2차원 배열을 회전하는 경우가 있습니다.
미리 정리해주면 좋을 것 같아서 회전 각도별로 코드 구현을 정리해봤습니다.
90도 회전 : 열은 행으로, 순서는 역순으로.
def rotate_90(m):
N = len(m)
ret = [[0] * N for _ in range(N)]
for r in range(N):
for c in range(N):
ret[c][N-1-r] = m[r][c]
return ret180도 회전 : 행과 열 모두 역순으로(원래 위치의 반대로 들어감)
def rotate_180(m):
N = len(m)
ret = [[0] * N for _ in range(N)]
for r in range(N):
for c in range(N):
ret[N-1-r][N-1-c] = m[r][c]
return ret270도 회전(-90도 회전.)
def rotate_270(m):
N = len(m)
ret = [[0] * N for _ in range(N)]
for r in range(N):
for c in range(N):
ret[N-1-c][r] = m[r][c]
return ret총 정리
def rotate(m, d):
"""
:input:
m: 회전하고자 하는 2차원 배열. 입력이 정방형 행렬이라고 가정한다.
d: 90도씩의 회전 단위. -1: -90도, 1: 90도, 2: 180도, ...
"""
N = len(m)
ret = [[0] * N for _ in range(N)]
if d % 4 == 1:
for r in range(N):
for c in range(N):
ret[c][N-1-r] = m[r][c]
elif d % 4 == 2:
for r in range(N):
for c in range(N):
ret[N-1-c][N-1-r] = m[r][c]
elif d % 4 == 3:
for r in range(N):
for c in range(N):
ret[N-1-c][r] = m[r][c]
else:
for r in range(N):
for c in range(N):
ret[r][c] = m[r][c]
return ret추가 zip코드(함수화)
def rotated(array_2d):
list_of_tuples = zip(*array_2d[::-1])
return [list(elem) for elem in list_of_tuples]
# return map(list, list_of_tuples)테스트
arr = [[1,2,3],[4,5,6],[7,8,9]]
nm_arr = [[1,2],[3,4],[5,6]]
print(rotated(arr))
print(rotated(nm_arr))위의 예시를 실행시키면 결과는 아래와 같다. 꼭 N^N 배열이 아니더라도 가능하다.
유사 문제
행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시킨다. 각 회전은 (x1, y1, x2, y2)인 정수 4개로 표현한다.
- x1 행 y1 열부터 x2 행 y2 열까지의 영역에 해당하는 직사각형에서 테두리에 있는 숫자들을 한 칸씩 시계방향으로 회전합니다.
(2, 2, 5, 4) 회전
행렬의 세로 길이(행 개수) rows, 가로 길이(열 개수) columns, 그리고 회전들의 목록 queries가 주어질 때, 각 회전들을 배열에 적용한 뒤, 그 회전에 의해 위치가 바뀐 숫자들 중 가장 작은 숫자들을 순서대로 배열에 담아 return 하도록 solution 함수를 완성하라.
제한사항
- rows는 2 이상 100 이하
- columns는 2 이상 100 이하
- 처음에 행렬에는 가로 방향으로 숫자가 1부터 하나씩 증가하면서 적혀있습니다.
- 즉, 아무 회전도 하지 않았을 때, i 행 j 열에 있는 숫자는 ((i-1) x columns + j)입니다.
- queries의 행의 개수(회전의 개수)는 1 이상 10,000 이하
- queries의 각 행은 4개의 정수 [x1, y1, x2, y2]
- x1 행 y1 열부터 x2 행 y2 열까지 영역의 테두리를 시계방향으로 회전
- 1 ≤ x1 < x2 ≤ rows, 1 ≤ y1 < y2 ≤ columns
- 모든 회전은 순서대로 이루어집니다.
- 예를 들어, 두 번째 회전에 대한 답은 첫 번째 회전을 실행한 다음, 그 상태에서 두 번째 회전을 실행했을 때 이동한 숫자 중 최솟값
입출력 예시
| row | columns | queries | result |
|---|---|---|---|
| 6 | 6 | [[2,2,5,4],[3,3,6,6],[5,1,6,3]] | [8, 10, 25] |
| 3 | 3 | [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] | [1, 1, 5, 3] |
| 100 | 97 | [[1,1,100,97]] | [1] |
전체 코드
def solution(rows, columns, queries):
answer = []
array = [[0 for col in range(columns)] for row in range(rows)]
t = 1
for row in range(rows):
for col in range(columns):
array[row][col] = t
t += 1
for x1,y1,x2,y2 in queries:
tmp = array[x1-1][y1-1]
mini = tmp
for k in range(x1-1,x2-1):
test = array[k+1][y1-1]
array[k][y1-1] = test
mini = min(mini, test)
for k in range(y1-1,y2-1):
test = array[x2-1][k+1]
array[x2-1][k] = test
mini = min(mini, test)
for k in range(x2-1,x1-1,-1):
test = array[k-1][y2-1]
array[k][y2-1] = test
mini = min(mini, test)
for k in range(y2-1,y1-1,-1):
test = array[x1-1][k-1]
array[x1-1][k] = test
mini = min(mini, test)
array[x1-1][y1] = tmp
answer.append(mini)
return answer파이썬 배열 뒤집기
axis = 0 기준으로 2차원 numpy 배열 뒤집기 (how to reverse numpy 2D array by axis=0)
| (1) x[::-1] | (2) np.flip(x, axis=0) |
|---|---|
| # returns a view in reversed order by axis=0 arr_2d[::-1] [Out]:array([[5, 6, 7, 8, 9], [0, 1, 2, 3, 4]]) |
# reverse 2D array by axis 0 np.flip(arr_2d, axis=0) [Out]:``array([[5, 6, 7, 8, 9], [0, 1, 2, 3, 4]]) |
axis = 1 기준으로 2차원 numpy 배열 뒤집기 (how to reverse numpy 2D array by axis=1)
| (1) x[:, ::-1] | (2) np.flip(x, axis=1) |
|---|---|
| # returns a view of 2D array by axis=1 arr_2d[:, ::-1] [Out]:``array([[4, 3, 2, 1, 0], [9, 8, 7, 6, 5]]) |
# reverse 2D array by axis 1 np.flip(arr_2d, axis=1) [Out]:``array([[4, 3, 2, 1, 0], [9, 8, 7, 6, 5]]) |
axis =0 & axis = 1 기준으로 2차원 numpy 배열 뒤집기 (revserse numpy 2D array by axis=0 &1)
| (1) x[:, ::-1][::-1] | (2) np.flip(x) |
|---|---|
| # returns a view arr_2d[:, ::-1][::-1] [Out]:array([[9, 8, 7, 6, 5], [4, 3, 2, 1, 0]]) |
# 2D array np.flip(arr_2d) [Out]:``array([[9, 8, 7, 6, 5], [4, 3, 2, 1, 0]]) |
'practivceAlgorithm > 자료구조&알고리즘' 카테고리의 다른 글
| [알고리즘] 슬라이딩 윈도우 (0) | 2021.08.11 |
|---|---|
| [알고리즘] LCA(최소 공통 조상)과 sparse table (0) | 2021.08.09 |
| [자료구조] Segment의 memory를 줄인 Penwick Tree (0) | 2021.08.07 |
| [자료구조] Segment Tree : 구간 연산 구간 변경 (0) | 2021.08.03 |
| [알고리즘] 비트마스크???!!! (0) | 2021.07.29 |