Algorithm
[코딩테스트] 코딩테스트 빈출 유형 정리
potato_pizza
2024. 4. 7. 20:38
728x90
1. 회전
1-1. zip()
정사각형, 직사각형 모두 동일하게 적용
arr = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]
# 시계 90 (= 반시계 270)
arr_90 = list(map(list, zip(*arr[::-1])))
print(arr_90)
# 시계 180
arr_180 = [a[::-1] for a in arr[::-1]]
# 시계 270 (= 반시계 90)
arr_270 = [x[::-1] for x in list(map(list, zip(*arr[::-1])))[::-1]]1-2. 인덱스 규칙 찾아서 회전
정사각형
arr = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
n = 3
# 시계 방향 90 (= 반시계 방향 270)
rotate_90 = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
rotate_90[j][n - i - 1] = arr[i][j]
# 시계 180 & 반시계 180
rotate_180 = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
rotate_180[n - i - 1][n - j - 1] = arr[i][j]
# 시계 270 & 반시계 90
rotate_270 = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
rotate_270[n - 1 - j][i] = arr[i][j]직사각형
a = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]
def rotate_90(a):
m = len(a)
n = len(a[0])
result = [[0]* m for _ in range(n)]
for i in range(m):
for j in range(n):
result[j][m-i-1] = a[i][j]
return result
def rotate_180(a):
n = len(a)
m = len(a[0])
result = [[0]* m for _ in range(n)]
for i in range(n):
for j in range(m):
result[n-i-1][m-j-1] = a[i][j]
return result
def rotate_270(a):
n = len(a)
m = len(a[0])
result = [[0]* n for _ in range(m)]
for i in range(n):
for j in range(m):
result[m-1-j][i] = a[i][j]
return result2. 부분 회전
# 7X7 배열
arr = [[7 * j + i for i in range(1, 8)] for j in range(7)]
new_arr = [[0] * 7 for _ in range(7)]
sy, sx = 2, 2
length = 3
# 배열의 특정 부분(정사각형)을 회전
def rotate_90(sy, sx, length):
global arr, new_arr
# 정사각형을 시계방향으로 90도 회전
for y in range(sy, sy + length):
for x in range(sx, sx + length):
# 1단계 : (0,0)으로 옮겨주는 변환
oy, ox = y - sy, x - sx
# 2단계 : 90도 회전했을때의 좌표
ry, rx = ox, length - oy - 1
# 3단계 : 다시 (sy,sx)를 더하기
new_arr[sy + ry][sx + rx] = arr[y][x]
# new_arr 값을 현재 board에 옮김
for y in range(sy, sy + length):
for x in range(sx, sx + length):
arr[y][x] = new_arr[y][x]
print(arr[y][x])
rotate_90(sy, sx, length)
for i in range(len(arr)):
print(arr[i])3. 순열, 중복 순열, 조합, 중복 조합
3.1 순열(Permutations)
arr = [1, 2, 3, 4]
visited = [0] * len(arr)
# 뽑을 개수, 뽑힌 값을 담는 배열
def permutations(n, new_arr):
global arr
# 순서 상관 O, 중복 X
if len(new_arr) == n:
print(new_arr)
return
for i in range(len(arr)):
if not visited[i]:
visited[i] = 1
permutations(n, new_arr + [arr[i]])
visited[i] = 0
permutations(2, [])3.2 중복 순열(Product)
arr = [1, 2, 3, 4]
def product(n, new_arr):
global arr
# 순서 상관 O, 중복 O
if len(new_arr) == n:
print(new_arr)
return
for i in range(len(arr)):
product(n, new_arr + [arr[i]])
product(2, [])3.3 조합(Combinations)
arr = [1, 2, 3, 4]
def combinations(n, new_arr, c):
# 순서 상관 X, 중복 X
if len(new_arr) == n:
print(new_arr)
return
for i in range(c, len(arr)):
combinations(n, new_arr + [arr[i]], i + 1)
combinations(2, [], 0)3.4 중복 조합(Combinations with replacement)
arr = [1, 2, 3, 4]
def combinations_with_replacement(n, new_arr, c):
# 순서 상관 X, 중복 O
if len(new_arr) == n:
print(new_arr)
return
for i in range(c, len(arr)):
combinations(n, new_arr + [arr[i]], i)
combinations_with_replacement(2, [], 0)4. 중력
4.1 바닥까지 하강
arr = [[0, 1, 0], [1, 0, 1], [0, 1, 0], [0, 0, 1], [0, 1, 0]]
print("Before")
for i in range(len(arr)):
print(arr[i])
def gravity():
n = len(arr)
m = len(arr[0])
for i in range(n - 1):
for j in range(m):
p = i
# 현재칸이 아래로 내려갈 수 있다면 그 윗줄도 한 칸 씩 연쇄적으로 내려와야함
while 0 <= p and arr[p][j] == 1 and arr[p + 1][j] == 0:
arr[p][j], arr[p + 1][j] = arr[p + 1][j], arr[p][j]
p -= 1
gravity()
print("After")
for i in range(len(arr)):
print(arr[i])5. 나선형(달팽이) 배열
5.1 안에서 밖으로
- 좌 $\rightarrow$ 하 $\rightarrow$ 우 $\rightarrow$ 상
arr = [[0] * 5 for _ in range(5)]
def tornado():
global arr
d = [(0, -1), (1, 0), (0, 1), (-1, 0)]
y = len(arr) // 2
x = len(arr) // 2
num = 0 # 칸에 채워넣을 값
dist = 1
d_idx = 0 # 서 남 동 북 순서
move_count = 0 # 2가 되면 dist 길이가 1 늘어나고 move_count는 다시 0으로 초기화
while True:
for _ in range(dist):
dy, dx = d[d_idx]
Y = dy + y
X = dx + x
if (Y, X) == (0, -1): # 0행 -1열이 토네이도가 모두 끝나고 나서의 위치임
return
num += 1
arr[Y][X] = num
y = Y
x = X
move_count += 1
d_idx = (d_idx + 1) % 4
if move_count == 2:
dist += 1
move_count = 0
tornado()
for i in range(5):
print(arr[i])
5.2 밖에서 안으로
def solution(n):
if n == 1:
return [[1]]
answer = [[0 for j in range(n)] for i in range(n)]
x = 0
y = 0
d_idx=0
for i in range(n * n):
answer[x][y] = i + 1
if d_idx == 0:
y += 1
if y == n - 1 or answer[x][y + 1] != 0:
d_idx = 1
elif d_idx == 1:
x += 1
if x == n - 1 or answer[x + 1][y] != 0:
d_idx = 2
elif d_idx == 2:
y -= 1
if y == 0 or answer[x][y - 1] != 0:
d_idx = 3
elif d_idx == 3:
x -= 1
if x == n - 1 or answer[x - 1][y] != 0:
d_idx = 0
return answer
arr = solution(5)
for i in range(len(arr)):
print(arr[i])
6. 이동 중 벽에 부딪혀서 방향 전환
def get_next_loc(i, j, speed, dir):
if dir == UP or dir == DOWN: # i
cycle = R * 2 - 2
if dir == UP:
speed += 2 * (R - 1) - i
else:
speed += i
speed %= cycle
if speed >= R:
return (2 * R - 2 - speed, j, UP)
return (speed, j, DOWN)
else: # j
cycle = C * 2 - 2
if dir == LEFT:
speed += 2 * (C - 1) - j
else:
speed += j
speed %= cycle
if speed >= C:
return (i, 2 * C - 2 - speed, LEFT)
return (i, speed, RIGHT)7. 배열 한 칸씩 돌리기
from collections import deque
N, M, R = map(int, input.split())
arr = []
new_arr = [[0]*M for _ in range(N)]
q = deque()
for i in range(N):
arr.append(list(input().split()))
loops = min(N, M) // 2
for i in range(loops):
q.clear()
q.extend(arr[i][i:M-i])
q.extend([row[M-i-1] for row in arr[i+1:N-i-1]])
q.extend(arr[N-i-1][i:M-i][::-1])
q.extend([row[i] for row in arr[i+1:N-i-1]][::-1])
q.rotate(-R)
for j in range(i, M-i): # 상
new_arr[i][j] = q.popleft()
for j in range(i+1, N-i-1): # 우
new_arr[j][M-i-1] = q.popleft()
for j in range(M-i-1, i-1, -1): # 하
new_arr[N-i-1][j] = q.popleft()
for j in range(N-i-2, i, -1): # 좌
new_arr[j][i] = q.popleft()
return new_arrReference
728x90
반응형